看心情填坑

我感觉ZJOIDAY1之后我就会忘记掉，存个档压压惊

看了很多博客，感觉还是这里讲得最好。

大suo部you分证明和定义因为本人比较弱就不赘述了，基本前面的链接里都有了。

以下的所有论述的前提是置换群里所有的置换组合都是置换群中的一个置换，简单来说对于任意\(a\in G\),\(b\in G\)都有\(a*b\in G\)，定义所有染色方案集合为C，置换群为G

两个染色方案相等的定义是\(c1*f=c2(f\in G)\)

直接从burnside定理开始吧。

这个定理因为我比较弱连定义都不知道，一开始完全没有看懂。还是看上面链接懂的，直接贴吧。

定义\(G(c)=\left \{ f|f\in G,f*c=c \right \} \)，有与c等价的着色方案数=\(|G|/|G(c)|\)

我看懂第一反应就是卧槽这不是显然的么根本原因是我不会证

然后是polya定理虽然我也不知道原来这个定理是什么能用就行了。我个人觉得最全面的说法是对于置换群G，染色方案c的等价染色方案数记为N(G,c)，定义\(C(f)=\left \{ c|c\in C,f*c=c \right \} \)

有\(N(G,c)*\left | G \right |=\sum_{f\in G} \left | C(f) \right |\)

假如说没有任何的限制，那么设颜色数为m,\(C(f)=m^{l[f]}\)l[f]表示置换f的循环节长度，即f中每个独立的部分长度的lcm。

假如说有限制，比如说要求颜色1染a个，颜色2染b个，那么根据定义，满足\(c*f=c\)的前提是每一个独立的部分中的颜色都相等。

然后dp就可以了。

最普通的版本就是直接背包上，进阶的可能还要用矩乘、递推、BALABALA来优化，具体因题而异。

#include<cstdio>
#include<cstring>
using namespace std;
int na,nb,nc,m,mo,n,top,ans;
int dp[21][21][21];
int a[61],w[61];
bool b[61];
inline int pow(int x,int k){
    int ans=1;
    for(;k;k>>=1,x=x*x%mo)if(k&1)ans=ans*x%mo;
    return ans;
}
void work(){
    top=0;
    memset(b,false,sizeof(b));
    for(int i=1;i<=n;i++)if(!b[i]){
        int k=i;
        top++;
        w[top]=0;
        while(!b[k]){
            b[k]=true;
            k=a[k];
            w[top]++;
        }
    }
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=top;i++)
        for(int j=na;j>=0;j--)
            for(int k=nb;k>=0;k--)
                for(int l=nc;l>=0;l--){
                    if(j>=w[i])dp[j][k][l]=(dp[j][k][l]+dp[j-w[i]][k][l])%mo;
                    if(k>=w[i])dp[j][k][l]=(dp[j][k][l]+dp[j][k-w[i]][l])%mo;
                    if(l>=w[i])dp[j][k][l]=(dp[j][k][l]+dp[j][k][l-w[i]])%mo;
                }
    ans=(ans+dp[na][nb][nc])%mo;
}
int main(){
    scanf("%d%d%d%d%d",&na,&nb,&nc,&m,&mo);
    n=na+nb+nc;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)scanf("%d",&a[j]);
        work();
    }
    for(int i=1;i<=n;i++)a[i]=i;
    work();
    printf("%d",ans*pow(m+1,mo-2)%mo);
}