首页 > 代码库 > BZOJ 1004 HNOI2008 Cards Burnside引理
BZOJ 1004 HNOI2008 Cards Burnside引理
题目大意:给定n张卡牌和m个置换,求等价类个数
数据保证这m个置换加上自身置换后构成一个置换群
BZOJ坑爹0.0 这么重要的条件不给出来尼玛怎么做
Burnside引理……昨晚为了做这题硬啃了一晚上白书0.0 都快啃吐了0.0
Burnside引理:一个置换群下的等价类个数等于所有置换的不动点个数的平均值
没有接触过群论的建议去啃白书…… 网上的东西看不懂的
最后那个除法要用乘法逆元 我懒得写EXGCD写了费马小定理0.0
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 70 using namespace std; int r,g,b,m,n,p,ans; int a[M],stack[M],top; int f[21][21][21]; void DFS(int x) { stack[top]++; int temp=a[x]; a[x]=0; if(a[temp]) DFS(temp); } int DP() { int i,j,k; memset(f,0,sizeof f);f[0][0][0]=1; while(top) { for(i=r;~i;i--) for(j=g;~j;j--) for(k=b;~k;k--) { if(i>=stack[top]) f[i][j][k]+=f[i-stack[top]][j][k]; if(j>=stack[top]) f[i][j][k]+=f[i][j-stack[top]][k]; if(k>=stack[top]) f[i][j][k]+=f[i][j][k-stack[top]]; f[i][j][k]%=p; } stack[top--]=0; } return f[r][g][b]; } int KSM(int x,int y) { int re=1; while(y) { if(y&1)re*=x,re%=p; x*=x,x%=p; y>>=1; } return re; } int main() { int i,j; cin>>r>>g>>b>>m>>p; n=r+g+b; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) scanf("%d",&a[j]); for(j=1;j<=n;j++) if(a[j]) ++top,DFS(j); ans+=DP(),ans%=p; } for(j=1;j<=n;j++) a[j]=j; for(j=1;j<=n;j++) if(a[j]) ++top,DFS(j); ans+=DP(),ans%=p; ans*=KSM(m+1,p-2),ans%=p; cout<<ans<<endl; }
BZOJ 1004 HNOI2008 Cards Burnside引理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。