题解：P14816 [ICPC 2023 Yokohama R] Ferris Wheel
WorldMachine
·
·
题解
其实本题可以 \mathcal O(n)。
首先我们需要重新描述一个染色方案合法的条件：一个环，字符集为 [1,k]，每次可以删去两个相邻的相等元素，最后能够删完。
事实上，在合法判定这方面，不难通过归纳法证明环和序列是等价的，即一个合法的序列不管怎么循环移位都是合法的，反之亦然。
证明：将原序列表示成 \texttt{(...)(...)...(...|...)...(...)} 的形式，每对括号代表最外层匹配的字符，其中 \texttt| 是循环移位切开的位置，那么其它的括号不会受影响，考虑被切开的括号，由于是同种字符，\texttt( 移过去之后可以和相邻的 \texttt) 一起清除，这样就只剩下中间的 \texttt{...|...}，是一个更小的子问题。边界条件 |S|=2 显然成立。
而如果一个序列原本不合法但存在一个循环移位使得其合法，那么它就可以循环移位回去，那么原序列又是合法的（不是我这句话在说什么），矛盾。
因此可以将一个序列描述成 \Gamma=\underbrace{\mathbb Z_2*\cdots*\mathbb Z_2}_{k个}（k 个二阶循环群的自由积）中的元素，约简后的结果要么是单位元 e，要么是不可约的字符串如 \texttt{qwq}。
现在要计算旋转同构意义下的本质不同染色方案个数，考虑使用 Burnside 引理，设 G 为 2n 阶旋转群，那么答案为 \displaystyle{\dfrac{1}{2n}\sum_{g\in G}|X^g|}，其中 X^g 为在 g 作用下保持不变的合法染色方案集合。
循环移位 k 位后保持不变，意味着该方案具有周期 \gcd(2n,k)，而满足 \gcd(2n,k)=d 的 k 有 \varphi\left(\dfrac{2n}{d}\right) 个，故所求即为 \displaystyle{\dfrac{1}{2n}\sum_{d\mid2n}}\varphi\left(\dfrac{2n}d\right)f_d，其中 f_d 为重复 \dfrac{2n}{d} 次后合法的颜色序列个数。
考虑计算 f_d。
关于上面充要条件的证明：\Leftarrow 显然，\Rightarrow 考虑由于序列删不动了，每次肯定是同时删去头和尾，也是显然的。
因此有：
f_d=\left\{\begin{aligned}
&A_d&2\mid d\\
&B_d&2\nmid d
\end{aligned}
\right.
现在问题变为如何计算 A_d 和 B_d。设 F(x) 和 G(x) 是 A 和 B 的 OGF，首先求 F(x)。
一个合法的串要么是空的，要么可以被分解成 cUcV 的形式，其中 U 和 V 都是合法串，且 U 不能匹配到开头的 c，设满足条件的 U 的 OGF 为 H(x)（不同的 c 是本质相同的，因此 H(x) 与 c 的选取无关），那么有 F(x)=1+kx^2H(x)F(x)。
$$
H(x)=1+(k-1)x^2H^2(x)
$$
解得 $H(x)=\dfrac{1-\sqrt{1-4(k-1)x^2}}{2(k-1)x^2}$，如果你直接代回关于 $F(x)$ 的方程则需要超乎常人的勇气和毅力，更好的方法是由 $F(x)$ 的方程得到 $H(x)=\dfrac{F(x)-1}{kx^2F(x)}$，然后代入上面的方程并整理得到 $(1-k^2x^2)F^2(x)+(k-2)F(x)-(k-1)=0$，然后就能解得：
$$
F(x)=\frac{2-k+k\sqrt{1-4(k-1)x^2}}{2(1-k^2x^2)}
$$
令 $t=x^2$，使用广义二项式定理展开 $\sqrt{1-4(k-1)t}$，再和 $\dfrac{1}{1-k^2t}$ 乘起来，再加加减减一点剩下的东西，可得：
$$
A_{2m}=k^{2m}\left(1+\dfrac k2\sum_{i=1}^m\binom{1/2}{i}\left(\dfrac{-4(k-1)}{k^2}\right)^i\right)
$$
设 $Y=\dfrac{-4(k-1)}{k^2}$，$S_m=\displaystyle\sum_{i=1}^m\dbinom{1/2}iY^i$，则有 $A_{2m}=k^{2m}\left(1+\dfrac k2S_m\right)$。
接下来考虑求出 $G(x)$。
根据上面的说明，契合 $G(x)$ 的串在序列上消彻底之后得到的既约串 $W$ 一定是一个长度为奇数的回文串，长度为 $2l+1$ 的这样的串显然有 $k(k-1)^l$ 个（中间任取，再从中间向两侧依次选取，不能和上一个相等）。那么原串 $S$ 可以表示成 $S_0w_1S_1w_2\cdots S_{l-1}w_lS_l$ 的形式，其中 $S_0$ 是契合 $F(x)$ 的串，而 $S_i$（其中 $i>0$）是契合 $H(x)$ 的串。因此有：
$$
\begin{aligned}
G(x)&=\sum_{l=0}^{+\infty}k(k-1)^lx^{2l+1}F(x)H^{2l+1}(x)\\
&=kxF(x)H(x)\sum_{l=0}^{+\infty}((k-1)x^2H^2(x))^l\\
&=kxF(x)H(x)\sum_{l=0}^{+\infty}(H(x)-1)^l\\
&=\dfrac{kxF(x)H(x)}{2-H(x)}
\end{aligned}
$$
第三个等号用到了 $H(x)$ 的定义，神奇吧。
设 $\Delta(x)=\sqrt{1-4(k-1)x^2}$，$\lambda(x)=\dfrac{1-\Delta(x)}{2(k-1)x}$，通过一通极度漫长且折磨的化简之后我们可以得到：
$$
G(x)=\dfrac{kx}{2(1-k^2x^2)}\left(k-\dfrac{k-2}{\Delta(x)}\right)
$$
然后再把 $\Delta(x)$ 的定义代进去，终于得到了 $G(x)$ 的完整表达式：
$$
G(x)=\dfrac{k^2x}{2(1-k^2x^2)}-\dfrac{k(k-2)x}{2(1-k^2x^2)\sqrt{1-4(k-1)x^2}}
$$
采用和上面展开 $F(x)$ 类似的方法，可以得到 $B_{2m+1}$ 的表达式：
$$
B_{2m+1}=k^{2m+1}\left(1+\left(1-\dfrac k2\right)\sum_{i=1}^m\binom{-1/2}{i}\left(\dfrac{-4(k-1)}{k^2}\right)^i\right)
$$
设 $Q_m=\displaystyle\sum_{i=1}^m\dbinom{-1/2}{i}Y^i$，则有 $B_{2m+1}=k^{2m+1}\left(1+\left(1-\dfrac k2\right)Q_m\right)$。
只需要 $\mathcal O(n)$ 递推出 $\dbinom{a}{m}Y^m$ 然后求前缀和就能够处理出 $S_m$ 和 $Q_m$ 并直接求解 $A_{2m}$ 和 $B_{2m+1}$。这是容易做的：
$$
\binom{a}{m}Y^m=\binom{a}{m-1}\dfrac{a-m+1}{m}\cdot Y^m=\left(\binom{a}{m-1}Y^{m-1}\right)\dfrac{(a-m+1)Y}{m}
$$
具体地说，对于 $\dfrac12$ 和 $-\dfrac12$，有：
$$
\begin{aligned}
\binom{1/2}mY^m&=\left(\binom{1/2}{m-1}Y^{m-1}\right)\dfrac{(3-2m)Y}{2m}\\
\binom{-1/2}mY^m&=\left(\binom{-1/2}{m-1}Y^{m-1}\right)\dfrac{(1-2m)Y}{2m}
\end{aligned}
$$
线性预处理逆元，然后就做完了，时间复杂度为 $\mathcal O(n)$。注意到这个东西是可以整式递推的，不过前面有个 Burnside 所以还是只有 $\mathcal O(n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 3e6 + 5, p = 998244353, inv2 = (p + 1) / 2;
int n, k, tot, pri[412855], phi[N << 2], inv[N], S[N], Q[N];
il int mod(int x) { return x >= p ? x - p : x; }
il int qpow(int a, int b) { int c = 1; while (b) { if (b & 1) c = (ll)c * a % p; a = (ll)a * a % p, b >>= 1; } return c; }
void sieve(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!phi[i]) phi[pri[++tot] = i] = i - 1;
for (int j = 1, k; j <= tot && (k = i * pri[j]) <= n; j++) {
if (!(i % pri[j])) { phi[k] = phi[i] * pri[j]; break; }
phi[k] = phi[i] * (pri[j] - 1);
}
}
}
il int A(int m) { return qpow(k, m << 1) * (1 + (ll)k * inv2 % p * S[m] % p) % p; }
il int B(int m) { return qpow(k, m << 1 | 1) * (1 + (1 - (ll)k * inv2 % p + p) * Q[m] % p) % p; }
int main() {
cin >> n >> k; if (k == 1) return cout << 1, 0; sieve(n << 1);
const int Y = 4ll * (1 - k + p) % p * qpow(k, p - 3) % p, Yinv2 = (ll)Y * inv2 % p;
for (int m = 1, C = 1, C_ = 1; m <= n; m++) {
inv[m] = m == 1 ? 1 : ll(p - p / m) * inv[p % m] % p;
int Yinv2m = (ll)Yinv2 * inv[m] % p;
C = C * (3 - 2ll * m + p) % p * Yinv2m % p, C_ = C_ * (1 - 2ll * m + p) % p * Yinv2m % p;
S[m] = mod(S[m - 1] + C), Q[m] = mod(Q[m - 1] + C_);
} int n2 = n << 1, ans = 0;
for (int d = 1; d <= n2; d++) if (!(n2 % d)) ans = (ans + (ll)phi[n2 / d] * (d & 1 ? B : A)(d >> 1)) % p;
cout << (ll)ans * qpow(n2, p - 2) % p;
}
```