首页 > 代码库 > hdu5822 color
hdu5822 color
首先考虑假如是树上的做法:
考虑dp,f(i)表示对i的子树染色的方案数。
用hash可以实现查询两棵子树是否相同。
从而根据hash值排序分类,将相同的子树放在一类. (1)
f(i)等于每一类的f(p)乘起来除以此类大小size的阶乘。(2)
从而O(nlogn)求出了环周围的树的答案
然后考虑用群论求环上的答案。
等价于有tot个珠子(环上的点),每个珠子有一个颜色(子树的形状),我们说旋转x格是此问题的置换群之一,***当且仅当旋转x格后各个珠子的颜色与相应位置的要求依然吻合***。(3)
求旋转那些格数之后可以吻合可以用KMP匹配判断。
旋转x格后的不动点个数为$$\prod_{i=1}^{(tot,i)} f[p(i)]$$
(因为当子树形状相同时,必然有对应f值相同)
预处理前缀乘积,用Bunside公式计算答案即可。
hdu5822 color
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。