Description

現(xiàn)有r個互不相同的盒子和n個互不相同的球，要將這n個球放入r個盒子中，且不允許有空盒子。則有多少種放法？

Input

n, r(0 <= n, r <= 10)。

Output

有多少種放法。

Sample Input

3 2

Sample Output

6

Source

SDNU ACM-ICPC 2010復(fù)賽(2010級) 思路：這道題用的是斯特林函數(shù)。 第一類斯特林函數(shù)：將 n 個不同元素構(gòu)成m個圓排列，如果要將n + 1個元素構(gòu)成m個圓排列，考慮第n + 1個元素： ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）如果n個元素構(gòu)成m - 1個圓排列，則第n + 1個元素獨(dú)自構(gòu)成一個圓排列：s(n, m - 1)； ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）如果n個元素構(gòu)成m個圓排列，則第n + 1個元素插入任意元素的左邊：n * s(n, m)； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 總和s(n + 1, m) = s(n, m - 1) + n * s(n, m)。 第二類斯特林函數(shù)：將n個不同的球放入m個無差別的盒子中，要求盒子非空，考慮第n + 1個元素： ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）如果n個元素構(gòu)成m - 1個集合，則第n + 1個元素就構(gòu)成單獨(dú)一個集合：s(n, m - 1); ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）如果n個元素構(gòu)成m個集合，則第n + 1個元素就查到任意一個集合：m * s(n, m); ????????????????????? ? ? ? ? 總和s(n + 1, m) = s(n, m - 1) + m * s(n, m)。 但是題目要求是r個不同的盒子，r個不同盒子的排列就是 r!，所以最后的答案應(yīng)該乘以r的階乘。 #include<bits/stdc++.h> using namespace std;#define ll long long #define eps 1e-9const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 100000 + 8;int a[18][18];int main() {int n, r, sum = 1;memset(a, 0, sizeof(a));scanf("%d%d", &n, &r);a[1][1] = 1;for(int i = 2; i <= n; i++){for(int j = 1; j <= r; j++){a[i][j] = a[i - 1][j - 1] + a[i - 1][j] * j;}}for(int i = 1; i <= r; i++)sum *= i;printf("%d\n", sum * a[n][r]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/RootVount/p/11418879.html

總結(jié)

以上是生活随笔為你收集整理的SDNU 1011.盒子与球（斯特林函数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。