CF 341C: Iahub and Permutations

题目链接：

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

题目大意：

给定一个含有N个位置的序列，某些位置上的数字已经确定，某些位置上的数字没有确定。

求这个序列可能产生多少种错排(a[i] != i)。

算法：

这题的做法基本就是DP或容斥。

先说一下DP的解法。感谢wuyiqi大牛的耐心讲解。  >_<

显然所有已经填好的位置可以不管，我们只看 a[i] = -1 的位置。

x 表示目前有多少个位置使得a[i] = -1 且数字 i 已经被填在某个位置上，称为无限制位置。

y 表示目前有多少个位置使得a[i] = -1 且数字 i 没有被填在某个位置上，称为有限制位置。

那么，最一开始的时候，我们先把 y 个有限制位置抛弃不看。

因为a[i] = -1 且 i 也没有出现在任何位置上，所以忽略不看不会有影响。

现在我们先把 x 个无限制的位置填好。

由于有 x 个数的 a[i] = -1 但是数字 i 已经被使用了。所以也一定有 x 个数的a[i] != -1但是数字 i 还没被用。

就把这 x 个没使用的数字放在 x 个被填的位置上。方法数是 x! 。

现在我们把 y 个无限制的位置一个接一个的加进来

用 d[i] 表示已经有多少个无限制的位置被加进来，且不违反错排的规则。

显然d[0] = x ! 。

如果此时我们把第 i 个有限制的位置加进来。分以下几种情况：

1）我们从 x 个无限制的的位置中找一个 j ，令a[i] = a[j]，a[j] = i。规约到d[i - 1]的方案数。

2）我们从i - 1个有限制的位置中找一个位置 j ，令a[i] = j，a[j] = i。规约到d[i - 2]的方案数。

3）我们从i - 1个有限制的位置中找一个位置 j ，令a[i] = j，但是a[j] != i。规约到d[i - 1]的方案数。也就相当于由原来的 d[j] != j 限制变为了d[j] != i，其它限制不变。

容斥的做法，就是枚举至少有多少个 i 使得a[i] = i，具体可以看ftiasch的代码。

PS：

这题对我来说还算是稍有意义。

因为这场比赛我的后一个半小时都在想这个。也没别的事好干。

这种感觉简直太可怕了。QAQ  若菜一把辛酸泪啊

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MOD = 1000000007;
const int MAXN = 2100;
int a[MAXN];
bool hash[MAXN];
long long d[MAXN];

int main()
{
    int n;
    scanf("%d", &n);
    memset(hash, 0, sizeof(hash));
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &a[i]);
        if(a[i] != -1)
        {
            hash[a[i]] = true;
        }
    }
    int x = 0, y = 0;
    for(int i = 0; i < n; i ++)
    {
        if(a[i] == -1)
        {
            if(hash[i + 1])
            {
                x ++;
            }
            else
            {
                y ++;
            }
        }
    }
    d[0] = 1;
    for(int i = 1; i <= x; i ++)
    {
        d[0] = d[0] * i % MOD;
    }
    for(int i = 1; i <= y; i ++)
    {
        d[i] = (x + i - 1) * d[i - 1] % MOD;
        if(i > 1)
        {
            d[i] = (d[i] + (i - 1) * d[i - 2]) % MOD;
        }
    }
    printf("%I64d\n", d[y]);
    return 0;
}