[HNOI2008] Cards

这应该是最传(麻)统(烦)的做法

首先题目里面有句话说

输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

这话啥意思?意思就是置换群大小 |G| = m+1 (自己到自己也算一个)

(并且(除幺元置换之外)没有不动点,这个性质直接导致了那个组合数的解法)

上文的大概证明可以找找洛谷上的题解

不过我们还是可以这么做:

找每个置换 g_i 的循环节,然后DP出不动点的个数。

最后算一下方案就好了, 直接硬上 Burnside

 

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据