描述
一日，崔克茜来到小马镇表演魔法。
其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？
输入
第一行一个整数 T (T ≤ 100)表示数据组数。 对于每组数据，第一行有两个整数 n 和 k (1 ≤ n ≤ 300, 0 ≤ k ≤ n)。 第二行有 n 个整数 ai，表示第 i 个盒子中，装有可以打开第 ai 个盒子的钥匙。
输出
对于每组询问，输出一行表示对应的答案。要求相对误差不超过四位小数。
样例输入
4 5 1 2 5 4 3 1 5 2 2 5 4 3 1 5 3 2 5 4 3 1 5 4 2 5 4 3 1
样例输出
0.000000000 0.600000000 0.900000000 1.000000000
1，每个盒子都有一个入度和一个出度，以之前二分图拆点的经验来看，必然会形成很多个环。
2，每个环至少选择一个盒子。
3，每个环至少选择一个盒子的组合数，联想到母函数，组合数。
4.自由YY。可以DP，但是误差可能大一些。可以全部求出来再除，这样误差小一些。
（ps：学会了母函数再搞组合是要多一分灵感！弯的four）
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<cmath> using namespace std; const int maxn=310; double c[maxn][maxn]; double a[maxn],b[maxn]; int loop[maxn],num[maxn],cnt,laxt[maxn],n; void init() { cnt=0; for(int i=0;i<=n;i++){ a[i]=b[i]=num[i]=loop[i]=laxt[i]=0; } } void getc() { int i,j; for(i=1;i<=300;i++){ c[i][0]=c[i][i]=1.0; for(j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } return ; } void geta() { int i,j,k; for(i=1;i<=num[1];i++) a[i]=c[num[1]][i],b[i]=0.0; for(i=2;i<=cnt;i++){ for(j=0;j<=n;j++) for(k=1;k<=num[i];k++) if(j+k<=n) b[j+k]+=a[j]*c[num[i]][k];//不是+1 for(j=0;j<=n;j++){ a[j]=b[j]; b[j]=0; } } } int main() { int i,j,T,k; scanf("%d",&T); getc();//组合数C while(T--){ scanf("%d%d",&n,&k); init(); for(i=1;i<=n;i++) scanf("%d",&laxt[i]); for(i=1;i<=n;i++){//分组 if(!loop[i]){ ++cnt; for(j=i;;j=laxt[j]){ if(loop[j]) break; loop[j]=cnt; num[cnt]++; } } } geta();//保证每个环至少一个的母函数 printf("%.9lf ",a[k]/c[n][k]); } return 0; }