H - Nim Counting Editorial by Nyaan
別解：DPの高速化
上の解説では \(M = 2^{16} \geq \max(A)\) として \(\mathrm{O}(M(\log M + \log N) )\) 解法を紹介していますが、ここではもう \(1\) つの想定解として DPの高速化 による\(\mathrm{O}(M \log M \log N )\) 解法の解説を行います。 また、石取りゲーム (Nim) の勝利条件の関する知識はすでに持っていると仮定します。
ナイーブな DP
まず、愚直な解法として次の DP を考えます。
- \(dp(i, j) := \) 山 \(i\) まで石の個数が確定していて、石の個数の xor が \(j\) である場合の数
するとこの DP は、山 \(i\) の石の個数で場合分けを行うと次の遷移で計算できます。 ( \(\oplus\) は xor (排他的論理和) を意味する記号です。 )
\[ dp(i, j) = \begin{cases} 1 & i = 0, j = 0 \\ 0 & i = 0, j \neq 0 \\ \displaystyle \sum_{a \in A} dp(i-1,j \oplus a) & \mathrm{otherwise} \end{cases} \]
求める答えは、山の個数 \(i\) が \(1 \leq i \leq N\) で、排他的論理和 \(j\) が \(0\) でない場合の \(dp(i, j)\) を全て足したものになります。
この DP により \(\mathrm{O}(N M K)\) で答えを求めることができますが、これでは実行時間には間に合いません。 \(N,M,K\) はいずれも \(10^5\) 程度なので、ここから \(N,M,K\) の 3 つのうち 2 つの実行時間への寄与を線形より高速にする必要があります。
xor 畳み込みを利用した高速化
xor 畳み込み (xor convolution) とは、 2 つの長さ \(M\) の列 \(f, g\) があった時に
\[ h_k = \sum_{i \oplus j = k} f_i \times g_j\]
を満たす長さ \(M\) の列 \(h\) を計算することを言います。 これはアダマール変換を利用すると \(\mathrm{O}(M \log M)\) で高速に計算できることが知られています。 ( アダマール変換に関する解説はここでは割愛します。詳しくは実装をお読みください。 )
上記のDP は xor 畳み込みを利用すると計算量から \(K\) を落とすことが出来ます。より具体的には、 DP を \(1\) 行ごとに遷移する式に変形することで xor 畳み込みを適用できる形になります。
列 \(F(i)\) を長さ \(M\) の 0-indexed の列 \( (dp(i,0), dp(i, 1), \dots, dp(i, M-1) )\) として定めます。
また、列 \(G\) を \(a\)が\(A\) に入っているときは \(a\) 番目の要素が \(1\) で、それ以外の場合は \(a\) 番目の要素が \(0\) である列として定めます。すると\(i \leq 0\) に対して
\[F(i+1)_u = \sum_{s \oplus t = u} F(i)_s \times G_t\]
と表せて、 xor畳み込みを利用すれば \(F(i)\) から \(F(i+1)\) を \(\mathrm{O}(M \log M)\) でまとめて計算することが出来ます。
これで計算量は \(\mathrm{O}(N M \log M)\) まで落とせましたがこれではまだ速度が足りません。xor 畳み込みを使うと \(M\) は計算量から落とせなさそうなので、次は \(N\) を落とす方法を考えてみましょう。
二分累乗法を利用したさらなる高速化
上記の DP は \(F(0)\) に \(G\) を \(\mathrm{O}(N)\) 回畳み込み続けるという DP を行っています。このような単純な構造の DP では 二分累乗法 を利用した高速化を適用すると、遷移の回数を \(\mathrm{O}(\log N)\) 回に抑えることができます。
長さ \(M\) の列 \( S(i) \) を次のように定めます。
- \(S(i)_j :=\) 山の個数が \(1\) 個以上 \(i\) 個以下で、石の個数の xor が \(j\) である場合の数
このとき\(S(i)\) は \(F(1),\dots,F(i)\) の和として表せます。より厳密には、
\[S(i)_j = \sum_{s=1}^i F(s)_j\]
が成り立ちます。また、このとき答えは \(\sum_{j=1}^{M-1} S(N)_j\) になります。
ここで二分累乗法の成立条件を振り返ると、次の 2 つの遷移を高速に計算できればよいとわかります。
- \(S(k), F(k) \to S(k + 1), F(k + 1)\)
- \(S(k), F(k) \to S(2k), F(2k)\)
考えます。もしもこの 2 つが高速に計算できれば、二分累乗(繰り返し自乗法)の要領で \(S(N), F(N)\) を \(\mathrm{O}(\log N)\) で計算できます。
前者は今までの DP を利用すると高速に計算できるので後者を考えます。 これは \(S(2k), F(2k)\) を
- 「 山 \(1\) から 山 \(k\) の石の置き方の場合の数」\(\times\) 「 山 \(k+1\) から 山 \(2k\) の石の置き方の場合の数」
と解釈すると \(F(k), S(k)\) の係数の積に分割することが出来るので、次の式が成り立つことが示せます。
\[S(2k)_u = S(k)_u + \sum_{s \oplus t = u} S(k)_s \times F(k)_t\]
\[F(2k)_u = \sum_{s \oplus t = u} F(k)_s \times F(k)_t\]
以上の式を利用して二分累乗法を行うことで、遷移 1 回あたり \(\mathrm{O}(M \log M)\) の遷移を \(\mathrm{O}(\log N)\) 回行うことで \(S(N)\) を計算することができました。計算量は全体で \(\mathrm{O}(M \log M \log N)\) となり十分高速に計算することができます。
posted:
last update: