[BZOJ1004](HNOI 2008) Cards
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。
【分析】
上个月学的群论终于派上用场了23333……
这题几乎就是一道等价类计数的练习题?注意到输入数据中黑体部分已经明确指出了输入数据中的所有置换恰好是一个完整的置换群(单位元是确定的,因此这里无需输入),那么根据Burnside引理,我们就有:等价类个数等于置换群中每个元素的“不动点”个数的平均值。其中“不动点”是指在置换$p$的作用下保持不变的排列种数。
那么,这道题中的“不动点”怎么求呢?根据置换的性质,我们可以将每种“洗牌法”分解成若干个不相交循环的乘积。对于一个排列,只要保证它在每个循环中的所有元素“颜色”都相同,就可以保证它在这种“洗牌法”下是一个“不动点”。于是,我们只要将每个置换分解成k个循环,记录下各个循环的长度$len_i$,就可以将问题转化为背包问题:“有3个背包,容量分别为Sr,Sb,Sg,将k件物品放入3个背包,第i件物品重量为$len_i$,求三个背包恰好放满的方案数”。
是不是毫无编码难度?→_→ 不过还要注意一点,我们上面的分析暂时没有考虑置换群中的单位元(即置换(1,2,...n)),只要再用可重集的全排列公式求出单位元的不动点个数,加上上面dp的结果后除以m + 1就好了。(读入的m个置换外加单位元)
最后不要忘了,上面所说的所有除法都是在模p剩余系$Z_p$中进行的,要用乘逆元来实现。
, c = getchar();
+ c - , y = ; , maxk = ;
};
] = ;
;i <= n;++i) fact[i] = fact[i-] * i % mod;
) ans += mod;
, mod, x, y);
? x + mod : x;
;
};
;i <= n;++i){
, cnt = , j = p[i];
; ++cnt;
;
][][] = ;
;i <= len;++i){
;j <= R;++j) ;k <= B;++k){
;
][j-loop[i]][k];
][j][k-loop[i]];
][j][k];
;i <= n;++i) getd(p[i]);
init();
work();
cout << endl << ( ;
}
Burnside引理+背包+可重集排列
最新文章
- Smart3D系列教程6之 《案例实战演练3——倾斜数据正射影像及DSM的生产》
- 中國區的代理協議的韓國遊戲廠商PatiGames
- JAVA-小青蛙跳石头游戏
- shell脚本常规技巧
- eclipse快捷键Alt + / 失效
- 支持向量机(SVM)算法
- 用c#开发微信 (17) 微活动 3 投票活动 (文本投票)
- lisener在web.xml中设置
- Jboss image upload and http access to show image--reference
- Oracle自带的exception
- linux访问windows共享文件夹
- thinkphp整合系列之phpexcel生成生成excel文件
- 一文搞懂各种 Docker 网络 - 每天5分钟玩转 Docker 容器技术(72)
- GMA Round 1 数列与方程
- git 安装配置
- oracle 11g中的自动维护任务管理
- 收藏:IPicture总结
- C#学习笔记(四):switch语句
- Maven 项目依赖 pom 文件模板
- 关于java 获取 html select标签 下拉框 option 文本内容 隐藏域
热门文章
- AlertDialog.Builder 显示为白色 蓝色字
- ShellCode的几种调用方法
- java===编译引用第三方文件的类(原创)
- python基础=== itertools介绍(转载)
- 用__builtin_return_address获得程序运行栈情况【转】
- clearcase command (linux 常用命令)
- 给mongodb设置密码权限
- PHP-5.6.22安装
- Spring学习(一)——Spring中的依赖注入简介
- 追忆似水流年sed