1140.  箱里的鑰匙

---

有N個(gè)編號(hào)為1到N的箱子和N個(gè)編號(hào)為1到N的鑰匙，第i號(hào)鑰匙只能用來打開第i號(hào)箱子?，F(xiàn)在我們隨機(jī)地將一把鑰匙鎖進(jìn)一個(gè)箱子里，即每個(gè)箱子里都恰好有 一把鑰匙，保證所有的情況都等可能性地出現(xiàn)。現(xiàn)在你有M個(gè)炸彈，每個(gè)炸彈可以用來炸開一個(gè)箱子，一旦你把某個(gè)箱子打開，你就可以取出其中的鑰匙，從而有可 能用這鑰匙打開更多的箱子。你的策略很簡單，當(dāng)沒有箱子可以打開時(shí)，隨便選一個(gè)箱子，用炸彈炸開它，取出鑰匙并繼續(xù)打開盡可能多的箱子，直至沒有箱子可以 打開，然后繼續(xù)使用下一顆炸彈。

現(xiàn)給定N，你的任務(wù)是求出你可以取得所有鑰匙的概率。這個(gè)概率必須輸出成分?jǐn)?shù)“A/B”的形式，A和B都是正整數(shù)且公約數(shù)必須為1。

輸入格式

輸入一行，包含空格隔開的兩個(gè)數(shù)N和M

輸出格式

輸出為A/B的形式。

輸入樣例

3 1

輸出樣例

1/3

數(shù)據(jù)規(guī)模與約定

1 ≤ N ≤ 20, 1 ≤ M ≤ N

解析:
這個(gè)題目基本上就是一個(gè)數(shù)學(xué)題,涉及到第一類stirling數(shù)的求解.
所謂第一類stirling數(shù),例如S[n,k]表示將一個(gè)大小為n的集合分成k個(gè)部分,每個(gè)部分的元素個(gè)數(shù)不小于1,且形成環(huán)的總方法數(shù).
一個(gè)元素也算作單獨(dú)的環(huán).
容易的到
    S[1,1]=1;
    S[n,0]=0;
當(dāng)n<k時(shí),S[n,k]=0;
對(duì)合法的n,k,滿足: S[n,k]=S[n-1,k-1]+(n-1)*S[n-1,k];
把n當(dāng)作鑰匙(也即箱子)的個(gè)數(shù),k為鑰匙所放位置形成的"環(huán)",每破壞一個(gè)箱子,都可以得到該箱子所屬環(huán)的所有鑰匙,k表示實(shí)際的環(huán)的個(gè)數(shù)
當(dāng)k>m時(shí)便不可能取得到所有的鑰匙.
這樣下面的代碼就很好理解了.