首页 > 代码库 > [BZOJ 1004][HNOI2008]Cards（Polya定理/Burnside引理）
[BZOJ 1004][HNOI2008]Cards（Polya定理/Burnside引理）
Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有
多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方
案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.
两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗
成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数)
Solution
Polya学习了一个
用背包来求每种置换的不动点数
（一开始忘记加不变的那种置换了…）
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int n,sr,sb,sg,m,p,a[65][65],b[65],f[25][25][25],ans=0;bool vis[65];void exgcd(int a,int b,int& d,int& x,int& y){ if(!b){d=a,x=1,y=0;return;} exgcd(b,a%b,d,y,x);y-=x*(a/b);}int inv(int a,int p){ int d,x,y; exgcd(a,p,d,x,y); return (x+p)%p;}int dp(int cnt){ memset(f,0,sizeof(f)); f[0][0][0]=1; for(int i=1;i<=cnt;i++) for(int j=sr;j>=0;j--) for(int k=sb;k>=0;k--) for(int l=sg;l>=0;l--) { f[j][k][l]=0; if(j>=b[i])f[j][k][l]=(f[j][k][l]+f[j-b[i]][k][l])%p; if(k>=b[i])f[j][k][l]=(f[j][k][l]+f[j][k-b[i]][l])%p; if(l>=b[i])f[j][k][l]=(f[j][k][l]+f[j][k][l-b[i]])%p; } return f[sr][sb][sg];}int main(){ scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p); n=sr+sb+sg; for(int i=1;i<=m+1;i++) { if(i!=m+1) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); else{ for(int j=1;j<=n;j++) a[i][j]=j; } memset(vis,0,sizeof(vis)); int cnt=0; for(int j=1;j<=n;j++) { if(!vis[j]) { vis[j]=1;b[++cnt]=1; int t=a[i][j]; while(t!=j) {vis[t]=1;b[cnt]++;t=a[i][t];} } } ans=(ans+dp(cnt))%p; } ans=(ans*inv(m+1,p))%p; printf("%d\n",ans); return 0;}
[BZOJ 1004][HNOI2008]Cards（Polya定理/Burnside引理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。