[HNOI2008] Cards

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

首先题目里面有句话说

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

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

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

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

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

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

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

 

通过移位形成的置换群的轮换数

有这样一个结论,n个元素的置换群通过移k位形成的置换数是 \gcd(n, k)
例如 n = 6, k = 2 的置换群的置换数是 \gcd(6, 2) = 2

0 1 2 3 4 5
2 3 4 5 0 1

形成的置换是 [2, 4, 0][3, 5, 1]

考虑一下为什么是这样的,一个直观的入手点就是尝试几个例子,然后分析一下置换是怎样形成的,清楚了这个自然也就明白了置换数会是多少。

  • 假设我们移位 k,并且从 \rm base 位置开始寻找置换,那么置换将会是 (kx + \mathrm{base} )\mod n \; (x \in \mathbb{N} ) 得到的数字。

例如 n = 9, k = 6

0 1 2 3 4 5 6 7 8
6 7 8 0 1 2 3 4 5

\rm{base} = 0 位置对应开始

\begin{array}{c} 6 \times 1 \mod 9 = 6 \\ 6 \times 2 \mod 9 = 3 \\ 6 \times 3 \mod 9 = 0 \\ \end{array}

\rm{base} = 1 位置对应开始


\begin{array}{c} (6 \times 1 + 1) \mod 9 = 7 \\ (6 \times 2 + 1) \mod 9 = 4 \\ (6 \times 3 + 1) \mod 9 = 1 \\ \end{array}

\rm{base} = 2 位置对应开始

\begin{array}{c} (6 \times 1 + 2) \mod 9 = 8 \\ (6 \times 2 + 2) \mod 9 = 5 \\ (6 \times 3 + 2) \mod 9 = 2 \\ \end{array}

对于这个例子观察发现,形成的置换貌似就是\mathrm{mod}\; \gcd(n,k) 的同余类。

看看这是不是正确的,前面的分析过程使我们将置换转换为 (kx + \mathrm{base} ) \mod n 这样的一个式子, 也就是说这个式子的结果根据 \rm base 的不同为什么会形成\mathrm{mod}\; \gcd(n,k) 的同余类。

我们在这里让 \mathrm{base} < n ,于是我们有:

(kx + \mathrm{base}) \;\mathrm{mod}\; n = kx \;\mathrm{mod}\; n + \mathrm{base}

这样我们可以只分析 kx \mod n 这一部分。

我们让 kx \;\mathrm{mod}\; n \equiv ky \;\mathrm{mod}\; n

所以 k \cdot (y-x) \;\mathrm{mod}\; n = 0

x = 0 时,ky \;\mathrm{mod}\; n = 0 ,这就意味着我们要证明满足此式子的 y > 0\min x\frac{n}{gcd(n,k)}

我们假设 x < \frac{n}{gcd(n, k)} 且满足上式时,kx | n,而且显然 kx | m ,那么 kx 就是 nk 的最小公倍数 。

但是 kx < k \cdot \frac{n}{gcd(n,k)} ,右边才是最小公倍数,所以当 x < \frac{n}{gcd(n, k)} 时,不满足 k \cdot (y-x) \;\mathrm{mod}\; n = 0

所以满足上式的 \min x=\frac{n}{gcd(n,k)}。这也就是轮换的个数是 \frac{n}{gcd(n,k)}