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

时间:2022-05-18 09:03:21

题目描述

用三种颜色染一个长度为 $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的更多相关文章

  1. BZOJ1004&colon; &lbrack;HNOI2008&rsqb;Cards&lpar;Burnside引理 背包dp&rpar;

    Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4255  Solved: 2582[Submit][Status][Discuss] Descript ...

  2. bzoj1004 &lbrack;HNOI2008&rsqb;Cards Burnside 引理&plus;背包

    题目传送门 https://lydsy.com/JudgeOnline/problem.php?id=1004 题解 直接 Burnside 引理就可以了. 要计算不动点的个数,那么对于一个长度为 \ ...

  3. bzoj1004&colon; &lbrack;HNOI2008&rsqb;Cards&lpar;burnside引理&plus;DP&rpar;

    题目大意:3种颜色,每种染si个,有m个置换,求所有本质不同的染色方案数. 置换群的burnside引理,还有个Pólya过几天再看看... burnside引理:有m个置换k种颜色,所有本质不同的染 ...

  4. BZOJ1004 HNOI2008 Cards Burnside、背包

    传送门 在没做这道题之前天真的我以为\(Polya\)可以完全替代\(Burnside\) 考虑\(Burnside\)引理,它要求的是对于置换群中的每一种置换的不动点的数量. 既然是不动点,那么对于 ...

  5. bzoj1004 &lbrack;HNOI2008&rsqb;Cards Burnside定理&plus;背包

    题目传送门 思路:首先是Burnside引理,要先学会这个博客. Burnside引理我们总结一下,就是 每种置换下不动点的数量之和除以置换的总数,得到染色方案的数量.        这道题,显然每种 ...

  6. 【BZOJ1004】【HNOI2008】Cards 群论 置换 burnside引理 背包DP

    题目描述 有\(n\)张卡牌,要求你给这些卡牌染上RGB三种颜色,\(r\)张红色,\(g\)张绿色,\(b\)张蓝色. 还有\(m\)种洗牌方法,每种洗牌方法是一种置换.保证任意多次洗牌都可用这\( ...

  7. BZOJ 1004&colon; &lbrack;HNOI2008&rsqb;Cards&lpar; 置换群 &plus; burnside引理 &plus; 背包dp &plus; 乘法逆元 &rpar;

    题意保证了是一个置换群. 根据burnside引理, 答案为Σc(f) / (M+1). c(f)表示置换f的不动点数, 而题目限制了颜色的数量, 所以还得满足题目, 用背包dp来计算.dp(x,i, ...

  8. 【BZOJ1004】&lbrack;HNOI2008&rsqb;Cards Burnside引理

    [BZOJ1004][HNOI2008]Cards 题意:把$n$张牌染成$a,b,c$,3种颜色.其中颜色为$a,b,c$的牌的数量分别为$sa,sb,sc$.并且给出$m$个置换,保证这$m$个置 ...

  9. luogu P1446 &lbrack;HNOI2008&rsqb;Cards burnside引理 置换 不动点

    LINK:Cards 不太会burnside引理 而这道题则是一个应用. 首先 一个非常舒服的地方是这道题给出了m个本质不同的置换 然后带上单位置换就是m+1个置换. burnside引理: 其中D( ...

随机推荐

  1. SQL2008中Merge的用法

    在SQL2008中,新增了一个关键字:Merge,这个和Oracle的Merge的用法差不多,只是新增了一个delete方法而已.下面就是具体的使用说明: 首先是对merge的使用说明: merge ...

  2. recovery编译汉化

    当BoardConfig.mk中定义了recovery的字体且为中文字体时,自动编译为中文版,否则编译为英文版 例如: BOARD_USE_CUSTOM_RECOVERY_FONT := \&quot ...

  3. 与众不同 windows phone &lpar;14&rpar; - Media(媒体)之音频播放器&comma; 视频播放器&comma; 与 Windows Phone 的音乐和视频中心集成

    原文:与众不同 windows phone (14) - Media(媒体)之音频播放器, 视频播放器, 与 Windows Phone 的音乐和视频中心集成 [索引页][源码下载] 与众不同 win ...

  4. 关于解决Git项目本地修改代码之后执行pull操作之后报错的问题

    解决办法: 注意!该方法执行后会导致远程仓库覆盖本地仓库的文件,如果不需要对本地文件进行保存,可以无视,若之后还需要用到,请备份所报错文件! 1.Eclipse中选中项目右键-->Team--& ...

  5. &OpenCurlyDoubleQuote;挑三拣四”地学一学Java I&sol;O

    古人云:“读书破万卷,下笔如有神”.也就是说,只有大量的阅读,写作的时候才能风生水起——写作意味着输出(我的知识传播给他人),而读书意味着输入(从他人的知识中汲取营养). 对于Java I/O来说,I ...

  6. 安卓GridView奇偶行不同颜色

    背景:安卓制作表格,两列多行,奇数行和偶数行背景色不同 分析:GridView是经常用来制作表格的,但是和ListView不同,不能简单的用position % 2 == 0/1 来判断奇偶行,下面提 ...

  7. yolov3中 预测的bbox如何从特征图映射到原图?

    Anchor Box的边框 选取标准的k-means(欧式距离来衡量差异),在box的尺寸比较大的时候其误差也更大,而我们希望的是误差和box的尺寸没有太大关系.所以通过IOU定义了如下的距离函数,使 ...

  8. 菜鸟手下的iOS开发笔记&lpar;swift&rpar;

    在阳春4月的一天晨会上,有一个老板和蔼的对他的一个菜鸟手下说:“你既然会Android,那你能不能开发iOS?” 不是说好的要外包的吗?内心跌宕,但是表面淡定的菜鸟手下弱弱的回道:“可以试试”. 第二 ...

  9. 怎样编写YARN应用程序

    (注意:本文的分析基于Hadoop trunk上的"Revision 1452188"版本号,详细可參考:http://svn.apache.org/repos/asf/hadoo ...

  10. Logcat &plus; money 笔记

    如下命令:将过滤后的日志按照指定格式输出到指定的文件中 adb logcat -v time -s Test_Tag:v > logcat_local.txt A:其中 -v time 用来指定 ...