最终得对抗自己

[考试题] Color

题目大意

给一个N个节点无标号基环外向树, 有M种颜色, 问给这个基环外向树的每个节点染色, 可以染出来的本质不同基环外向树数量对998244353取模。
N≤1e5, M≤1e9

解题报告

我果然把置换群那一套忘完了…今天重温一遍。
首先找出基环, 把环上每棵树dp一遍搞出这棵树染色本质不同的方案数, 顺便把树的结构哈希出来(注意树哈希比较鬼畜…为了防重最好把深度和子树大小什么的一起哈希进去), 这样问题就转化为一个环, 每个点可以染dp[i]种颜色中的一种, 每个节点的特征码为hash[i], 问这个环在任意旋转置换下的本质不同染色方案数。
然后这就是经典的burnside+polya计数了, 考虑在旋转i次置换的循环节大小为N/gcd(i, N), 那么一共有gcd(i, N)个循环节, 循环之间互不干扰, 于是乘起来即可算出等价类数目, 最后除以置换群大小得到结果。

后记

最近一直使用linux, 学了一发gdb命令行调试, 简直爽歪歪, 对codeblocks强大调试功能产生依赖后感到非常无奈…

以及找到了onenote在Linux下的替代品(雾):git.coding.net+git定时push

我真机智qwq

代码

   

加入讨论

电子邮件地址不会被公开。 必填项已用*标注

关于本站

这是Hineven的博客!
主要保存蒟蒻的解题报告(笔记)
还有发布分享一些奇怪的东西

你可以通过上面的↑友情链接
访问Socialists的其他博客。

The Socialists!

我们的Site:socialists.studio
访问量:

AmazingCounters.com