题目大意
$$ f((i + n) \bmod r, (j + m) \bmod c) = p_{f(i, j)} $$其中 $p$ 是一个给定的颜色的排列。
两种染色方案相同当且仅当其中一个可以通过下标平移（模意义下）得到另一个。求不同的染色方案数。
$2 \leq K \leq 10^4$, $1 \leq r, c \leq 10^6$，需要处理 $100$ 组询问。
时间限制 $10$ 秒。
题解
记网格的行、列组成的集合分别为 $X$ 和 $Y$，颜色集为 $K$。
Burnside 引理
首先考虑无视排列 $p$ 给出的限制，即 $p$ 是单位排列的特殊情况。
$$ \begin{align*} G \times K^{X \times Y} &\longrightarrow K^{X \times Y} \newline (g, f) &\longmapsto f \circ g \end{align*} $$其中 $f \circ g$ 表示映射的复合 $t \mapsto f(g(t))$，其中 $t \in X \times Y$。
$$ |K^{X \times Y} / G| = \frac{1}{|G|} \sum_{g \in G} \\# \\{ f \in K^{X \times Y} : f \circ g = f \\} $$注意到 $G \cong C_r \oplus C_c$ 同构于两个循环群的直和，我们不难写出答案
$$ |K^{X \times Y} / G| = \frac{1}{rc} \sum_{i | r, j | c} \varphi(i) \varphi(j) |K|^{\frac{rc}{\operatorname{lcm}(i, j)}} $$额外限制
$$ f \circ g = p \circ f $$$$ \frac{1}{|G|} \sum_{g \in G} \\# \\{ f \in K^{X \times Y} : f \circ g = p \circ f \\} $$我们先考虑这玩意怎么求，之后再来证明这个式子。
$$ p_{f(t)} = f(g(t)) $$即格子 $t$ 在置换 $g$ 作用下的像的颜色，一定是 $t$ 自身颜色在排列上的后续。不妨设 $g = (s, t) \in C_r \oplus C_c$，则格子 $t$ 在置换 $g$ 的不断作用下经过的轨道大小为 $l = \operatorname{lcm}\left( \dfrac{r}{\gcd(s, r)}, \dfrac{c}{\gcd(c, t)} \right)$，进而可知 $t$ 中只有长度为 $l$ 的因子的循环才能完成该轨道的染色。
$$ \frac{1}{cr} \sum_{i | r, j | c} \varphi(i) \varphi(j) K(\operatorname{lcm}(i, j))^{\frac{rc}{\operatorname{lcm}(i, j)}} $$其中 $K(x)$ 表示排列 $p^x$ 的不动点个数。
预处理一下排列的环长信息，直接暴力枚举即可。由于排列中不同的环长最多有 $O(\sqrt{K})$ 种，而 $10^6$ 范围内因子数 $d \leq 240$，故单次询问的时间复杂度是 $O(K + \sqrt{R} + d^2\sqrt{K})$。足以通过此题。
| |
证明
我们的结论可以归纳为
$$ f \circ g = p \circ f $$$$ \frac{1}{|G|} \sum_{g \in G} \\# \\{ f \in X : f \circ g = p \circ f \\} $$
我们首先说明我们所定义的等价类是“好”的良定义（即与代表元选取无关）。
$$ \begin{align*} f_1 \circ g = p \circ f_1 &\iff (f_2 \circ g_0) \circ g = p \circ (f_2 \circ g_0) \newline &\iff f_2 \circ (g_0 \circ g \circ g_0^{-1}) = p \circ f_2 \newline &\iff f_2 \circ (g_0^{-1}gg_0) = p \circ f_2 \newline \end{align*} $$上式中最后一步是群作用的定义。注意到 $g \mapsto g_0^{-1}gg_0$ 是双射，故对 $f_1$ 和 $f_2$ 而言符合要求的 $g$ 是一样多的。
$$ G_{p}^{f} = \\{ g \in G : f \circ g = p \circ f \\} $$我们前面已经证明，当 $f_1$ 与 $f_2$ 在同一条轨道中时有 $|G_{p}^{f_1}| = |G_{p}^{f_2}|$。此外，我们断言：当 $G_{p}^{f}$ 非空时有 $|G_{p}^{f}| = |G^{f}|$。
$$ f \circ (gg_0) = (f \circ g_0) \circ g = f \circ g = p \circ f $$$$ f \circ (g^{-1}g_0) = (f \circ g_0) \circ g^{-1} = (f \circ g) \circ g^{-1} = f $$故有 $gG^f \supset G_{p}^{f}$。综上有 $gG^f = G_{p}^{f}$，进而 $|G^f| = |G_{p}^{f}|$。
$$ \sum_{g \in G} \\# \\{ f \in X : f \circ g = p \circ f \\} = \sum_{f \in X} |G_{p}^{f}| = \sum_{\overline{f} \in X / G} |G_{p}^{f}| |G(f)| $$注意到 $|G_{p}^{f}|$ 的取值只可能为 $0$ 或 $|G^f|$，而 $|G^f||G(f)| = |G|$，由此命题得证。
效率优化
我们发现代码的性能瓶颈是 60-69 行的查询部分，中间那个 for 循环每次都会完整遍历整个 map。
同时不难发现，我们的查询实际上是计数序列和全 $1$ 序列的 Dirichlet 卷积。同时计数序列有一个很微妙的的性质：所有非零元只出现在下标是 $\operatorname{lcm}(r, c)$ 因子的位置。
这种情况下的 Dirichlet 卷积可以通过枚举 $\operatorname{lcm}(r, c)$ 的素因子进行。具体细节参考代码。
由于 $\operatorname{lcm}(r, c)$ 的因子数 $d_1 \leq 6720$，素因子个数 $\omega \leq 11$，故单次查询的时间复杂度降为 $O(K + R + d_1\omega + d^2 \log d_1)$。实际测试中运行效率显著提升。
| |