去年看错排公式，死都看不懂，基础扎实之后再来看就略懂了。
公式： dp[ n ] = ( n-1 ) * ( dp[n-1] + dp[n-2] )
解析公式：比如有n个元素，各对应n个正确位置，dp[n]表示这n个元素全部排错的可能。
比如有元素：1 2 3 4 5 ... k ... n
1.假设第n个元素，要它在错误的位置上，则有n-1种情况。
2.对于剩下的n-1个元素，随便取一个位置上的元素k，要它在错误的位置上，则有2种情况
1）它在第n个元素的位置，相当于n和k两个元素交换位置，和其它没有关系，剩余n-2个元素爱怎么排就怎么排，dp[n-2]
2）不在第n个元素的位置，假设把n作为k的正确位置，则1 2 3 4 5...(k)...n，除去正确位置k，就是n-1个元素放在n-1个位置上，dp[n-1]。
初始化：
dp[1]=0;
dp[2]=1;
dp[ n ] = ( n-1 ) * ( dp[n-1] + dp[n-2] );
hdu2068：http://acm.hdu.edu.cn/showproblem.php?pid=2068
题解：
有n个人要猜对一半以上，就是错一半以下，排错公式。
对于这些错的人，也可以互不相同，组合数公式。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; ll ans[20]; ll c[30][30];///C(n,m) = C(n-1,m) + C(n-1,m-1) void init() { memset(ans,0,sizeof(ans)); memset(c,0,sizeof(c)); ans[0]=1;///一个都没有错只有1种 ans[1]=0; ans[2]=1; ans[3]=2; for(ll i=4;i<20;i++) ans[i] = (i-1) * ( ans[i-1]+ans[i-2] ); for(int i=0;i<30;i++) c[i][0]=1; for(int i=1;i<30;i++) for(int j=1;j<=i;j++) c[i][j] = c[i-1][j] + c[i-1][j-1]; } int main()///hdu2068 RPG错排 { init(); int n; while(scanf("%d",&n) && n) { ll res=0; for(int i=0;i<=n/2;i++) res += ans[i] * c[n][i]; printf("%lld ",res); } return 0; }
hdu2049：http://acm.hdu.edu.cn/showproblem.php?pid=2049
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; ll ans[30]; ll c[30][30];///C(n,m) = C(n-1,m) + C(n-1,m-1) void init() { memset(ans,0,sizeof(ans)); memset(c,0,sizeof(c)); ans[0]=0;///一个都没有错只有1种 ans[1]=0; ans[2]=1; ans[3]=2; for(ll i=4;i<25;i++) ans[i] = (i-1) * ( ans[i-1]+ans[i-2] ); for(int i=0;i<30;i++) c[i][0]=1; for(int i=1;i<30;i++) for(int j=1;j<=i;j++) c[i][j] = c[i-1][j] + c[i-1][j-1]; } int main()///hdu2049 考新朗 { init(); int n,t; scanf("%d",&t); while( t-- ) { int n,m; scanf("%d%d",&n,&m); ll res=0; res = ans[m] * c[n][m]; printf("%lld ",res); } return 0; }