1140. 箱里的钥匙
有N个编号为1到N的箱子和N个编号为1到N的钥匙，第i号钥匙只能用来打开第i号箱子。现在我们随机地将一把钥匙锁进一个箱子里，即每个箱子里都恰好有
一把钥匙，保证所有的情况都等可能性地出现。现在你有M个炸弹，每个炸弹可以用来炸开一个箱子，一旦你把某个箱子打开，你就可以取出其中的钥匙，从而有可
能用这钥匙打开更多的箱子。你的策略很简单，当没有箱子可以打开时，随便选一个箱子，用炸弹炸开它，取出钥匙并继续打开尽可能多的箱子，直至没有箱子可以
打开，然后继续使用下一颗炸弹。
现给定N，你的任务是求出你可以取得所有钥匙的概率。这个概率必须输出成分数“A/B”的形式，A和B都是正整数且公约数必须为1。
输入格式
输入一行，包含空格隔开的两个数N和M
输出格式
输出为A/B的形式。
输入样例
3 1
输出样例
1/3
数据规模与约定
1 ≤ N ≤ 20, 1 ≤ M ≤ N
解析:
这个题目基本上就是一个数学题,涉及到第一类stirling数的求解.
所谓
第一类stirling数,例如S[n,k]表示
将一个大小为n的集合分成k个部分,每个部分的元素个数不小于1,且形成环的
总方法数.
一个元素也算作单独的环.
容易的到
S[1,1]=1;
S[n,0]=0;
当n<k时,S[n,k]=0;
对合法的n,k,满足: S[n,k]=S[n-1,k-1]+(n-1)*S[n-1,k];
把n当作钥匙(也即箱子)的个数,k为钥匙所放位置形成的"环",每破坏一个箱子,都可以得到该箱子所属环的所有钥匙,k表示实际的环的个数
当k>m时便不可能取得到所有的钥匙.
这样下面的代码就很好理解了.
1 #include<iostream>
2 using namespace std;
3 const int MAXN=30;
4 template <class T>
5 T Gcd(T a,T b)
6 {
7 return (!a)? b : Gcd(b%a,a);
8 }
9
10 int main()
11 {
12 freopen("box.in","r",stdin);
13 freopen("box.out","w",stdout);
14 long long n,m,S[MAXN][MAXN];
15 cin >> n >> m;
16 memset(S,0,sizeof(S));
17 S[1][1]=1;
18 for (int i=2;i<=n;++i)
19 for (int j=1;j<=i;++j)
20 S[i][j]=S[i-1][j-1]+(i-1)*S[i-1][j];
21 long long B=1;
22 for (int i=2;i<=n;++i) B*=i;
23 long long A=B;
24 for (int i=m+1;i<=n;++i) A-=S[n][i];
25 long long G=Gcd(A,B);
26 cout << A/G << '/' << B/G << endl;
27 return 0;
28 }
29