题目描述
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
输入输出格式
输入格式：
一个信封数n
输出格式：
一个整数，代表有多少种情况。
输入输出样例
输入样例#1：
样例1：2 样例2：3
输出样例#1：
样例1：1 样例2：2
传说中的错排问题。
解法一：容斥。
设共有n个位置。所有的排列情况共有n!种，某个位置x排对的情况有(n-1)!种，总数为C[n][1](←组合数)*(n-1)!种。再用容斥原理把多减的加回来，以此类推。
得到： ans= n!-C[n][1]*(n-1)!+C[n][2]*(n-2)!-C[n][3]*(n-3)!......C[n][n]*(n-n)!
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int mxn=;
int n;
int c[mxn][mxn];
LL f[mxn];
void init(){
int i,j;f[]=;
for(i=;i<=n;i++)f[i]=f[i-]*i;
for(i=;i<=n;i++)c[i][]=;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
c[i][j]=c[i-][j-]+c[i-][j];
return;
}
int main(){
scanf("%d",&n);
init();
int i,j;
LL ans=f[n];
for(i=;i<=n;i++){
if(i&)ans-=f[n-i]*c[n][i];
else ans+=f[n-i]*c[n][i];
}
cout<<ans<<endl;
return ;
}
解法二：递推
错排问题递推公式：
f[0]=0;f[1]=0;f[2]=1 ,此后 $ f[n]=(n-1)*(f[n-1]+f[n-2]) $
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int f[mxn];
int n;
int main(){
cin>>n;
f[]=f[]=;
f[]=;
for(int i=;i<=n;i++){
f[i]=(i-)*(f[i-]+f[i-]);
}
cout<<f[n]<<endl;
return ;
}