题目大意

• 给定一个长度为 $n$ 的序列 $a$，求将序列中所有的 $-1$ 替换成一个正整数使得 $\{a_1,\ a_2,\ \cdots,\ a_n\}=\{1,\ 2,\ \cdots,\ n\}$ 且 $\forall\ 1\leq i\leq n,\ a_i\not=i$ 的方案数目模 $10^9+7$。

• $2\leq n\leq 2\times 10^3$

分析

显然当 $\exists\ a_i=i$ 时，答案为 $0$。

将 $a_i=-1$ 的位置 $i$ 分为两类：

• 第一类，$\forall\ a_j\not=i$，即 $i$ 这个数的位置还未确定，则该位置只能放除了 $i$ 以外的数；

• 第二类，$\exists\ a_j=i$，即 $i$ 这个数的位置已经确定，则该位置放的数不受限制。

设第一类的位置有 $tot_1$ 个，第二类的位置有 $tot_2$ 个。问题转化为有 $tot_1$ 个位置只能放除了 $i$ 以外的数，有 $tot_2$ 个位置放的数不受限制，求方法数。

解法 1

容斥原理。

考虑满足 $a_i=i$ 的位置 $i$ 的个数，下面研究至少有 $k$ 个位置满足 $a_i=i$ 的方法数。

从只能放除了本身以外的数的 $tot_1$ 个位置中，选出 $k$ 个放本身值，有 $C_{tot_1}^k$ 种情形。剩余 $tot_1+tot_2-i$ 个位置任意放，有 $\left(tot_1+tot_2-k\right)!$ 种情形。由乘法原理，方法数为

$$\binom{tot_1}k\cdot\left(tot_1+tot_2-k\right)!.$$

由容斥原理，最终方法数为

$$\sum_{i=0}^{tot_1}\binom{tot_1}i\cdot\left(tot_1+tot_2-i\right)!\cdot\left(-1\right)^i. $$

预处理组合数时间复杂度 $\Theta(n^2)$，预处理阶乘时间复杂度 $\Theta(n)$，计算时间复杂度 $\Theta(n)$，最终时间复杂度 $\Theta(n^2)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,a[2001],tot1,tot2;
//tot1: 不能放自身的位置个数 
//tot2: 可以随便放的位置个数 
long long answer;
bool p[2001];

long long fac[2001],C[2001][2001];
void initfac(int N){
	fac[0]=1;
	for(int i=1;i<=N;i++)
		fac[i]=fac[i-1]*i%mod;
}
void initC(int N){
	for(int i=0;i<=N;i++)
		C[i][0]=1;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if(a[i]==i){
			printf("0\n");
			return 0;
		}
		if(a[i]!=-1)p[a[i]]=true;
		else tot1++;
	}
	initfac(tot1);
	for(int i=1;i<=n;i++)
		if(a[i]==-1&&p[i])tot1--,tot2++;
	initC(tot1);
	for(int i=0;i<=tot1;i++){
		int t=(i&1)?-1:1;
		answer+=fac[tot1+tot2-i]*C[tot1][i]%mod*t;
		answer=(answer+mod)%mod;
	}
	printf("%lld\n",answer);
    return 0;
}

解法 2

二维动态规划。

设状态 $dp_{i,\ j}$ 表示有 $i$ 个位置只能放除了本身以外的数，有 $j$ 个位置放的数不受限制时的方法数。则答案为 $dp_{tot_1,\ tot_2}$。

显然有边界 $dp_{0,\ j}=j!$，下面讨论边界 $dp_{i,\ 0}$。

位置 $i$ 只能放 $1\sim i-1$ 的数，有 $i-1$ 种可能。不妨设位置 $i$ 放的是 $x$。

• 位置 $x$ 放的是 $i$。此时有 $dp_{i-2,\ 0}$ 种情况；
• 位置 $x$ 放的不是 $i$。此时等价于 $dp_{i-1,\ 0}$ 的情况。

综上所述，$dp_{i,\ 0}=(i-1)\left(dp_{i-1,\ 0}+dp_{i-2,\ 0}\right)$。

讨论 $dp_{i,\ j}$（$i,\ j\geq 1$）。任取一放的数不受限制的位置。

• 若放的是这 $i$ 个数中的数，有 $dp_{i-1,\ j}$ 种情况，共有 $i\cdot dp_{i-1,\ j}$ 种情况；

• 若放的是这 $j$ 个数中的数，有 $dp_{i,\ j-1}$ 种情况，共有 $j\cdot dp_{i,\ j-1}$ 种情况；

综上所述，$dp_{i,\ j}=i\cdot dp_{i-1,\ j}+j\cdot dp_{i,\ j-1}$。

时间复杂度 $\Theta(n^2)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,a[2001],tot1,tot2;
//tot1: 不能放自身的位置个数 
//tot2: 可以随便放的位置个数 
long long dp[2001][2001];
//dp[i][j]: 有 i 个位置不能放自身，j 个位置可以随便放 
bool p[2001];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if(a[i]==i){
			printf("0\n");
			return 0;
		}
		if(a[i]!=-1)p[a[i]]=true;
		else tot1++;
	}
	for(int i=1;i<=n;i++)
		if(a[i]==-1&&p[i])tot1--,tot2++;
	dp[0][0]=1;
	for(int i=2;i<=tot1;i++)
		dp[i][0]=(dp[i-1][0]+dp[i-2][0])%mod*(i-1)%mod;
	for(int j=1;j<=tot2;j++)
		dp[0][j]=dp[0][j-1]*j%mod;
	for(int i=1;i<=tot1;i++)
		for(int j=1;j<=tot2;j++)
			dp[i][j]=(i*dp[i-1][j]%mod+j*dp[i][j-1]%mod)%mod;
	printf("%d\n",dp[tot1][tot2]);
    return 0;
}

解法 3

动态规划。

设状态 $dp_i$ 表示有 $i$ 个位置只能放除了本身以外的数，有 $tot_2$ 个位置放的数不受限制时的方法数。则答案为 $dp_{tot_1}$。

显然有边界 $dp_0=tot_2!$，下面讨论 $dp_i$（$i\geq 1$）。

• 若 $i$ 这个数放的是不受限制的 $tot_2$ 个位置中的一个，有 $tot_2dp_{i-1}$ 种情况；

• 其余情况类似「解法 2」中错位排列的求法，有 $(i-1)(dp_{i-1}+dp_{i-2})$ 中情况。

综上所述，$dp_i=tot_2dp_{i-1}+(i-1)(dp_{i-1}+dp_{i-2})$。

注意 $i=1$ 时，$dp_{i-2}$ 会发生数组越界，需要特殊处理。

时间复杂度 $\Theta(n)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,a[2001],tot1,tot2;
//tot1: 不能放自身的位置个数 
//tot2: 可以随便放的位置个数 
long long answer;
bool p[2001];
long long dp[2001]={1};

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if(a[i]==i){
			printf("0\n");
			return 0;
		}
		if(a[i]!=-1)p[a[i]]=true;
		else tot1++;
	}
	for(int i=1;i<=n;i++)
		if(a[i]==-1&&p[i])tot1--,tot2++;
	for(int i=1;i<=tot2;i++)dp[0]=dp[0]*i%mod; 
	dp[1]=tot2*dp[0]%mod;
	for(int i=2;i<=tot1;i++){
		dp[i]=(dp[i-1]+dp[i-2])%mod*(i-1)%mod;
		dp[i]=(dp[i]+tot2*dp[i-1]%mod)%mod;
	}
	printf("%lld\n",dp[tot1]);
    return 0;
}