CF341C. Iahub and Permutations
题目传送门
题意
给你一个排列,其中有些位置为 \(-1\),表示这个位置的数被挖掉了, 你现在要填上这些数,使得结果是一个\(a_i \neq i\) 的排列。
问合法方案数。
题解
就只写做法的了。
考虑把没出现的数字一个一个填进去, 我们发现不同数字之间是没有区别的,唯一的区别是有些数字受限制, 而有些可以随便填。
比如说, 对于一个数字 \(x\), 这个数字不能放在第\(x\)个, 假如还有 \(m\) 个位置可以填入, 那么这个数字只能填入其中 \(m-1\) 个位置, 但是:如果\(x\)位置上已经有数字填进去了, 那么这个数字就不受限制了, 它可以填入剩下的 \(m\) 个位置中。
记 \(f_{i, j}\) 表示还要填入 \(i\) 个数字, 其中 \(j\) 个是受限制的, 其他可以随便填。有:
\[ f_{i,0} = i! \]\[ f_{i, j} = (i-j) f_{i-1, j-1} + (j-1) f_{i-1, j-2} \]如何理解第二条式子?对于每个受限的数都有一个受限的位置, 考虑每次取第一个受限的位置, 往里面放一个数, 有两种情况:
假如放入的是一个不受限的数, 那么不能放在这个位置的那个数现在就不受限了, 所以 \(j-1\)
假如放入的是另一个受限的数, 那么就少了1个受限的数,因为他被放了, 然后又因为原本那个数不受限了, 所以是 \(j-2\)
就这样了
实现
#include
#include
#define ll long long
using namespace std;
int read(){
int num=0, flag=1; char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c == '-') c=getchar(), flag=-1;
while(isdigit(c)) num=num*10+c-'0', c=getchar();
return num*flag;
}
const int N = 2005;
const ll mod = 1e9+7;
int n, a[N], vis[N];
ll f[N][N];
int main(){
n = read();
for(int i=1; i<=n; i++) a[i]=read();
f[0][0] = 1;
for(int i=1; i<=n; i++) f[i][0] = f[i-1][0]*i%mod;
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
f[i][j] = f[i-1][j-1] * (i-j) % mod;
if(j > 1) f[i][j] = (f[i][j] + (j-1) * f[i-1][j-2]) % mod;
}
}
int cnt1=0, cnt2=0;
for(int i=1; i<=n; i++) if(a[i] != -1) vis[a[i]]=1;
for(int i=1; i<=n; i++) if(a[i] == -1) cnt1++, cnt2+=!vis[i];
printf("%d\n", f[cnt1][cnt2]);
return 0;
}