1004: [HNOI2008]Cards burnside定理

https://www.lydsy.com/JudgeOnline/problem.php?id=1004

输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。（保证置换的完备性）

要考虑1，2，3.。。n这个置换，然后算出每种置换的方案数，除上总置换数m+1，就是答案，因为有取模，所以需要算逆元，然后对与一种置换来说总的情况数可以用dp来计算，因为每一个置换群只能涂成一种颜色，然后我们需要满足涂的颜色种数满足条件，dp[i][j][k]维护当红i个，蓝j个，绿k个的总方案数，最后全部加到答案中乘上逆元即可

/**************************************************************

    Problem: 1004

    User: walfy

    Language: C++

    Result: Accepted

    Time:932 ms

    Memory:3992 kb

****************************************************************/

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

ll quick(ll a,ll b,ll c)

{

    ll ans=;

    while(b)

    {

        if(b & ) ans=ans*a%c;

        a=a*a%c;

        b>>=;

    }

    return ans;

}

int d[N][N],num[N],dp[][N][N][N];

bool vis[N];

int main()

{

    int a,b,c,n,m,p;

    scanf("%d%d%d%d%d",&a,&b,&c,&m,&p);

    n=a+b+c;

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&d[i][j]);

    for(int i=;i<=n;i++)d[m+][i]=i;

    m++;

    ll ans=;

    for(int i=;i<=m;i++)

    {

        int cnt=;

        memset(num,,sizeof num);

        memset(vis,,sizeof vis);

        for(int j=;j<=n;j++)

        {

            if(!vis[j])

            {

                num[++cnt]=;

                vis[j]=;

                int now=d[i][j];

                while(now!=j)

                {

                    vis[now]=;

                    now=d[i][now];

                    num[cnt]++;

                }

            }

        }

        int now=,pre=;

        dp[now][][][]=;

        for(int j=;j<=cnt;j++)

        {

            swap(now,pre);

            memset(dp[now],,sizeof dp[now]);

            for(int x=;x<=a;x++)for(int y=;y<=b;y++)for(int z=;z<=c;z++)

            {

                if(x>=num[j])dp[now][x][y][z]=(dp[now][x][y][z]+dp[pre][x-num[j]][y][z])%p;

                if(y>=num[j])dp[now][x][y][z]=(dp[now][x][y][z]+dp[pre][x][y-num[j]][z])%p;

                if(z>=num[j])dp[now][x][y][z]=(dp[now][x][y][z]+dp[pre][x][y][z-num[j]])%p;

            }

        }

        ans=(ans+dp[now][a][b][c])%p;

    }

    ans=ans*quick(m,p-,p)%p;

    printf("%lld\n",ans);

    return ;

}

/***********************

***********************/