BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp…
2018-07-12 07:32:41来源:博客园 阅读 ()
Submit: 4255 Solved: 2582
[Submit][Status][Discuss]
Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有
多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方
案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.
两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗
成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
Input
第一行输入 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种洗牌法中的一种代
替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。
Output
不同染法除以P的余数
Sample Input
2 3 1
3 1 2
Sample Output
HINT
有2 种本质上不同的染色法RGB 和RBG,使用洗牌法231 一次可得GBR 和BGR,使用洗牌法312 一次 可得BRG
和GRB。
100%数据满足 Max{Sr,Sb,Sg}<=20。
Source
这题非常的妙啊。
第一眼看过去应该是P♂lya定理,但是考虑到P♂lya定理是用颜色数做底数计算的,而此题有颜色数的限制,
所以我们考虑它最原始的版本—Burnside引理
这题置换的个数直接给出了($M$)
因此我们只需要求出每个置换中不动点的方案再乘上$M$Z在模$P$意义下的逆元就行了
考虑如何求每个置换中的不动点
联想P♂lya定理。我们在每个循环节中都必须要放同样的颜色,这题也是一样的,只不过多了个数的限制
那么我们直接把个数的限制当做状态dp就行了
设$f[i][a][b]$表示前$i$个循环节,用了$a$个红颜色,$b$个蓝颜色,$c$个黄颜色
转移的时候判断当前放的个数时候大于循环节长度,背包转移
注意最初的状态也算一种方案
#include<cstdio> #include<algorithm> #include<cstring> #define LL long long const int MAXN = 1e5 + 10; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int Sr, Sb, Sg, N, M, mod, change[MAXN]; int f[61][21][21], len[101], vis[101], num = 0; // f[i][j][k]前i个循环节,用了j个红,k个蓝, i - j - k个绿 len[i]第i个循环节有几个元素 int F(int *a) { memset(f, 0, sizeof(f)); memset(len, 0, sizeof(len)); memset(vis, 0, sizeof(vis)); num = 0; for(int i = 1; i <= N; i++) { if(!vis[i]) { int cur = i; num++; while(!vis[i]) len[num]++, vis[i] = 1, i = a[i]; } } f[0][0][0] = 1; for(int i = 1; i <= num; i++) { for(int a = 0; a <= Sr; a++) { for(int b = 0; b <= Sb; b++) { int c = i - a - b, sum = 0; if(c < 0 || c > Sg) continue; if(a >= len[i]) sum = (sum + f[i - 1][a - len[i]][b] ) % mod; if(b >= len[i]) sum = (sum + f[i - 1][a][b - len[i]] ) % mod; if(c >= len[i]) sum = (sum + f[i - 1][a][b]) % mod; f[i][a][b] = sum % mod; } } } return f[num][Sr][Sb] % mod; } int inv(int a, int p, int mod) { int base = 1; while(p) { if(p & 1) base = (base * a) % mod; a = (a * a) % mod; p >>= 1; } return base % mod; } main() { Sr = read(); Sb = read(); Sg = read(); M = read(), mod = read(); N = Sr + Sb + Sg; int ans = 0; for(int i = 1; i <= M; i++) { for(int j = 1; j <= N; j++) change[j] = read(); ans += F(change); } for(int i = 1; i <= N; i++) change[i] = i; ans += F(change); printf("%d", ans * inv(M + 1, mod - 2, mod) % mod); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
- 斜率优化dp学习笔记 洛谷P3915[HNOI2008]玩具装箱toy 2019-08-16
- BZOJ1008: [HNOI2008]越狱(组合数) 2018-07-11
- bzoj1008 [HNOI2008]越狱 2018-06-17
- bzoj1009 [ HNOI2008 ] -- KMP+矩阵乘法加速DP 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash