随笔题解 Pb. 2

来源：2022 杭电杯 Day 6 1011 Find different。

设有一个长度为 $l$ 的序列 $x_0,x_1,\dots,x_{l-1}$，其中 $0\leqslant x_i\lt m$。两种操作：

1. $x_i\leftarrow (x_i+1)\bmod m$
2. $x_i\leftarrow x_{(i+1)\bmod n}$

每次操作时，所有 $x_i$ 同时发生变化。

两个序列 $x_0,x_1,\dots,x_{l-1}$ 和 $y_0,y_1,\dots,y_{l-1}$，如果 $x$ 能够通过若干次操作变为 $y$，那么称 $x$ 和 $y$ 本质相同；否则称 $x$ 和 $y$ 本质不同。

$(0,2,2)$ 和 $(0,1,0)$ 是本质相同的，因为：

1. 进行操作 $1$：$(0,2,2)\rightarrow(1,0,0)$
2. 进行操作 $2$：$(1,0,0)\rightarrow(0,0,1)$
3. 进行操作 $2$：$(0,0,1)\rightarrow(0,1,0)$

对于所有 $1\leqslant l\leqslant n$，求出长度为 $l$ 的所有序列中有多少种本质不同的序列。模 $998244353$。

$n,m\leqslant 10^5$。

令 $f(n)$ 为长度为 $n$ 且满足题目要求的序列的数量。

Burnside 引理：集合 $X$ 在群 $\langle G,\times\rangle$ 作用下的等价类数量等于 $G$ 中所有元素作用在集合 $X$ 上时的不动点数量的算术平均值。

令 $X$ 为全体长度为 $n$ 的序列构成的集合；$G=\{(x,y)\mid 0\leqslant x\lt n,0\leqslant y\lt m\}$，其中 $(x,y)\in G$ 表示进行 $x$ 次操作 $2$ 和 $y$ 次操作 $1$。显然两种操作的相对顺序不影响。

定义 $G$ 上的乘法 $\times$ 为

$$(x_1,y_1)\times(x_2,y_2)=(x_1+x_2\bmod n,y_1+y_2\bmod m)$$

显然 $\langle G,\times\rangle$ 是一个群。

考虑在 $(x,y)$ 作用下 $X$ 中的不动点的数量。此时为了方便，把 $x=0$ 看作 $x=n$，$y=0$ 看作 $y=m$。进行 $x$ 次操作 $1$ 会把原序列划分为 $(n,x)$ 个环（简单回路），每个元素移动到对应环上下一个元素的位置上；进行 $y$ 次操作 $2$ 会把所有元素在模 $m$ 意义下加 $y$。如果进行完所有操作之后序列仍保持不变，必是每个元素移动到的位置上原本的数值恰好比自身大 $y$。按照这样推下去，环上的每个元素会比自身大

$$k\cdot\frac{n}{(n,x)}y\quad(k\geqslant 1)$$

那么这就要求

$$m\Bigm|\frac{n}{(n,x)}y$$

于是我们就可以写出答案的表达式

$$\begin{aligned} &f(n)\\ =&\sum_{x=1}^n\sum_{y=1}^m\left[m\Bigm|\frac{n}{(n,x)}y\right]m^{(n,x)}\\ =&\sum_{x=1}^n\sum_{y\mid m}\left[\frac{m}{y}\Bigm|\frac{n}{(n,x)}\right]m^{(n,x)}\\ =&\sum_{x=1}^n\sum_{y\mid m}\left[y\Bigm|\frac{n}{(n,x)}\right]m^{(n,x)}\\ =&\sum_{x=1}^n\left(\frac{n}{(n,x)},m\right)m^{(n,x)}\\ =&\sum_{d=1}^n\sum_{x=1}^n\left[(n,x)=d\right]\left(\frac{n}{d},m\right)m^d\\ =&\sum_{d\mid n}\sum_{x=1}^{n/d}\left[\left(\frac{n}{d},x\right)=1\right]\left(\frac{n}{d},m\right)m^d\\ =&\sum_{d\mid n}\varphi\left(\frac{n}{d}\right)\left(\frac{n}{d},m\right)m^d\\ =&\sum_{ij=n}\varphi(i)(i,m)m^j \end{aligned}$$

时间复杂度 $O(n\log n)$。