概要
本質的には、解説PDFと同一の解法でしたが、考察の手順は割と違っていた気がします。人によっては、着想が分かりやすくなると思うので、記しておきます。
解法
多項式・形式的べき級数ではないものも、雑に多項式と書いていきます。
$f(x,y,z) = \biggl(x + \frac{1}{x} + y + \frac{1}{y} + z + \frac{1}{z} + xyz + \frac{1}{xyz}\biggr)$ とおきます。このとき、$N$ 回の操作の結果の分布は次のように解釈できます：
・$f(x,y,z)^N = \sum_{p,q,r}a_{p,q,r}x^py^qz^r$ であるとする。
・このとき、変数 $(x,y,z) = (p,q,r)$ となる操作手順の総数は、$a_{p,q,r}$ に等しい。
変数の状態に対して、操作手順の総数を持たせて dp していこうとすると、dp テーブル全体を $8$ 通りにスライドして重ね合わせることになります。dp の値を多項式の係数に対応させておくことで、遷移が多項式をかけることとして表現できていますね。
・$x + \frac{1}{x}$：$x$ の次数を $\pm 1$ する。
・$xyz + \frac{1}{xyz}$：$x,y,z$ の次数を全て共通で $\pm 1$する。
などとして、全ての dp 遷移が $f(x,y,z)$ に書き込まれています。
したがって、あとは $f(x,y,z)^N$ を上手く計算できる構造を見つければよいです。ここで高校数学レベルの簡単な計算で、\[ f(x,y,z) = \frac{1}{xyz}(1+xy)(1+xz)(1+yz)\] と因数分解できます。これは、「対称式で因数分解できて、項が8個なら、2個が3つだろう」「因数定理」のような観察もありますし、高校問題集的には「$x$ で整理して係数ごとの共通因数を探す」という方法も標準的です。
あとは簡単です（といいつつ、コンテスト中はここまでが一瞬でここからに時間を使った）。
最後に変数を $\pmod{m}$ して考えていて、これは $x^m = 1$ 等のルールに対応します。$x^m = y^m = z^m = 1$ というルールを追加した場合、\[(1+xy)^N = \sum_{0\leq i < m}a_ix^iy^i\] となる $a_i$ が計算できます（二項係数を周期 $m$ で集約する）。\[ f(x,y,z)^N = \frac{1}{(xyz)^N}\sum_{i,j,k}(a_ia_ja_k)(x^iy^i)(x^jz^j)(y^kz^k)\] なので、求めたい値に対応する $(i,j,k)$ に対する $a_ia_ja_k$ を足し合わせれば終わりです。
$a_i$ の計算は、二項係数を求めて集約するだけなので、$\Theta(N)$ で行えます。適切な $i,j,k$ の列挙は足して引いて割るだけ、くらいで $ \Theta (1)$ です（高々2通りになります）。全体として、$ \Theta (N)$ で答が求まります。
コメント
- 公式解説 pdf と本質的には同じだと思います。公式解説には $O(N \log N)$ と書いてあるが、$\log$ ありますっけ？
- 多項式環じゃない問題 → これは何の環と思えばよいのか？ まぁ適当で良いと思いますが、環 $\mathbb{Z}[x,1/x,y,1/y,z,1/z]$ あるいは、Laurent多項式環 $\mathbb{Z}((x,y,z))$ など。本問題については $m$ 乗周期なので、剰余環 $\mathbb{Z}[x,1/x,y,1/y,z,1/z] / (x^m-1,y^m-1,z^m-1)$。
- 行列、群環の元、多項式などによって、dp 遷移が描ける問題です。「数列の畳み込み」という形で理解することも可能ですが、文字式になると、多くの人の直感が働きやすいと思います（結合法則や交換法則が自明に感じられる、疎な元への分解が見つけやすい（因数分解））。
- 行列と思うのも、無駄に巨大な行列になって構造が見にくいです。
- 群環の元と思うならば、群は $(\mathbb{Z}/m\mathbb{Z})^3$ です。$e_1 = (1,0,0)$, $e_2 = (0,1,0)$, $e_3 = (0,0,1)$ として、\[f = [e_1] + [-e_1] + [e_2] + [-e_2] + [e_3] + [-e_3] + [e_1+e_2+e_3] + [-e_1-e_2-e_3]\] とおきます。$f^n$ が考察対象で、因数分解 $f = [-e_1-e_2-e_3] (1+[e_1+e_2]) (1+[e_1+e_3]) (1+[e_2+e_3])$。短く書ける分行列よりは良いですが、文字式の方が直感が働きそうですね。
- 2次元の類題 → https://atcoder.jp/contests/arc012/tasks/arc012_4
これも、 因数分解 $x+1/x+y+1/y = (x+y)(1+1/xy)$ からすぐに分かります。（そこよりも、二項係数を一般 mod で計算させているところの方が題意かもしれない）。
