UVaLuoguVjudge分析考虑 Polya 定理。容易得到一个置换的循环个数是 $\gcd(k,P)$ 。于是我们只需要找出所有置换即可。可以使用 KMP 。把原数组倍长，然后求差分数组。于是直接拿原差分数组匹配，能够匹配上的位置就对应着一个置换。代码// =================================== // author: M_sea // websi...
Luogu分析把每种洗牌法看成一个置换，那么题目就是等价类计数。考虑 Burnside 引理。我们只需要求出每个置换的不动点个数即可。考虑把置换拆成循环乘积的形式。对于一种不动点，显然一个循环内的颜色是相同的。于是可以考虑 DP 。设 $dp_{i,r,g,b}$ 表示前 $i$ 个循环，涂了 $r$ 个红色、$g$ 个绿色、$b$ 个蓝色的方案数，转移就是 01 背包。另外要自行加上单位置...