杭电 2068 RPG的错排 （组合数+错排公式）

杭电2068 RPG的错排

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

听题目名字也知道，这题和错排公式肯定有关。

仔细阅读以下题目意思。猜对一半人即算正确。即保证n/2个人错排即可。

同时是选择i/n 的i个人进行错排，所以需要再用组合数C进行选择。

而组合数C的实现也是本题的点之一。

AC代码：

#include <iostream>
using namespace std;
long long sum;
long long f[30];
int n;
long long c(int n,int m) //组合数C的求法，需记忆
{int a = 1;for(int i = 1;i <= m; i++){a = a*(n-i+1);a /= i;}return a;
}
int main() {f[1] = 0 ;f[2] = 1;for(int i=3;i<=12;i++) {f[i] = (i - 1) * (f[i-1] + f[i-2]);//错排公式}while(cin>>n) {if(n==0) {return 0;}else {sum=1;for(int i=1;i<=n/2;i++) {sum+=c(n,i) * f[i]; //求出总和}cout<<sum<<endl;}}return 0;
}