ZOJ-3687 The Review Plan I(容斥原理，禁位排列，dfs)

小咪咪 2022-06-10 12:06 141阅读 0赞

The Review Plan I

Michael takes the *Discrete Mathematics* course in this semester. Now it's close to the final exam, and he wants to take a complete review of this course.

The whole book he needs to review has N chapter, because of the knowledge system of the course is kinds of discrete as its name, and due to his perfectionism, he wants to arrange exactly N days to take his review, and one chapter by each day.

But at the same time, he has other courses to review and he also has to take time to hang out with his girlfriend or do some other things. So the free time he has in each day is different, he can not finish a big chapter in some particular busy days.

To make his perfect review plan, he needs you to help him.

Input

There are multiple test cases. For each test case:

The first line contains two integers N(1≤N≤50), M(0≤M≤25), N is the number of the days and also the number of the chapters in the book.

Then followed by M lines. Each line contains two integers D(1≤D≤N) andC(1≤C≤N), means at the Dth day he can not finish the review of the Cth chapter.

There is a blank line between every two cases.

Process to the end of input.

Output

One line for each case. The number of the different appropriate plans module 55566677.

Sample Input

4 3
    1 2
    4 3
    2 1
    
    6 5
    1 1
    2 6
    3 5
    4 4
    3 4

Sample Output

11
    284

题意：一本书有N个章节，给你M个限制，在第Di天不能读第Ci章节，问你有多少种方法在这N天读完N个章节。

思路：典型的禁位排列，关于禁位排列张坤龙的组合数学里有很详细的解释

传送门→https://wenku.baidu.com/view/98e0aab9fd0a79563c1e7220.html

这道题我们要用到下面这个定理

![Center][]

在这道题里，ri我们可以通过dfs来求，把每一种情况都遍历一遍。AC代码如下：

#include<iostream>
    #include<cstdio>
    #include<string.h>
    #include<math.h>
    using namespace std;
    typedef long long LL;
    #define MOD 55566677
    #define N 55
    LL f[N],res;
    int n,m,vis1[N],vis2[N],a[N][N],ban[N][N];
    void inint()
    {
        f[0]=1;
        for(int i=1; i<N; i++)
            f[i]=(f[i-1]*i)%MOD;
    }
    void dfs(int i,int num)  //第i个禁位，选num个禁位
    {
        if(i>m)
        {
            if(num&1) res=((res-f[n-num])%MOD+MOD)%MOD;
            else   res=(res+f[n-num])%MOD;
            return;
        }
        dfs(i+1,num);    //第i个禁位不选
        if((!vis1[a[i][0]])&&(!vis2[a[i][1]]))  //选第i个禁位
        {
            vis1[a[i][0]]=vis2[a[i][1]]=1;
            dfs(i+1,num+1);
            vis1[a[i][0]]=vis2[a[i][1]]=0;
        }
    }
    
    int main()
    {
        int i,j,d,c;
        inint();
        while(~scanf("%d%d",&n,&m))
        {
            memset(vis1,0,sizeof(vis1));
            memset(vis2,0,sizeof(vis2));
            memset(ban,0,sizeof(ban));
            for(i=1; i<=m; i++)
            {
                scanf("%d%d",&a[i][0],&a[i][1]);
                if(ban[a[i][0]][a[i][1]])
                {
                    i--;
                    m--;
                }
                else ban[a[i][0]][a[i][1]]=1;
            }
            res=0;
            dfs(1,0);
            res=(res%MOD+MOD)%MOD;
            printf("%lld\n",res);
        }
        return 0 ;
    }

[Center]: /images/20220610/bbfd5c0b23d649dfa14d5f69c7d5c68e.png