bzoj1004:[HNOI2008]Cards

思路:由于题目给出了置换,又要求本质不同的方案数,考虑使用Burnside引理,Burnside引理即通过所有置换和原来相同的方案数之和除以方案数总数,而对于某一个置换要使置换后得到的与原来的相同,就应该把置换形成的环染成同一种颜色,也就是说属于一个环内的元素颜色一定相同,然后有一定要有一定量的红蓝绿色,因此用一个完全背包去背即可,

f[i][j][k]表示选了i张红色j张蓝色k张绿色的方案数,f[i][j][k]=f[i][j][k]+f[i-sum][j][k]+f[i][j-sum][k]+f[i][j][k-sum](sum表示当前环大小,然后i,j,k一定要判是不是大于sum),最后还有就是任何时候都不要忘了不动也是一个置换,因此有m+1个置换。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define maxn 65
 8
 9 int sr,sg,sb,m,p,n,ans,tot;
10 int a[maxn],next[maxn],vis[maxn],f[21][21][21],sum[maxn];
11
12 int calc(){
13     for (int i=1;i<=n;i++) next[i]=a[i];tot=0,memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f)),memset(sum,0,sizeof(sum));
14     for (int i=1;i<=n;i++) if (!vis[i]){
15         int size=0;
16         while (!vis[i]) vis[i]=1,size++,i=next[i];
17         sum[++tot]=size;
18     }
19     f[0][0][0]=1;
20     for (int i=1;i<=tot;i++)
21         for (int j=sr;j>=0;j--)
22             for (int k=sg;k>=0;k--)
23                 for (int l=sb;l>=0;l--){
24                     if (j>=sum[i]) f[j][k][l]=(f[j][k][l]+f[j-sum[i]][k][l])%p;
25                     if (k>=sum[i]) f[j][k][l]=(f[j][k][l]+f[j][k-sum[i]][l])%p;
26                     if (l>=sum[i]) f[j][k][l]=(f[j][k][l]+f[j][k][l-sum[i]])%p;
27                 }
28     return f[sr][sg][sb];
29 }
30
31 int power(int a,int k,int p){
32     if (k==0) return 1;
33     if (k==1) return a%p;
34     int x=power(a,k/2,p),ans=x*x%p;
35     if (k&1) ans=ans*a%p;
36     return ans;
37 }
38
39 int main(){
40     scanf("%d%d%d%d%d",&sr,&sg,&sb,&m,&p),n=sr+sg+sb;
41     for (int i=1;i<=n;i++) a[i]=i;ans=(ans+calc())%p;
42     for (int i=1;i<=m;i++){
43         for (int j=1;j<=n;j++)
44             scanf("%d",&a[j]);
45         ans=(ans+calc())%p;
46     }
47     ans=ans*power(m+1,p-2,p)%p;
48     printf("%d\n",ans);
49     return 0;
50 }

然后听说这道题有一个玄学写法,答案就是n!/(Sr!*Sg!*Sb!*(m+1)),然而蒟蒻并不知道这是为什么。。。。。神犇求教。。。

时间: 10-12

bzoj1004:[HNOI2008]Cards的相关文章

【BZOJ1004】[HNOI2008]Cards Burnside引理

[BZOJ1004][HNOI2008]Cards 题意:把$n$张牌染成$a,b,c$,3种颜色.其中颜色为$a,b,c$的牌的数量分别为$sa,sb,sc$.并且给出$m$个置换,保证这$m$个置换加上本身的置换能构成一个置换群,两种染色方案被认为是相同的当且仅当一种方案可以通过某个置换变成另一种.求不同的染色方案数.答案对$P$取模. $sa,sb,sc\le 20,m\le 60$ 题解:这里对每种颜色都有一个限制,怎么办呢? 回顾从Burnside引理到Pólya定理的推导过程. 如果

【bzoj1004】[HNOI2008]Cards

1004: [HNOI2008]Cards Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2928  Solved: 1754[Submit][Status][Discuss] Description 小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出

【bzoj1004】 HNOI2008—Cards

http://www.lydsy.com/JudgeOnline/problem.php?id=1004 (题目链接) 题意 n张卡片,染成3种颜色,每种颜色只能染固定张数.给出一些洗牌方案,问染色方案数. Solution Burnside引理. 左转题解:LCF 代码 // bzoj1004 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #includ

【bzoj1004】[HNOI2008]Cards Burnside引理+背包dp

题目描述 用三种颜色染一个长度为 $n=Sr+Sb+Sg$ 序列,要求三种颜色分别有 $Sr,Sb,Sg$ 个.给出 $m$ 个置换,保证这 $m$ 个置换和置换 ${1,2,3,...,n\choose 1,2,3,...,n}$ 构成一个置换群,求置换后不同构的序列个数模 $p$ . $0\le Sr,Sb,Sg\le 20,0\le m\le 60,m+1\le p\le 100$ ,$p$ 是质数. 输入 第一行输入 5 个整数:Sr,Sb,Sg,m,p(m<=60,m+1<p<

BZOJ 1004: [HNOI2008]Cards Polya计数+DP

Polya计数+dp求满足对应循环的不动点有几个 1004: [HNOI2008]Cards Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2046  Solved: 1212 [Submit][Status][Discuss] Description 小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,S

bzoj 1004 1004: [HNOI2008]Cards burnside定理

1004: [HNOI2008]Cards Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1668  Solved: 978[Submit][Status] Description 小 春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答 案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最

[HNOI2008]Cards

1004: [HNOI2008]Cards Time Limit: 10 Sec  Memory Limit: 162 MB[Submit][Status][Discuss] Description 小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他

luogu P1446 [HNOI2008]Cards

题目链接 luogu P1446 [HNOI2008]Cards 题解 题意就是求染色方案->等价类 洗牌方式构成成了一个置换群 然而,染色数限制不能用polay定理直接求解 考虑burnside引理 对于一个置换群其等价类的个数为置换中不动点的平均数 先暴力求出置换中的轮换,然后01背包DP求出不动点方案数 代码 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm

BZOJ1004 [HNOI2008]Cards

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/转载请注明出处,侵权必究,保留最终解释权! 题目链接:BZOJ1004 正解:$Burnside$引理 解题报告: 经典$Burnside$引理题. 考虑一般的$Burnside$引理题都是直接求出一阶循环的个数,然后对于置换个数取平均数. 但是有颜色限制,所以我们不能直接算. 而因为一个洗牌方案相