BZOJ1004 HNOI2008 Cards Burnside、背包

传送门

---

在没做这道题之前天真的我以为\(Polya\)可以完全替代\(Burnside\)

考虑\(Burnside\)引理，它要求的是对于置换群中的每一种置换的不动点的数量。

既然是不动点，那么对于这一个置换中的一个轮换，这个不动点中轮换里所有位置的颜色都必须相同。

然后题目就转化成了一个背包。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<iomanip>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<vector>

#include<cmath>

//This code is written by Itst

using namespace std;

inline int read(){

    int a = 0;

    char c = getchar();

    while(!isdigit(c))

        c = getchar();

    while(isdigit(c)){

        a = a * 10 + c - 48;

        c = getchar();

    }

    return a;

}

int dp[21][21][21] , cg[61];

int sr , sb , sg , N , M , P , sum;

bool vis[61];

inline int poww(int a , int b){

    int times = 1;

    while(b){

        if(b & 1)

            times = times * a % P;

        a = a * a % P;

        b >>= 1;

    }

    return times;

}

inline int calcLen(int x){

    int cnt = 0;

    while(!vis[x]){

        vis[x] = 1;

        x = cg[x];

        ++cnt;

    }

    return cnt;

}

inline void add(int& a , int b){

    a = a + b >= P ? a + b - P : a + b;

}

void calc(){

    memset(vis , 0 , sizeof(vis));

    memset(dp , 0 , sizeof(dp));

    dp[0][0][0] = 1;

    for(int i = 1 ; i <= N ; ++i)

        if(!vis[i]){

            int t = calcLen(i);

            for(int j = sr ; j >= 0 ; --j)

                for(int k = sb ; k >= 0 ; --k)

                    for(int l = sg ; l >= 0 ; --l){

                        if(j >= t)

                            add(dp[j][k][l] , dp[j - t][k][l]);

                        if(k >= t)

                            add(dp[j][k][l] , dp[j][k - t][l]);

                        if(l >= t)

                            add(dp[j][k][l] , dp[j][k][l - t]);

                    }

        }

    add(sum , dp[sr][sb][sg]);

}

signed main(){

#ifndef ONLINE_JUDGE

    //freopen("in" , "r" , stdin);

    //freopen("out" , "w" , stdout);

#endif

    sr = read();

    sb = read();

    sg = read();

    N = sr + sb + sg;

    M = read();

    P = read();

    for(int i = 1 ; i <= N ; ++i)

    	cg[i] = i;

    calc();

    for(int i = 1 ; i <= M ; ++i){

    	for(int j = 1 ; j <= N ; ++j)

    		cg[j] = read();

    	calc();

    }

    cout << sum * poww(M + 1 , P - 2) % P;

    return 0;

}