容斥专题

容斥专题:容斥专题题集
复习了一下容斥,发现原来容斥可以用位运算写,以前一直使用dfs写的。。弱爆了。。
这两种做法各有适用的场合。
重新做了一下zoj3687
dfs版的容斥
题意:n天n个章节,给你m个约束条件,一个约束条件d,c表示第d天不能复习第c章节。问总共有多少种复习的方式(答案mod 55566677)。
思路:典型的容斥题目。算出满足所有约束的方案数,最后n!减一下即可。以前做的时候忘了约束会有重复,这次做又忘了。。真是渣渣。首先完全相同的约束只保留一个,否则会多算。然后,如果d或c有重复,则说明这两个约束条件同时满足的方案数为0,不能递归下去了。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll mod=55566677LL;
typedef struct Node{
    int d,c;
}Node;
Node node[30];
ll fact[55];
int n,m;
ll ans;
bool day[55],chap[55];
void init()
{
    memset(day,0,sizeof(day));
    memset(chap,0,sizeof(chap));
}
void dfs(int flag,int x)
{
    day[node[x].d]=1;chap[node[x].c]=1;
    if(flag&1) ans=(ans+fact[n-flag])%mod;
    else ans=(ans-fact[n-flag])%mod;
    for(int i=x+1;i<=m;i++)
    {
        if(day[node[i].d] || chap[node[i].c]) continue;
        dfs(flag+1,i);
    }
    day[node[x].d]=0;chap[node[x].c]=0;
}
int main()
{
    int i,j;
    fact[0]=1;
    for(i=1;i<=50;i++)
        fact[i]=(fact[i-1]*i)%mod;
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;init();
        int a,b,cnt=0;
        int map[55][55];
        memset(map,0,sizeof(map));
        for(i=1;i<=m;i++) {scanf("%d%d",&a,&b);map[a][b]=1;}
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(map[i][j])
                {
                    node[++cnt].d=i;node[cnt].c=j;
                }
        m=cnt;
        for(i=1;i<=m;i++) dfs(1,i);
        printf("%lld\n",((fact[n]-ans)%mod+mod)%mod);
    }
    return 0;
}

用位运算写的容斥
(待补充)