HDU 3625 Exmining the Rooms(第一類スターリング数、結合数学)

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3625
数学を組み合わせます
スターリング数は初めて聞きました.定義はウィキペディアを参照してください.https://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E7%81%B5%E6%95%B0
N個の元素は、K個のリングを構成して配列します.
いくつかの公式があります
S(N,0)=0
S(N,N)=1
S(0,0)=0
S(N,K)=S(N-1,K-1)+S(N-1,K)*(N-1)
問題が特別に規定されています.1単独で輪にすることはできません.すなわち、S(N,K)−S(N−1,K−1)こそ、k個のループを構成する方法の数である.
これらのメーターを知っていればいいです.
ブログを参照してください:http://www.cnblogs.com/nanke/archive/2011/09/07/2170290.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
ll fac[21] = {1};
ll stirling[21][21];
int main() {
	int i, j;
	for(i = 1; i <= 20; i++) {
		fac[i] = fac[i - 1] * i;
	}
	for(i = 1; i <= 20; i++) {
		stirling[i][0] = 0;
		stirling[i][i] = 1;
		for(j = 1; j <= 20; j++) {
			if(i != j) stirling[i][j] = stirling[i - 1][j - 1] + (i - 1) * stirling[i - 1][j];
		}
	}
	int t, n, k;
	scanf("%d",&t);
	while(t--) {
		scanf("%d %d", &n, &k);
		ll sum = 0;   //  n>1, k>0 ，       
		for(i = 1; i <= k; i++) {  //       k         
			sum += stirling[n][i] - stirling[n - 1][i - 1];
		}
		printf("%.4lf
",(double)sum/fac[n]);
	}
    return 0;
}