\(R\) を環とします。 正整数 \(n\) に対して \(f_n(x) \in R[[x]]\) を定数項が \(0\) であるような形式的冪級数とします。 このとき、以下の式が成り立ちます。

\[ \sum_{A \in \mathbb{N}^*} \prod_{i=1}^{|A|} f_{A_i}(x) = \frac{1}{1 - {\displaystyle \sum_{n \in \mathbb{N}} f_n(x)}} \]

一方、ランレングス圧縮した列が一致する \(A\) たちについてまとめて和を取ることを考えると、以下の式を得ます。

\[ \sum_{A \in \mathbb{N}^*} \prod_{i=1}^{|A|} f_{A_i}(x) = \sum_{B \in \mathcal{D}} \prod_{i=1}^{|B|} \frac{f_{B_i}(x)}{1 - f_{B_i}(x)} \]

ここで、\(\mathcal{D}\) は隣り合う \(2\) 要素が相異なるような \(\mathbb{N}\) の列全体です。

この式を逆向きに利用します。 正整数 \(n\) に対して \(g_n(x) \in R[[x]]\) を定数項が \(0\) であるような形式的冪級数としたとき、\(\frac{f_n(x)}{1 - f_n(x)} = g_n(x)\) を満たす \(f_n(x)\) をとれば

\[ \sum_{B \in \mathcal{D}} \prod_{i=1}^{|B|} g_{B_i}(x) = \frac{1}{1 - {\displaystyle \sum_{n \in \mathbb{N}} f_n(x)}} \]

です。 本問題では \(R = \mathbb{F}_p[t] / (t^2), ~ g_n(x) = (1+t)x^n\) として上の式の \(t^1 x^N\) の係数を計算すればよいです。 \(f_n(x) = \frac{g_n(x)}{1+g_n(x)} = \sum_{k=1}^{\infty} -(1+kt)({-x}^{n})^{k}\) より、\(\sum f_n(x)\) は \(\mathrm{O}(N \log(N))\) で \(N\) 次まで計算できます。 \((h_0 + h_1 t)^{-1} = h_0^{-1} - h_0^{-2}h_1 t \pmod {t^2}\) であるため結局、\(\mathbb{F}_p\) 上の形式的冪級数の逆元を計算することで答えが求まります。

追記: \(g_n(x, y) = x^n y\) とすると公式解説と同じ式が得られ、合流します。