Description
给你一个序列,和m种可以使用多次的置换,用3种颜色染色,求方案数%p.
Sol
Burnside定理+背包.
Burnside定理 \(N(G,\mathbb{C})=\frac {1}{\left | G \right |}\sum_{f\in G}\left |\mathbb{C}(f) \right |\)
\(\mathbb{C}\) 中非等价的着色数等于在 \(G\) 中的置换作用下保持不变的着色的平均数.《组合数学》
对于每一种置换 求出关于置换的一个有向圈(相当于一个连通块),这里有更好的算法,但是我没怎么想,反正范围小直接用的并查集暴力置换合并.
想让计算不定置换,就要将每个有向圈染成同样的颜色,然后用背包求出来.
注意,它可以不用任何一种置换,所以要加上单位元的置换,这个可以直接用组合数学求出来,逆元随便搞搞就可以了.
Code
/**************************************************************
Problem: 1004
User: BeiYu
Language: C++
Result: Accepted
Time:260 ms
Memory:2368 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int N = 65; int n,m,sr,sb,sg,Mo,cnt,ans;
int a[N],tmp[N],sz[N],id[N];
int f[N][N][N],p[N]; inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
inline int Pow(int a,int b,int res=1){ for(;b;b>>=1,a=a*a%Mo) if(b&1) res=res*a%Mo;return res; } int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]); }
void Merge(int u,int v){
int f1=Find(u),f2=Find(v);
if(f1!=f2) p[f2]=f1;
}
int work(){
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=n;i++) a[i]=in();
for(int i=1;i<=n;i++){
for(int i=1;i<=n;i++) Merge(i,a[i]);
for(int i=1;i<=n;i++) tmp[i]=a[a[i]];
for(int i=1;i<=n;i++) a[i]=tmp[i];
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
}
cnt=0;
memset(sz,0,sizeof(sz));memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) if(p[i]==i) id[i]=++cnt;
for(int i=1;i<=n;i++) sz[id[Find(i)]]++;
f[0][0][0]=1;
for(int u=1;u<=cnt;u++){
for(int i=sr;~i;i--) for(int j=sb;~j;j--) for(int k=sg;~k;k--){
if(i>=sz[u]) f[i][j][k]=(f[i][j][k]+f[i-sz[u]][j][k])%Mo;
if(j>=sz[u]) f[i][j][k]=(f[i][j][k]+f[i][j-sz[u]][k])%Mo;
if(k>=sz[u]) f[i][j][k]=(f[i][j][k]+f[i][j][k-sz[u]])%Mo;
}
}return f[sr][sb][sg];
}
int main(){
// freopen("in.in","r",stdin);
sr=in(),sb=in(),sg=in(),m=in(),Mo=in(),n=sr+sb+sg; ans=1;
for(int i=1;i<=n;i++) ans=(ans*i)%Mo;
for(int i=1;i<=sr;i++) ans=(ans*Pow(i,Mo-2))%Mo;
for(int i=1;i<=sb;i++) ans=(ans*Pow(i,Mo-2))%Mo;
for(int i=1;i<=sg;i++) ans=(ans*Pow(i,Mo-2))%Mo; for(int i=1;i<=m;i++) ans=(ans+work())%Mo;
cout<<ans*Pow(m+1,Mo-2)%Mo<<endl;
return 0;
}