CF340E Iahub and Permutations 题解
FFTotoro
·
·
题解
前言
Update：将写错的字母更改了一下。
偶然翻到一个 CF 远古题，看起来不错的样子，花了 3\operatorname{min} 写掉了。
翻了翻题解区，清一色的 DP，跟我一样用数论的寥寥无几。
解法
本做法需要使用容斥原理和基本数论。
考虑如果没有 a_i\ne i 的时候有多少种方法。显然地，设已经填好的数有 c 个，那么剩下的数可以看成一个全排列，答案为 (n-c)!。
我们发现如果直接判断合法的状态有多少种有些麻烦。正难则反，想想什么时候答案是不合法的。
假设先固定一个数在不合法的位置上，那么不管怎么放最终都是不合法的，剩下的数一共有 (n-c-1)! 种排法。
那如果两个数同时固定在不合法的位置上呢？利用上面的算法直接进行计算，会有重复计算的情况发生。这个时候就需要使用容斥原理，按照容斥原理的基本公式，设可能出现在不合法位置上的数的数量 ^{(1} 为 s，最终不合法的情况总数即为：
\sum\limits_{i=1}^{s}(-1)^iC_{s}^{i}(n-c-i)!
当然，最终我们要求得的是合法的方案数量，用 (n-c)! 减去上面的式子的值即可。细心的人可以发现，在上面的式子中如果 i=0，那么 \sum 后面那串东西的值就为 (n-c)!。所以，直接把 i\in[1,s] 改为 i\in[0,s] 即可。
- 这个数未在原数列中出现；
- 原数列中以这个数为下标的数是 $-1$，即这个数是待填入的；
可以证明，满足上述两个条件的数是有可能在最终不合法的方案中出现在不合法的位置上。
放代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int a[2001],f[2001]={1,1};
int qpow(int a,int b){
int r=1;
while(b){
if(b&1)r=r%mod*a%mod;
a=a%mod*a%mod; b>>=1;
}
return r;
}
int inv(int a,int b){return a*qpow(b,mod-2)%mod;}
int com(int n,int m){return inv(f[n],f[n-m]*f[m]%mod);}
// 经典三件套：快速幂、逆元和组合数
main(){
ios::sync_with_stdio(false);
int n,c=0,s=0,r=0; cin>>n;
for(int i=2;i<=n;i++)f[i]=f[i-1]*i%mod; // 阶乘预处理
map<int,bool> m,p;
for(int i=1;i<=n;i++){
if(cin>>a[i];a[i]==i){cout<<"0\n"; return 0;}
// 特判无解，如果原来的排列就起了冲突，那么最终一定无解
if(a[i]==-1)p[i]=true;
else m[a[i]]=true,c++;
}
for(int i=1;i<=n;i++)s+=(!m[i]&&p[i]); // 统计位置可能不合法的数的数量
for(int i=0;i<=s;i++) // 计算求和式
if(i&1)r=(r-com(s,i)*f[n-c-i]%mod+mod)%mod;
else r=(r+com(s,i)*f[n-c-i]%mod)%mod;
cout<<r<<endl;
return 0;
}
```