hdu2048 神、上帝以及老天爷（错排）

http://acm.hdu.edu.cn/showproblem.php?pid=2048

题意：n个人抽签，每个人不选择自己的概率。

错排思想：

当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用people(n)表示,那么people(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.

第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;

第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有people(n-2)种方法;2,不把它放到位置n（k也有一个限制位置，类似一个新的错排，只是规模变小了）,这时,对于这n-1个元素,有people(n-1)种方法;

综上得到

people(n)=(n-1)[people(n-2)+people(n-1)]

特殊地，people(1)=0,people(2)=1

int a[maxn];
void solve(){
    int n ;
    cin >> n ;
    int ans = 1 ;
    rep(i , 1 , n){
        ans = ans * i ;
    }
    printf("%.2lf%%
" , 100.0*a[n]/ans);
}

signed main()
{
    a[1] = 0 , a[2] = 1 ;
    rep(i , 3 , 20){
        a[i] = (i-1)*(a[i-1] + a[i-2]);
    }
    //int t ; scanf("%lld" , &t);while(t--)
    int _ ;cin>>_;while(_--)
        solve();
}