codeforces 340E Iahub and Permutations(错排or容斥)

转载请注明出处： http://www.cnblogs.com/fraud/           ——by fraud

Iahub and Permutations

Iahub is so happy about inventing bubble sort graphs that he's staying all day long at the office and writing permutations. Iahubina is angry that she is no more important for Iahub. When Iahub goes away, Iahubina comes to his office and sabotage his research work.

The girl finds an important permutation for the research. The permutation contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n). She replaces some of permutation elements with -1 value as a revenge.

When Iahub finds out his important permutation is broken, he tries to recover it. The only thing he remembers about the permutation is it didn't have any fixed point. A fixed point for a permutation is an element ak which has value equal to k (ak = k). Your job is to proof to Iahub that trying to recover it is not a good idea. Output the number of permutations which could be originally Iahub's important permutation, modulo 1000000007 (109 + 7).

Input

The first line contains integer n (2 ≤ n ≤ 2000). On the second line, there are n integers, representing Iahub's important permutation after Iahubina replaces some values with -1.

It's guaranteed that there are no fixed points in the given permutation. Also, the given sequence contains at least two numbers -1 and each positive number occurs in the sequence at most once. It's guaranteed that there is at least one suitable permutation.

Output

Output a single integer, the number of ways Iahub could recover his permutation, modulo 1000000007 (109 + 7).

Sample test(s)

input

5
-1 -1 4 3 -1

output

2

Note

For the first test example there are two permutations with no fixed points are [2, 5, 4, 3, 1] and [5, 1, 4, 3, 2]. Any other permutation would have at least one fixed point.

有一个序列，要求你将其中的-1换成1到n中的一个数，使得其成为1到n的一个排列，但要求第i为不得放i，问有几种替换的方法。

分析：

一个典型的错排问题，考虑到有部分数其本身的位置已被摆放，但其本身还没有用到，即这部分数是无限制的排列。

有一部分数是其本身的位置还是-1，但其本身已被使用，这些数的数目与上一种数必定是相同的，这类数已被放置，也无需考虑。

有一部分数是其本身的位置已被摆放，其本身也已被使用，故这类数不会对排列产生影响，也不必考虑。

剩下一部分数是其本身的位置还是-1，其本身也还未被用到，即这一部分的数是有限制的排列。

从而，我们只需要第一类数和第四类数。

假设摆放j个有限制排列的数时的方法为dp[j]，设总共有tx个无限制的数。

1.把一个有限制的数摆放到无限制的数所对应的tx个位置上时。。。仔细想想，这就相当于把一个无限制的数摆放到有限制的数的位置，则原来的那个有限制的数变成了无限制的数，即有限制的数减少了1，而无限制的数的数目不变，则有tx*dp[j-1]种。。

2.把一个有限制的数摆放到j-1个有限制的数位置上时，且a[i]=j,a[j]=i；则共有(j-1)*dp[j-2]。

3.把一个有限制的数摆放到j-1个个有限制的数位置上时，且a[i]=j,a[j]！=i；则共有(j-1)*dp[j-1]。

所以dp[j]=tx*dp[j-1]+(j-1)*dp[j-2]+(j-1)*dp[j-1];

然后，在把剩下的tx个摆好，就是tx的阶乘。

然后，就没然后了，就AC了。。。

======================

当然这道题也可以用容斥做，考虑a[i]==i的个数，总数去掉这些就是答案了。

//#####################
//Author:fraud
//Blog: http://www.cnblogs.com/fraud/
//#####################
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
const ll MOD =1000000007 ;
int a[10010];
ll b[2010];
bool vis[2010];
ll dp[2010];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    b[0]=1;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(ll i=1;i<2010;i++)b[i]=(b[i-1]*i)%MOD;
    int tx=0,ty=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){
            if(vis[i])tx++;
            else ty++;
        }
    }
    dp[0]=1;
    dp[1]=tx*dp[0]%MOD;
    for(int i=2;i<=ty;i++){
        dp[i]=(tx*dp[i-1]%MOD+(i-1)*dp[i-1]%MOD+(i-1)*dp[i-2]%MOD)%MOD;
    }
    cout<<dp[ty]*b[tx]%MOD<<endl;
    
    
    
        
            
    return 0;
}