出处： Codeforces
主要算法：思维+DP
难度：4.8
题意：
有一个长度为$n$的排列（即各元素互不相同），其中有一些为-1。现要求将数填到这些-1上，使得原排列是一个错位排列。问有几种方法？
思路分析：
又是一道超级难的DP……
这不就是一个错排的模板题吗？不是只要看有几个-1就做多少的错排吗？确实，样例很不良心，那就给你一组反例吧……
5
-1 -1 2 3 -1
我们注意到了，并不是剩下的元素全是错排。因为原来我们认为2不能处在2的位置，但是4作为第二个元素是可以处在2的位置的。这样一来……就错得很离谱了。
但是这道题跟错排的关系依然是很大的。如果还不了解错排，可以参见我的另一篇博客「错位排列及有关例题」
我们首先可以根据数字是否为-1，以及数字i是否被使用过，把给的数字$a[i]$分成几类：
第一类，$a[i] = -1$ 且 数字$i$还没有被使用过（即数字$i$没有出现在给定的序列中），那么这个位置除了其位置本身对应的数字$i$以外，其他剩余的数字都可以填进来。
第二类，$a[i] = -1$ 且 数字$i$已经被使用过了，那么任何剩余的数字都可以填进来而且不会影响错位排列，想填什么就填什么。
第三类，$a[i] ≠ -1$ 且 数字$i$还没有被使用过，这种数字的个数应该和第一类相同，都是有限制的随便填。
第四类，$a[i] ≠ -1$ 且 数字$i$已经被使用过了，这种东西用都没有，就当他们是垃圾就好了。
首先我们可以统计出一类（或三类）数字的出现次数$y$，以及二类数字的出现次数$x$。我们只考虑二类数字可能组成的方案数，将有$x$个数字填到$x$个无限制的位置中，方案数就是$P_x^x$。
下面正式开始DP。令$f[i]$表示加入$i$个一类数字后的方案数。因此很容易得到$f[0] = P_x^x，即 x!$
下面开始状态转移。对于第$i$个一类数字，我们可以把他填入到无限制的二类数字的位置中，方案数是$x * f[i-1]$。剩余的就直接做错位排列即可。
代码注意点：
随手MOD
Code
/*By QiXingzhi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
#define int ll
const int N = ;
const int INF = ;
const int MOD = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
int n,ans,x,y;
int f[N],a[N],b[N];
inline int JieCheng(int x){
int res = ;
for(int i = ; i <= x; ++i){
res = (res * i) % MOD;
}
return res%MOD;
}
#undef int
int main(){
#define int ll
// freopen(".in","r",stdin);
n = r;
for(int i = ; i <= n; ++i){
a[i] = r;
if(a[i] != -){
b[a[i]] = ;
}
}
// for(int i = 1; i <= n; ++i){
// printf("%lld ",b[i]);
// }
for(int i = ; i <= n; ++i){
if(a[i] == - && b[i] > ){
++x;
}
// printf("a[%lld] = %lld b[%lld] = %lld\n",i,a[i],i,b[i]);
if(a[i] == - && b[i] == ){
++y;
}
}
// printf("x = %lld y = %lld\n",x,y);
f[] = JieCheng(x);
for(int i = ; i <= y; ++i){
f[i] = (x * f[i-] + (i-) * f[i-]) % MOD;
if(i > ) f[i] = (f[i] + (i-) * f[i-]) % MOD;
}
printf("%lld",f[y]);
return ;
}