实际上复杂度似乎更低一点，但是不太好写出来。

能，而且可以降得很多。你当时“第二问用 Burnside，第一问按稳定子群反演”的方向是对的；真正可以省掉的是：枚举每个具体子群，以及逐对子群判断包含关系。你题解最后一页描述的实现，恰好在这两步上都采用了比较直接的枚举。

我沿着这个方向继续推了一下，得到一个可实现的上界。令

$$N=nm,\qquad L=\operatorname{lcm}(n,m).$$

再记

$$R(n,m)=\sum_{s\mid N}\tau(\gcd(s,L)).$$

其中 $\tau(x)$ 是约数个数，则两问一起可以做到

$$\boxed{ O\!\left(k+T_{\rm factor}(n,m)+R(n,m)\log(2N)\right). }$$

这里 $T_{\rm factor}$ 是分解 $n,m$ 的代价；直接试除就是 $O(\sqrt n+\sqrt m)$。并且

$$R(n,m)\le \tau_3(N)=\sum_{s\mid N}\tau(s)=\prod_{q^e\parallel N}\binom{e+2}{2}.$$

也就是说，分解完 $n,m$ 以后，关于矩阵尺寸的部分可以降到约数级别，而不需要枚举 $nm$ 个位置，更不需要枚举全部子群。

我也把下面的算法写出来核对了：在题面的 $n,m\le1000$ 范围内，遍历所有尺寸得到 $R(n,m)\le7560$。所以最终大致是 $O(k)$ 的排列处理，加至多几千次快速幂。题面给出的完整范围是 $n,m\le1000$，$k\le10^6$。

下面分两层讲：先给一个比较自然的“商群类型”算法，再把它压成上面的复杂度。

1. 第二问可以写成一个通用函数

设颜色排列中，长度为 $r$ 的循环有 $c_r$ 个，定义

$$F_d=\#\operatorname{Fix}(p^d)=\sum_{r\mid d}r c_r.$$

对于任意一个将要出现的商群 $Q$，把位置集合看成 $Q$，仍然由 $Q$ 的平移定义相似关系。记：

$$B(Q)=\text{这个位置群上的优美的画的相似类数量}.$$

你题解中第二问的论证可以原样用在这里：枚举平移 $x$，统计满足 $p(A)=xA$ 的染色，再除以群的大小。

若 $x\in Q$ 的阶为 $d$，那么位置被分成 $|Q|/d$ 个长度为 $d$ 的环。每个环的起点颜色有 $F_d$ 种选择，其余颜色唯一确定。因此

$$\boxed{ B(Q)=\frac1{|Q|} \sum_{d\mid\exp(Q)} J_Q(d)F_d^{|Q|/d}, } \tag{1}$$

其中 $J_Q(d)$ 表示 $Q$ 中阶恰好为 $d$ 的元素个数。

这个公式的“除以 $|Q|$”也可以直接验证：一个合法轨道中的每幅画都有 $|\operatorname{Stab}(A)|$ 个平移将它变为 $p(A)$，所以整个轨道贡献

$$|\operatorname{orbit}(A)|\cdot|\operatorname{Stab}(A)|=|Q|.$$

对 $(A,x)$。

对于素数幂部分

$$Q_q=C_{q^u}\times C_{q^v},\qquad u\le v.$$

有

$$J_{Q_q}(1)=1,$$

以及

$$J_{Q_q}(q^j) = q^{\min(u,j)+\min(v,j)} - q^{\min(u,j-1)+\min(v,j-1)} \quad(j\ge1). \tag{2}$$

原因就是“阶整除 $q^j$”的元素数减去“阶整除 $q^{j-1}$”的元素数。不同素数的部分相乘即可。

所以，单独第二问其实只需枚举 $L$ 的约数，不必枚举 $\tau(n)\tau(m)$ 对约数。

颜色部分也不用做 $O(k\log k)$ 的筛：先 $O(k)$ 分解排列，再仅在 $L$ 的约数格上做按素因子的前缀和，就能在

$$O\bigl(k+\omega(L)\tau(L)\bigr)$$

时间内算出所有需要的 $F_d$。

2. 第一问：不需要知道稳定子群“长在哪里”

你题解的第一问是按稳定子群分类，再将合法轨道数乘以轨道大小。这个出发点可以保留。

关键是增加一个函数：

$$T(Q)=\text{位置群为 $Q$，且平移稳定子恰好平凡的合法轨道数}.$$

设原群为

$$G=C_n\times C_m.$$

对于一个具体子群 $H\le G$，稳定子恰好是 $H$ 的画，恰好对应于商群 $G/H$ 上稳定子平凡的画。

因此第一问答案为

$$\boxed{ A_1=\sum_{H\le G}|G/H|\,T(G/H). } \tag{3}$$

这里最重要的观察是：

右边关于 $H$ 的贡献，只取决于 $G/H$ 的同构类型，不取决于 $H$ 在二维矩阵中的具体方向。

所以你题解中那些“斜分量”造成的复杂坐标关系，完全可以不处理。只要统计每种商群类型出现多少次。

商群类型只有约数级别

对每个素数 $q\mid N$，令

$$a_q=\min(v_q(n),v_q(m)),\qquad b_q=\max(v_q(n),v_q(m)).$$

则 $G$ 的这一部分是

$$C_{q^{a_q}}\times C_{q^{b_q}}.$$

它的商群类型可以用

$$C_{q^u}\times C_{q^v}, \qquad 0\le u\le a_q,\quad u\le v\le b_q$$

表示。

因此全部商群同构类型的数量是

$$D= \prod_{q\mid N} \left((a_q+1)(b_q+1)-\frac{a_q(a_q+1)}2\right) \le \tau(n)\tau(m). \tag{4}$$

每种类型出现多少次，也有简单公式

固定一个素数，简写 $a=a_q,b=b_q$。令

$$M_{a,b}(u,v) = \#\{H\le C_{q^a}\times C_{q^b}: (C_{q^a}\times C_{q^b})/H\cong C_{q^u}\times C_{q^v}\}.$$

则

$$\boxed{ M_{a,b}(u,v)= \begin{cases} 1,&u=v,\\[2mm] q^{v-u-1}(q+1),&u<v\le a,\\[2mm] q^{a-u},&u\le a<v\le b. \end{cases} } \tag{5}$$

这是按不变因子类型统计子群的素数幂版本；相关一般公式可见 Tóth 关于秩二有限阿贝尔群子群计数的论文。

也可以直接理解它：有限阿贝尔群的自对偶性将“商群类型的数量”变成“该类型子群的数量”。类型为 $(u,v)$ 的子群包含整个 $q^u$-挠子群；模掉它以后，剩下的是一个阶为 $q^{v-u}$ 的循环子群，用阶恰好的元素数除以生成元个数即可。

不同素数的 $M$ 相乘得到 $M_G(Q)$，于是式 (3) 变成

$$\boxed{ A_1=\sum_{\text{商群类型 }Q}M_G(Q)|Q|T(Q). } \tag{6}$$

现在唯一的问题是：如何由 $B(Q)$ 得到 $T(Q)$。

3. 逐对子群容斥，可以变成每个素数至多四项的差分

这一步是另一个主要简化。

非平凡稳定子一定包含一个素数阶子群。所以排除非平凡稳定子，只需要对这些最小的子群做容斥。

固定素数 $q$。当

$$Q_q=C_{q^u}\times C_{q^v},\qquad 0<u\le v$$

时，

$$Q_q[q]\cong C_q^2.$$

它有 $q+1$ 个一维子空间，也就是 $q+1$ 个阶为 $q$ 的子群。任意两个不同的一维子空间都生成整个 $Q_q[q]$。因此，容斥中所有二阶及以上的交集都相同，总系数为

$$\sum_{i=2}^{q+1}(-1)^i\binom{q+1}{i}=q.$$

而这些一维子群对应的商群类型，也只有至多两种。

将其他素数的坐标固定，把当前数组值写成 $f_{u,v}$，定义变换

$$\boxed{ (\mathcal D_q f)_{u,v}= \begin{cases} f_{0,0},&u=v=0,\\[1mm] f_{0,v}-f_{0,v-1},&u=0<v,\\[1mm] f_{u,v}-qf_{u-1,v}-f_{u,v-1} +qf_{u-1,v-1},&0<u<v,\\[1mm] f_{u,u}-(q+1)f_{u-1,u} +qf_{u-1,u-1},&0<u=v. \end{cases} } \tag{7}$$

其中，当 $u<v$ 时，有 $q$ 条直线对应商群类型 $(u-1,v)$，另有一条对应 $(u,v-1)$；当 $u=v$ 时，全部 $q+1$ 条直线都对应 $(u-1,u)$。

对所有素数分别做这个变换，就得到

$$\boxed{ T=\left(\prod_{q\mid N}\mathcal D_q\right)B. } \tag{8}$$

不同素数的变换作用在不同坐标上，可以依次执行。总共只需要 $O(\omega(N)D)$ 次运算，不需要枚举任何一对子群。

到这里，已经得到一个相当自然的算法：

先枚举所有商群类型，用式 (1) 计算 $B$；再做式 (7) 的差分得到 $T$；最后用式 (6) 加权求和。

它的复杂度可以写成

$$O\!\left( k+T_{\rm factor} +\left(\sum_Q\tau(\exp Q)\right)\log(2N) +\omega(N)D \right).$$

粗略上界就是

$$\boxed{ O\!\left( k+T_{\rm factor} +\tau(n)\tau(m)\tau(L)\log(2N) \right). } \tag{9}$$

这一版已经把原来的主要多项式因子都去掉了，而且比处理斜分量、再对子群做容斥更容易写清楚。

4. 再合并同类项：最终只需要两个约数

上面还能继续压缩。

观察式 (1)：无论商群类型是什么，所有涉及颜色的项都长成

$$F_d^{s/d}, \qquad s=|Q|,\quad d\mid\exp(Q).$$

所以最终没有必要保留“这个项来自哪一种商群”，只需要保留二元组 $(s,d)$。

难点在于：不能先枚举所有类型和所有阶，再声称只花合并后的时间。这里要利用系数按素因子分解，直接生成合并后的系数。

把容斥变换转移到权重上

由

$$A_1=\sum_Q M_G(Q)|Q|\,T(Q).$$

和式 (8)，可以把线性变换从 $B$ 上转置到权重上。

固定素数 $q$，省略 $M$ 的下标 $a,b$，并约定不合法坐标上的 $M$ 为零。转置后，再除掉式 (1) 中的群阶分母，得到局部权重

$$\boxed{ \begin{aligned} W_q(u,v)={}&M(u,v)-qM(u,v+1)\\ &-q\bigl(q+\mathbf1_{v=u+1}\bigr)M(u+1,v)\\ &+q^3M(u+1,v+1). \end{aligned} } \tag{10}$$

这个式子只是式 (7) 收集系数的结果；实现时也可以不记公式，直接把每个状态的权重向至多四个位置分配。

接着定义

$$K_q(e,j)= \sum_{\substack{0\le u\le a,\ u\le v\le b\\u+v=e}} W_q(u,v)\,J_{C_{q^u}\times C_{q^v}}(q^j). \tag{11}$$

它已经合并了所有“群阶的 $q$-指数为 $e$、元素阶的 $q$-指数为 $j$”的贡献。

于是第一问可以直接写成

$$\boxed{ A_1= \sum_{s\mid N} \sum_{d\mid\gcd(s,L)} \left( \prod_{q\mid N}K_q(v_q(s),v_q(d)) \right) F_d^{s/d}. } \tag{12}$$

这里按素因子相乘的是系数，不是 $F_d$，也不是整个答案。

另外，当 $s=N$ 时，只有原群 $G$ 自己这一种商群，其权重为 $1$。因此

$$\prod_qK_q(v_q(N),v_q(d))=J_G(d).$$

也就是说，枚举式 (12) 时，把其中 $s=N$ 的项另外累加，再除以 $N$，就同时得到了第二问。

复杂度为什么就是开头的 R(n,m)R(n,m)

对每个素数，合法指数对为

$$0\le e\le a+b,\qquad 0\le j\le\min(e,b).$$

所以二元组总数是

$$\begin{aligned} R(n,m) &=\prod_{q\mid N} \sum_{e=0}^{a_q+b_q}(\min(e,b_q)+1)\\ &=\prod_{q\mid N} \frac{(b_q+1)(2a_q+b_q+2)}2. \end{aligned} \tag{13}$$

每一项只做一次快速幂。各素数的局部表预处理，以及 $F_d$ 的约数前缀和，都可以被 $O(R\log(2N))$ 吸收。

因此得到

$$\boxed{ O\!\left( k+T_{\rm factor}(n,m)+R(n,m)\log(2N) \right). }$$

深度优先枚举 $(s,d)$，不保存全部二元组，空间还可以控制为

$$\boxed{ O\bigl(k+\tau(L)+\log^2(2N)\bigr). }$$

5. 一个很直观的特例：$n=m=q$，其中 $q$ 是素数

这个特例很能体现压缩的效果。

具体子群有 $q+3$ 个，但商群类型只有三个：

$$1,\qquad C_q,\qquad C_q^2.$$

最终两问直接化成

$$\boxed{ A_2= \frac{ F_1^{q^2}+(q^2-1)F_q^q }{q^2} }$$

以及

$$\boxed{ A_1= F_1^{q^2} +(q^2-1) \left( F_q^q-F_1^q-(q-1)(F_q-F_1) \right). } \tag{14}$$

第一问只剩三个非平凡快速幂。

比如 $p$ 为恒等置换时，$F_1=F_q=k$，式 (14) 立即退化为 $A_1=k^{q^2}$。当 $q=2$、颜色排列交换两种颜色时，得到 $A_1=6,A_2=3$。

顺便，原题解描述的枚举量其实也可以写得比较明确。由其中的子群参数化，具体子群数量是

$$S(n,m)=\sum_{a\mid n}\sum_{b\mid m}\gcd(a,b).$$

如果严格按最后一页所述，对每个参数都枚举相应的 $a\times b$ 个平移，那么这部分循环次数是

$$E(n,m)=\sum_{a\mid n}\sum_{b\mid m}ab\gcd(a,b).$$

另有 $S(n,m)^2$ 次子群对检查。这里尚未计入单次检查、最大公因数、快速幂等代价。

特别地，$n=m=q$ 时，

$$S=q+3,\qquad E=q^3+2q+1.$$

所以，按讲义中这个枚举框架，素数正方形就已经有立方级枚举；合并商群类型之后，它反而几乎是最简单的情况。没有原标程，我不把这个循环计数当作对具体代码运行时间的断言。

实现与校验

我写了式 (12) 对应的 C++17 实现，使用原题的输入输出格式，并跑了共 615 组校验：315 组小规模逐染色穷举、198 组独立的显式子群枚举校验、100 组大尺寸恒等置换校验，以及两个题面样例，均一致。

另外遍历了所有 $1\le n\le m\le1000$，得到：

• 商群类型数最大为 504；
• 未做最后合并时，式 (1) 的求和项数最大为 13680；
• 最终二约数版本的 $R(n,m)$ 最大为 7560，在 $(n,m)=(704,945)$ 取到。

代码

所以，重新写这道题的题解时，我会把核心从“枚举稳定子群并判断包含关系”，改成：

按商群同构类型计数，用秩至多二的局部容斥得到平凡稳定子，再把相同的 $F_d^{s/d}$ 合并。

这保留了你原来的群论思路，但复杂度可以从不太透明的 $\operatorname{poly}(n,m)+k$，明确降到上面的 $O(k+T_{\rm factor}+\tau_3(nm)\log(nm))$ 上界。