prow2012-A3-0002

从 Trac 迁移的文章

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

原文章内容如下：

题意:n元置换{A i},满足m个A bi!=c i , 1<=bi , ci<=n, i=1..m,计算这样的置换的数量。(zYc学长那copy题意最省时间什么的>.<)

很容易想到的是1<<25的容斥，但是太大了，比赛时不敢写，没想到标程还真是……

枚举2进制取舍是完整的1<<25，用DFS进行取舍可以在发生冲突的第一时间return，

{{{
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
bool use[2][60];
int limit[60][2],N,M,MOD =55566677 ;
long long A[60],ans;
void dfs(int now,int k){
    if (now==M){
        if (k&1) ans-=A[N-k],ans%=MOD;
        else ans+=A[N-k],ans%=MOD;
        return ;
    }
    bool &one = use[0][limit[now][0]];
    bool &two = use[1][limit[now][1]];
    if (!one&&!two){
        one = two = true;
        dfs(now+1,k+1);
        one = two = false;
    }
    dfs(now+1,k);
}

int main(){
    A[0] = 1;
    int i,a,b,j;
    for (i=1;i<=50;i++)
        A[i] = A[i-1]*i,A[i]%=MOD;

    while(scanf("%d%d",&N,&M)!=EOF){
        ans = 0;
        memset(use,false,sizeof(use));
        int T = 0;
        for (i=0;i<M;i++){
            scanf("%d%d",&a,&b);
            a--,b--;
            for (j=0;j<i;j++)
                if (a==limit[j][0]&&b==limit[j][1])
                    break;
            if (j>=i)
            limit[T][0] = a,limit[T][1] = b,T++;
        }
        M = T;
        dfs(0,0);
        ans = (ans%MOD+MOD)%MOD;
        printf("%lld\n",ans);
    }
}

}}}

题意:n元置换{A i},满足m个A bi!=c i , 1<=bi , ci<=n, i=1..m,计算这样的置换的数量。(zYc学长那copy题意最省时间什么的>.<)

很容易想到的是1<<25的容斥，但是太大了，比赛时不敢写，没想到标程还真是……

枚举2进制取舍是完整的1<<25，用DFS进行取舍可以在发生冲突的第一时间return，

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
bool use[2][60];
int limit[60][2],N,M,MOD =55566677 ;
long long A[60],ans;
void dfs(int now,int k){
    if (now==M){
        if (k&1) ans-=A[N-k],ans%=MOD;
        else ans+=A[N-k],ans%=MOD;
        return ;
    }
    bool &one = use[0][limit[now][0]];
    bool &two = use[1][limit[now][1]];
    if (!one&&!two){
        one = two = true;
        dfs(now+1,k+1);
        one = two = false;
    }
    dfs(now+1,k);
}
int main(){
    A[0] = 1;
    int i,a,b,j;
    for (i=1;i<=50;i++)
        A[i] = A[i-1]*i,A[i]%=MOD;
    while(scanf("%d%d",&N,&M)!=EOF){
        ans = 0;
        memset(use,false,sizeof(use));
        int T = 0;
        for (i=0;i<M;i++){
            scanf("%d%d",&a,&b);
            a--,b--;
            for (j=0;j<i;j++)
                if (a==limit[j][0]&&b==limit[j][1])
                    break;
            if (j>=i)
            limit[T][0] = a,limit[T][1] = b,T++;
        }
        M = T;
        dfs(0,0);
        ans = (ans%MOD+MOD)%MOD;
        printf("%lld\n",ans);
    }
}