2012-A3-0002

从 Trac 迁移的文章

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

原文章内容如下：

题意:n元置换{A ,,i,,},满足m个A ,,bi,,!=c ,,i,, , 1<=b,,i,, , c,,i,,<=n, i=1..m,计算这样的置换的数量。

这题直接计算找不到突破口，由于是同时满足若干个否定性的条件，于是考虑用容斥原理进行计算。

用S,,i,,表示满足A,,bi,,!= c,,i,, ,~S,,i,,表示A,,bi,,==c,,i,,

由于同时满足若干组~S,,i,,的数量很好求，于是考虑容斥原理的形式应往这个方向靠。

|AND(S,,i,,)| = |全集|-|OR(~S,,i,,)| = |全集| - |~S,,i,, , Choose 1| + |AND(~S,,i,,,Choose 2)| - ... + (-1)^k^|AND(~S,,i,,,Choose k)| + ...

然后就dfs枚举~S,,i,,的交集合，利用容斥计算。

题目中有条件重复的trick，需要去重再处理，否则会使+-选取错误而导致wa


{{{
#include<cstdio>
typedef unsigned num;
typedef unsigned long long ull;
#define count __builtin_popcountll
const num mo = 55566677;

num d[32],r[32],x[64],n,m,ans;

void dfs(num k,ull day,ull rd){
    if(count(day)!=count(rd))return;
    if(k<m){
        if(!(1ull<<d[k] & day) && !(1ull<<r[k] & rd))
            dfs(k+1,day|1ull<<d[k],rd|1ull<<r[k]);
        dfs(k+1,day,rd);
    }else{
        if(count(rd)&1)
            ans += mo-x[n-count(rd)];
        else ans+=x[n-count(rd)];
        ans %=mo;
    }
}
int main(){
    for(num i=x[0]=1;i<=50;++i)x[i]=x[i-1]*i % mo;
    for(;2==scanf("%u%u",&n,&m);){
        for(num i=0;i<m;++i){
            scanf("%u%u",d+i,r+i);
            --d[i],--r[i];
        }
        for(num i=0,k=0;i<m;++i){
            for(num j=0;j<i;++j)
                if(d[i]==d[j]&&r[i]==r[j])goto xx;
            d[k]=d[i];r[k++]=r[i];
            xx:ans=k;
        }
        m=ans;ans=0;
        dfs(0,0llu,0llu);
        printf("%u\n",ans);
    }
}
}}}

题意:n元置换{A _i},满足m个A _bi!=c _i , 1<=b_i , c_i<=n, i=1..m,计算这样的置换的数量。

这题直接计算找不到突破口，由于是同时满足若干个否定性的条件，于是考虑用容斥原理进行计算。

用S_i表示满足A_bi!= c_i ,~S_i表示A_bi==c_i

由于同时满足若干组~S_i的数量很好求，于是考虑容斥原理的形式应往这个方向靠。

|AND(S_i)| = |全集|-|OR(~S_i)| = |全集| - |~S_i , Choose 1| + |AND(~S_i,Choose 2)| - ... + (-1)^k|AND(~S_i,Choose k)| + ...

然后就dfs枚举~S_i的交集合，利用容斥计算。

题目中有条件重复的trick，需要去重再处理，否则会使+-选取错误而导致wa

#include<cstdio>
typedef unsigned num;
typedef unsigned long long ull;
#define count __builtin_popcountll
const num mo = 55566677;
num d[32],r[32],x[64],n,m,ans;
void dfs(num k,ull day,ull rd){
    if(count(day)!=count(rd))return;
    if(k<m){
        if(!(1ull<<d[k] & day) && !(1ull<<r[k] & rd))
            dfs(k+1,day|1ull<<d[k],rd|1ull<<r[k]);
        dfs(k+1,day,rd);
    }else{
        if(count(rd)&1)
            ans += mo-x[n-count(rd)];
        else ans+=x[n-count(rd)];
        ans %=mo;
    }
}
int main(){
    for(num i=x[0]=1;i<=50;++i)x[i]=x[i-1]*i % mo;
    for(;2==scanf("%u%u",&n,&m);){
        for(num i=0;i<m;++i){
            scanf("%u%u",d+i,r+i);
            --d[i],--r[i];
        }
        for(num i=0,k=0;i<m;++i){
            for(num j=0;j<i;++j)
                if(d[i]==d[j]&&r[i]==r[j])goto xx;
            d[k]=d[i];r[k++]=r[i];
            xx:ans=k;
        }
        m=ans;ans=0;
        dfs(0,0llu,0llu);
        printf("%u\n",ans);
    }
}