题目描述
用三种颜色染一个长度为 $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<100)。n=Sr+Sb+Sg。
接下来 m 行,每行描述一种洗牌法,每行有 n 个用空格隔开的整数 X1X2...Xn ,恰为 1 到 n 的一个排列,表示使用这种洗牌法,第 i 位变为原来的 Xi 位的牌。输入数据保证任意多次洗牌都可用这 m 种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。
输出
不同染法除以P的余数
样例输入
1 1 1 2 7
2 3 1
3 1 2
样例输出
2
题解
Burnside引理+背包dp
由于颜色有3种,因此不能直接使用Polya定理。
考虑Burnside引理推导Polya定理的过程:对于一种置换,不动点需要满足:每个循环种的颜色相同。
这种推导即可应用于本题。我们对于一个置换,取出其所有循环,这个循环需要 循环大小 个同种颜色。
显然是一个背包dp。设 $f[i][j][k]$ 表示前 $i$ 个置换,用了 $j$ 种颜色1和 $k$ 种颜色2的方案数(用了 $sum_i-j-k$ 种颜色3)。那么对于第 $i$ 个置换,讨论其颜色即可转移。
最终对于该置换的不动点数目即为 $f[k][Sr][Sb]$ ,$k$ 为循环数目。
把所有置换(包括置换后得到本身的置换 ${1,2,3,...,n\choose 1,2,3,...,n}$ )的不动点数目加起来,乘以 $m$ 的逆元即为答案。
时间复杂度 $O(mn^3)$
#include <cstdio>
#include <cstring>
int a , b , c , p , f[65][25][25] , v[65] , vis[65];
int solve()
{
int tot = 0 , sum = 0 , w , i , j , k;
memset(vis , 0 , sizeof(vis));
memset(f , 0 , sizeof(f));
f[0][0][0] = 1;
for(i = 1 ; i <= a + b + c ; i ++ )
{
if(!vis[i])
{
tot ++ ;
for(w = 0 , j = i ; !vis[j] ; j = v[j])
vis[j] = 1 , w ++ ;
sum += w;
for(j = 0 ; j <= a ; j ++ )
{
for(k = 0 ; k <= b ; k ++ )
{
if(sum - j - k <= c)
{
if(j >= w) f[tot][j][k] += f[tot - 1][j - w][k];
if(k >= w) f[tot][j][k] += f[tot - 1][j][k - w];
if(sum - j - k >= w) f[tot][j][k] += f[tot - 1][j][k];
f[tot][j][k] %= p;
}
}
}
}
}
return f[tot][a][b];
}
int main()
{
int m , i , j , ans = 0;
scanf("%d%d%d%d%d" , &a , &b , &c , &m , &p);
for(i = 1 ; i <= a + b + c ; i ++ ) v[i] = i;
ans = solve();
for(i = 1 ; i <= m ; i ++ )
{
for(j = 1 ; j <= a + b + c ; j ++ ) scanf("%d" , &v[j]);
ans = (ans + solve()) % p;
}
for(i = 1 ; i <= p - 2 ; i ++ ) ans = ans * (m + 1) % p;
printf("%d\n" , ans);
return 0;
}
我才不会告诉你们下面的代码也能过呢(数据太水了 = =)
#include <cstdio>
int p;
int pow(int x , int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = ans * x % p;
x = x * x % p , y >>= 1;
}
return ans;
}
int main()
{
int a , b , c , m , i , ans = 1;
scanf("%d%d%d%d%d" , &a , &b , &c , &m , &p);
for(i = 1 ; i <= a + b + c ; i ++ ) ans = ans * i % p;
for(i = 1 ; i <= a ; i ++ ) ans = ans * pow(i , p - 2) % p;
for(i = 1 ; i <= b ; i ++ ) ans = ans * pow(i , p - 2) % p;
for(i = 1 ; i <= c ; i ++ ) ans = ans * pow(i , p - 2) % p;
ans = ans * pow(m + 1 , p - 2) % p;
printf("%d\n" , ans);
return 0;
}
【bzoj1004】[HNOI2008]Cards Burnside引理+背包dp的更多相关文章
-
BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp)
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4255 Solved: 2582[Submit][Status][Discuss] Descript ...
-
bzoj1004 [HNOI2008]Cards Burnside 引理+背包
题目传送门 https://lydsy.com/JudgeOnline/problem.php?id=1004 题解 直接 Burnside 引理就可以了. 要计算不动点的个数,那么对于一个长度为 \ ...
-
bzoj1004: [HNOI2008]Cards(burnside引理+DP)
题目大意:3种颜色,每种染si个,有m个置换,求所有本质不同的染色方案数. 置换群的burnside引理,还有个Pólya过几天再看看... burnside引理:有m个置换k种颜色,所有本质不同的染 ...
-
BZOJ1004 HNOI2008 Cards Burnside、背包
传送门 在没做这道题之前天真的我以为\(Polya\)可以完全替代\(Burnside\) 考虑\(Burnside\)引理,它要求的是对于置换群中的每一种置换的不动点的数量. 既然是不动点,那么对于 ...
-
bzoj1004 [HNOI2008]Cards Burnside定理+背包
题目传送门 思路:首先是Burnside引理,要先学会这个博客. Burnside引理我们总结一下,就是 每种置换下不动点的数量之和除以置换的总数,得到染色方案的数量. 这道题,显然每种 ...
-
【BZOJ1004】【HNOI2008】Cards 群论 置换 burnside引理 背包DP
题目描述 有\(n\)张卡牌,要求你给这些卡牌染上RGB三种颜色,\(r\)张红色,\(g\)张绿色,\(b\)张蓝色. 还有\(m\)种洗牌方法,每种洗牌方法是一种置换.保证任意多次洗牌都可用这\( ...
-
BZOJ 1004: [HNOI2008]Cards( 置换群 + burnside引理 + 背包dp + 乘法逆元 )
题意保证了是一个置换群. 根据burnside引理, 答案为Σc(f) / (M+1). c(f)表示置换f的不动点数, 而题目限制了颜色的数量, 所以还得满足题目, 用背包dp来计算.dp(x,i, ...
-
【BZOJ1004】[HNOI2008]Cards Burnside引理
[BZOJ1004][HNOI2008]Cards 题意:把$n$张牌染成$a,b,c$,3种颜色.其中颜色为$a,b,c$的牌的数量分别为$sa,sb,sc$.并且给出$m$个置换,保证这$m$个置 ...
-
luogu P1446 [HNOI2008]Cards burnside引理 置换 不动点
LINK:Cards 不太会burnside引理 而这道题则是一个应用. 首先 一个非常舒服的地方是这道题给出了m个本质不同的置换 然后带上单位置换就是m+1个置换. burnside引理: 其中D( ...
随机推荐
-
SQL2008中Merge的用法
在SQL2008中,新增了一个关键字:Merge,这个和Oracle的Merge的用法差不多,只是新增了一个delete方法而已.下面就是具体的使用说明: 首先是对merge的使用说明: merge ...
-
recovery编译汉化
当BoardConfig.mk中定义了recovery的字体且为中文字体时,自动编译为中文版,否则编译为英文版 例如: BOARD_USE_CUSTOM_RECOVERY_FONT := \" ...
-
与众不同 windows phone (14) - Media(媒体)之音频播放器, 视频播放器, 与 Windows Phone 的音乐和视频中心集成
原文:与众不同 windows phone (14) - Media(媒体)之音频播放器, 视频播放器, 与 Windows Phone 的音乐和视频中心集成 [索引页][源码下载] 与众不同 win ...
-
关于解决Git项目本地修改代码之后执行pull操作之后报错的问题
解决办法: 注意!该方法执行后会导致远程仓库覆盖本地仓库的文件,如果不需要对本地文件进行保存,可以无视,若之后还需要用到,请备份所报错文件! 1.Eclipse中选中项目右键-->Team--& ...
-
“挑三拣四”地学一学Java I/O
古人云:“读书破万卷,下笔如有神”.也就是说,只有大量的阅读,写作的时候才能风生水起——写作意味着输出(我的知识传播给他人),而读书意味着输入(从他人的知识中汲取营养). 对于Java I/O来说,I ...
-
安卓GridView奇偶行不同颜色
背景:安卓制作表格,两列多行,奇数行和偶数行背景色不同 分析:GridView是经常用来制作表格的,但是和ListView不同,不能简单的用position % 2 == 0/1 来判断奇偶行,下面提 ...
-
yolov3中 预测的bbox如何从特征图映射到原图?
Anchor Box的边框 选取标准的k-means(欧式距离来衡量差异),在box的尺寸比较大的时候其误差也更大,而我们希望的是误差和box的尺寸没有太大关系.所以通过IOU定义了如下的距离函数,使 ...
-
菜鸟手下的iOS开发笔记(swift)
在阳春4月的一天晨会上,有一个老板和蔼的对他的一个菜鸟手下说:“你既然会Android,那你能不能开发iOS?” 不是说好的要外包的吗?内心跌宕,但是表面淡定的菜鸟手下弱弱的回道:“可以试试”. 第二 ...
-
怎样编写YARN应用程序
(注意:本文的分析基于Hadoop trunk上的"Revision 1452188"版本号,详细可參考:http://svn.apache.org/repos/asf/hadoo ...
-
Logcat + money 笔记
如下命令:将过滤后的日志按照指定格式输出到指定的文件中 adb logcat -v time -s Test_Tag:v > logcat_local.txt A:其中 -v time 用来指定 ...