?錯排問題本質上就是一個動態規劃問題，其狀態轉移方程為：
記d[n]為n個人錯排情況的總數。
那么策略可以描述為：分析第n個人錯排的可能情況：
1）前n-1個人滿足錯排的情況，那么第n個人加入后還要錯排意味著第n個人與前n-1個人里的任意一個交換字條（共有n-1種交換法）
2）若前n-1個人并不滿足錯排，但加入第n個人后滿足錯排。這必然意味著第n個人加入后與前n-1中的某個人交換字條后才滿足n個人錯排。而又因為原本前n-1人不滿足錯排，那么前n-1個人中至少有一個人手上的字條是匹配的，那么第n個人就只能與匹配者交換字條。此時可以證明前n-1人中字條匹配者人數不能大于1，可以反證（如果有兩人字條匹配，那么在第n個人交換后必然還有一個人字條匹配，不滿足）
tip：
printf()輸出百分號的時候，有的oj上必須寫成%%，有的可以寫成%。嚴格點的話，還是采用第一種寫法穩妥。
ac代碼如下：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; //錯排思想 long long d[30]; long long f(int n){if(d[n]!=-1){return d[n];}else{d[n]=(n-1)*(f(n-1)+f(n-2));return d[n];} } int main(void){memset(d,-1,sizeof(d));d[1]=0;d[2]=1;f(20);int c;scanf("%d",&c);while(c--){int n;scanf("%d",&n);long long cnt1=d[n];long long cnt2=1;for(int i=1;i<=n;i++){cnt2*=i ;}double ans=double(cnt1)/double(cnt2);printf("%.2lf%%\n",ans*100);//printf("%.2lf%\n",ans*100); //這樣寫就是wronganser }return 0; }
?
)
