1140. 箱里的鑰匙
有N個編號為1到N的箱子和N個編號為1到N的鑰匙，第i號鑰匙只能用來打開第i號箱子。現在我們隨機地將一把鑰匙鎖進一個箱子里，即每個箱子里都恰好有
一把鑰匙，保證所有的情況都等可能性地出現?，F在你有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