BZOJ1004 [HNOI2008]Cards

Published on 2017 Jul 12 09:13:56
Last Updated on 2017 Jul 15 17:33:34

传送门
1W 1A
刷第一页题目……
注意题目中 输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替
QAQ第一次读题被坑了好久。。。
还有p是质数QAQ
一看就是Burnside…群论入门教程 ←这篇是写得比较好的
可以用背包解决对于一种置换的计数问题
可以理解为三个背包,容量为Sr、Sb、Sg,把每个循环节看成一个体积为循环节长度的物体,最终要三个背包恰好装满,求方案数
最后求平均数的除法要用乘法逆元解决,直接快速幂/exgcd
记得置换里有一个“不变”,要加进去
代码里应用了一些邪恶的define技巧

#include <bits/stdc++.h>
#define F(b) for(int k##b=s##b;k##b>=0;--k##b)
using namespace std;
int dp[66][66][66],trans[233][66];
int sr,sg,sb,n,m,p;
int vis[66];
inline void add(int& a,int b){
    if((a+=b)>=p) a-=p;
}
int getcnt(int* tr){
    memset(vis,0,sizeof vis);
    memset(dp,0,sizeof dp);
    dp[0][0][0]=1;
    int cnt;
    for(int i=1;i<=n;i++) if(!vis[i]){
        int x=0,p=i;
        ++cnt;
        do ++x,vis[p=tr[p]]=1; while(p!=i);
        F(r)F(g)F(b){
            int& nd=dp[kr][kg][kb];
            if(kr>=x) add(nd,dp[kr-x][kg][kb]);
            if(kg>=x) add(nd,dp[kr][kg-x][kb]);
            if(kb>=x) add(nd,dp[kr][kg][kb-x]);
        }
    }
    return dp[sr][sg][sb];
}
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1,a=(a*a)%p) if(b&1) c=(c*a)%p;
    return c;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>sr>>sb>>sg>>m>>p;
    n=sr+sb+sg;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>trans[i][j];
    ++m;
    for(int i=1;i<=n;i++) trans[m][i]=i;
    int ans=0;
    for(int i=1;i<=m;i++) add(ans,getcnt(trans[i]));
    printf("%d",(ans*qpow(m,p-2))%p);
}