CF341C. Iahub and Permutations [DP 排列]

http://codeforces.com/contest/341/problem/C

---

题意：

有一个长度为n的排列a，其中有一些位置被替换成了-1。你需要尝试恢
复这个排列，将-1替换回数字。
求有多少种可行的替换方法，满足得到的是一个排列，且不存在ai = i的
位置。n $le$ 2000

---

感觉很巧妙的转化：

$n$排列$ ightarrow n*n$的棋盘上放$rook$

对角线是不能放的

我们把放了$rook$的行和列删除后，可以发现每列和每行最多一个不能放的位置

$f[i][j]$表示在删除后的棋盘上放了$i$列，有$j$个不能放的位置

$f[i][j]=f[i][j-1]-f[i-1][j-1] f[i][0]=i!$

因为$f[i][j-1] ightarrow f[i][j]$多了一个不能放的位置，对应方案数为$f[i-1][j-1]$

代码这么好写的题$Candy?$因为处理$n,m$,$ll$取模$WA$了三次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2005,INF=1e9+5,MOD=1e9+7;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,k,del[N],a[N];
ll f[N][N];
void dp(){
    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<=m;j++) f[i][j]=(f[i][j-1]-f[i-1][j-1]+MOD)%MOD;
    printf("%I64d",f[n][m]);
}
int main(){
    //freopen("in","r",stdin);
    n=read();m=n;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]!=-1) k++,del[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=-1&&a[a[i]]==-1) m--;//printf("look %d %d %d %d
",i,a[i],del[a[i]],a[a[i]]);;
    }
    n-=k;m-=k;
    //printf("hi %d %d
",n,m);
    dp();
}