AGC027E や ARC110E を一般化すると、任意の位数 n の群とその長さ m の元の列で O(m + n log(n)) で同じことができそうですね。

数列 a に対する変な操作 X が、 実は簡単な操作 S （例：階差、累積和）を行った a では、簡単な操作 Y（例：swap）に見えるという問題。\(SX = YS \Leftrightarrow S^{-1}YS = X\) だから簡単な操作で表せる共役な演算を見つけろという問題に言い換えられる。\(X, Y\) の位数は等しい。\(S, Y\) が置換を表しているとき、\(X\) のサイクル分解は、\(Y\) のサイクル分解の頂点ラベルを \(S\) で置換したグラフになる。

\(g(x) \in \mathbb{Z}[x]\) が与えられる。次を満たす \(f(x) \in \mathbb{Z}[x]\) が存在する条件を求めたい（ABC288D）。

\begin{align}
&f(x)(1+x+\cdots+x^{A-1}) = g(x) \\
\iff &f(x) = g(x)(1-x) / (1-x^A)
\end{align}

\(h(x) :=g(x)(1-x) = \sum_i h_i x^i\) が \(1-x^A\) で割り切れればよい。従って、\(\sum_i h_{k+iA} = 0\) が任意の \(k\) で成り立てばよい。

\(g(x) \in \mathbb{Z}[x]\) が与えられる。\((1-2x+x^2) f(x) = g(x) \pmod{1-x^A}\) を満たす \(f(x) \in \mathbb{Z}[x]\) が存在するか判定せよ（ARC129D）。

\begin{align}
&(1-2x+x^2) f(x) = g(x) \pmod{1-x^A} \\
\iff &(1-x)^2 f(x) = g(x) \pmod{1-x^A} \\
\iff &(1-x) f(x) = g(x) \pmod{1+x+\cdots+x^{A-1}}

\end{align}

よって
\begin{align}
&g(x) = 0 \pmod {1-x, 1+x+\ldots+x^{A-1}} \\
\iff &g(x) = 0 \pmod {1-x, A} \\
\iff &g(1) = 0 \pmod A
\end{align}