思路简述
把题目中的求概率改成求比例，那就是求满足 \(a_i\not= i\) 排列的个数占全排列个数的比例
我们知道 \(n\) 的全排列个数为 \(n!\)，那么要计算的就是满足 \(a_i\not= i\) 排列的个数，暂且用 \(\{a_i\not= i \}\) 表示
设 \(n\) 个数中 \(\{a_i\not= i \}\)个数为 \(f_n\)
显然 \(\{a_i=i\}\) 个数为 \(1\)，然后随便调换其中数的位置，可以发现， \(n\) 个数中有 \(k\) 个数满足 \(a_i\not= i\) 的排列有 \(C_n^k\times f_k\) 个
那么我们可以写出转移方程：
\[f_n=n!-\sum_{k=2}^{n-1}C_n^k\times f_k-1\]
显然 \(f_2=1\)，然后预处理一下阶乘和组合数，就可以递推答案了。
代码实现
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef long long LL;
LL C[25][25],f[25];
LL fac[25];
int T,n;
int main(){
fac[0]=1;
for(int i=1;i<=20;i++){
fac[i]=fac[i-1]*i;C[i][0]=1;C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
f[2]=1;
for(int i=3;i<=20;i++){
f[i]=fac[i]-1;
for(int j=i-1;j>=2;j--)
f[i]-=C[i][j]*f[j];
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
double ans=1.0*(int)(1.0*f[n]/fac[n]*10000+0.5)/100;
printf("%.2lf%%\n",ans);
}
return 0;
}