题目大意:
某人写了n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
分析:
方法一:递推
已经处理了f[0]~f[n-1],考虑f[n],新来了一个数n,这个数要放错位,有n-1种情况。其他的数的放置每次都有f[n-1]种情况,被n占用位置的数k,将k放在n位置,可以再多出f[n-2]种情况。
证明:可以将n位置想成是一个k的原位置,由于之前f[n-1]种情况中,不会出现让k在原位置的情况,所以现在把k放在这个n的“新”原位置上,不会将方案数重复计算。
#includeusing namespace std;long long f[30];int n;int main(){ cin>>n; f[0]=1; f[1]=0; for(int i=2;i<=n;i++) f[i]=(i-1)*(f[i-1]+f[i-2]); cout<
方法二:容斥
首先有n!种排列,减去单个信放正确的情况,每个有(n-1)!种,但是每2个信封被放重复的情况多减了,所以再加回来。再减去3个,加上4个...
dfs容斥。预处理阶乘
#includeusing namespace std;long long fac[30];int n;long long ans;void dfs(int x,int k){ if(x==n+1) { if(k&1) ans-=fac[n-k]; else ans+=fac[n-k]; return; } dfs(x+1,k); dfs(x+1,k+1);}int main(){ cin>>n; fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; dfs(1,0); cout<