team2012-E1-mysol-0002

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出 n 本书，要求每天恰好读完一本书，求读书顺序的方案总数
但是有 m 个特殊条件：在第 D[i] 天里无法读完第 C[i] 本书

我的做法是枚举这 m 条特殊条件中，违反了其中的哪些特殊条件
这么做其实就是用了容斥原理和德摩根定律：
不违反条件_1 and 不违反条件_2 and ... and 不违反条件_n
  = not (违反条件_1 or 违反条件_2 or ... or 违反条件_n)
  = 无条件的方案数 - count(违反 1 个条件的) + count(违反 2 个条件的)
  - ... + (-1) ^ n * count(违反 n 个条件的)

枚举时我用的暴力枚举的方式，对 2 ^ m 种可能的条件组合的都进行枚举
如果这种组合是可以出现的（不相互冲突），则参与计算
我在暴力枚举时用了一点小的代码技巧，使得不需要多出额外的 O(n) 时间
具体方法难以简单地描述清楚，大家可以看我的代码

用 dfs 来做的话会更快，因为有许多无效状态在 dfs 时可以被提前剪掉

// By 猛犸也钻地 @ 2012.07.18 */
}}}

{{{
#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 55566677;

int main(){
    int n,m,P[51]={1},x[25],y[25];
    for(long long i=1;i<51;i++) P[i]=P[i-1]*i%MOD;
    while(scanf("%d%d",&n,&m)==2){
        int day[50]={},use[50]={};
        for(int i=0,j;i<m;i++){
            scanf("%d%d",x+i,y+i);
            x[i]--,y[i]--;
            for(j=0;j<i;j++) if(x[i]==x[j] && y[i]==y[j]) break;
            if(j<i) i--,m--;
        }
        int mask=(1<<m)-1,s=0,cnt=0,err=0,ans=P[n];
        for(int r=1;r<=mask;r++){
            int i=__builtin_ctz(r);
            s^=1<<i;
            if(1<<i&s){
                cnt++;
                if(day[x[i]]++) err++;
                if(use[y[i]]++) err++;
            }else{
                cnt--;
                if(--day[x[i]]) err--;
                if(--use[y[i]]) err--;
            }
            if(!err) ans=(ans+(cnt&1?MOD-P[n-cnt]:P[n-cnt]))%MOD;
        }
        printf("%d\n",ans);
    }
}
}}}

/* 解题报告 //
给出 n 本书，要求每天恰好读完一本书，求读书顺序的方案总数
但是有 m 个特殊条件：在第 D[i] 天里无法读完第 C[i] 本书
我的做法是枚举这 m 条特殊条件中，违反了其中的哪些特殊条件
这么做其实就是用了容斥原理和德摩根定律：
不违反条件_1 and 不违反条件_2 and ... and 不违反条件_n
  = not (违反条件_1 or 违反条件_2 or ... or 违反条件_n)
  = 无条件的方案数 - count(违反 1 个条件的) + count(违反 2 个条件的)
  - ... + (-1) ^ n * count(违反 n 个条件的)
枚举时我用的暴力枚举的方式，对 2 ^ m 种可能的条件组合的都进行枚举
如果这种组合是可以出现的（不相互冲突），则参与计算
我在暴力枚举时用了一点小的代码技巧，使得不需要多出额外的 O(n) 时间
具体方法难以简单地描述清楚，大家可以看我的代码
用 dfs 来做的话会更快，因为有许多无效状态在 dfs 时可以被提前剪掉
// By 猛犸也钻地 @ 2012.07.18 */

#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD = 55566677;
int main(){
    int n,m,P[51]={1},x[25],y[25];
    for(long long i=1;i<51;i++) P[i]=P[i-1]*i%MOD;
    while(scanf("%d%d",&n,&m)==2){
        int day[50]={},use[50]={};
        for(int i=0,j;i<m;i++){
            scanf("%d%d",x+i,y+i);
            x[i]--,y[i]--;
            for(j=0;j<i;j++) if(x[i]==x[j] && y[i]==y[j]) break;
            if(j<i) i--,m--;
        }
        int mask=(1<<m)-1,s=0,cnt=0,err=0,ans=P[n];
        for(int r=1;r<=mask;r++){
            int i=__builtin_ctz(r);
            s^=1<<i;
            if(1<<i&s){
                cnt++;
                if(day[x[i]]++) err++;
                if(use[y[i]]++) err++;
            }else{
                cnt--;
                if(--day[x[i]]) err--;
                if(--use[y[i]]) err--;
            }
            if(!err) ans=(ans+(cnt&1?MOD-P[n-cnt]:P[n-cnt]))%MOD;
        }
        printf("%d\n",ans);
    }
}