题解 CF340E 【Iahub and Permutations】

### 除了DP的方法外，本题还可以使用容斥原理来做 （什么？你不知道什么是[容斥原理](https://baike.baidu.com/item/容斥原理/10146840)？） 我们来分析一下问题。 #### 先不考虑那个a[k]!=k的条件 一个排列缺少了一部分，如果要填回这些部分，那么我们填回的这些部分的方案数，就是缺失的部分的元素个数的全排列个数。 #### 考虑这个条件呢？ 正难则反，我们先考虑不合法的情况，然后再减去就好啦 先考虑有一个元素k满足a[k]==k的排列，其他的元素咱们先不管是不是合法。这就相当于先固定了这一个位置上的数，剩下的缺失元素做全排列。好了，我们找出来一些不合法的解，减去它们。 然而有些排列在这一步被计算了两遍三遍甚至四遍五遍一百遍怎么办呢？ 好，那我们考虑有两个元素i，j满足a[i]==1,且a[j]==j的排列。同样，其他的不管。这就是相当于固定了这两个元素，剩下的做全排列。由于我们分别考虑一个元素i和一个元素j的时候一定考虑过了这种情况，那就再加回来。 同样的，我们再考虑三个元素四个元素……好多好多元素不合法的情况，再分别做一些加减工作求出所有不合法排列的个数。诶？这不就是容斥原理计算的过程么…… 那我们如果把某一个元素a[i]不合法的情况的排列的集合记为S[ei],现在的问题就是要求所有S[ei]的并集的元素个数啦。 #### 公式来啦 （一些约定：使用符号C（m,n）表示从n个元素中选择m个元素的组合数，A（m,n）表示从n个元素中选择m个元素的排列数，sigma（i，m，n）f（i）表示从m开始到n的所有整数i的f（i）求和） 我们设原排列有p个元素缺失，有q个缺失的元素填回去后有可能满足a[k]==k的非法条件，即记q为原序列中a[k]==-1,且k未出现在给出序列中的元素个数。 那对于这q个集合选取集合计算时，若选取了i个元素，则选取集合方式就有 C（i，q）种，剩余（p-i）个元素做全排列，即每种方式下有A（p-i，p-i）个全排列。 由于我们计算的是反面，所以要从全部里减去。因此计算选取i个元素时就要在答案里加上（-1）^i \* C（i,q）\* A(p-i,p-i)，那么总的答案就是 A（p，p）+sigma（i，1，q）（（-1）^i \* C（i,q）\* A(p-i,p-i)） ##### 这样我们就省去了DP的过程把题目转化成了好想好写的容斥原理啦 #### 小Tips 要开long long,并且在mod 1e9+7下ans可能会输出负，这时要调整成正的。 ##### 附上代码一份：（代码渣，dalao见谅） ```cpp #include<iostream> #define ll long long using namespace std; ll M=1000000007;//模数 ll fac[2010];//阶乘 ll facinv[2010];//阶乘逆元 ll ext[2010];//某元素是否已经在排列中 ll a[2010];//排列 ll num,cnt;//分别记录缺失元素个数和可能有a[i]==i的元素个数 ll qpow(ll d,ll p)//快速幂 { ll ret=1; while(p) { if(p%2) ret=(ret*d)%M; d=(d*d)%M; p/=2; } return ret; } int main() { ll n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]==-1) num++; else ext[a[i]]=1; } for(int i=1;i<=n;i++) { if(a[i]==-1&&!(ext[i])) cnt++; } fac[0]=1; for(int i=1;i<=num;i++)//求阶乘 { fac[i]=(fac[i-1]*i)%M; } facinv[num]=qpow(fac[num],M-2); for(int i=num-1;i;i--)//求逆元 { facinv[i]=facinv[i+1]*(i+1)%M; } facinv[0]=1; ll ans=fac[num]; for(int i=1;i<=cnt;i++)//计算答案 { ans+=((((qpow(-1,i%2)*fac[cnt])%M)*facinv[cnt-i]%M)*facinv[i]%M)*fac[num-i]%M; } while(ans<0)//调整 { ans+=M; } cout<<ans%M; return 0; } ```