Ex - No-capture Lance Game Editorial by Nyaan
はじめに、問題自体の解説を読みたい方は、ページ下方の「この問題の解説」から読むことを推奨します。
この問題はフーリエ変換・多次元フーリエ変換・アダマール変換などの変換を理解していると解ける問題です。以下の解説では
- 「通常の畳み込み(多項式の積)」「XOR 畳み込み」は一体どのような原理で動いているのか？
という点を理解して頂けることを目標として、前提知識の解説を行っていきます。
離散フーリエ変換
はじめに離散フーリエ変換の説明から始めていきます。
長さ \(N\) の 離散フーリエ変換 (以下、フーリエ変換) とは、列 \(f_0, f_1, \dots, f_{N-1}\) が入力として与えられたときに、一般項 \(F_k\) が次の式で表されるような列 \(F_0, F_1, \dots, F_{N-1}\) を出力として得る変換をいいます。ここで \(W_N\) (あるいは単に \(W\)) は \(1\) の \(N\) 乗根です。
\[F_k = \sum_{n=0}^{N-1} f_n W_N^{nk}\]
上の式を見てもイメージが掴みづらいと思うので直感的な説明を加えます。フーリエ変換は競技プログラミング的には「多項式の多点評価」とみなすのが一番便利だと思います。この「評価」とは、関数 \(f(x)\) および値 \(a\) がが与えられたときに \(f(a)\) の値を求めるという意味です。すなわち、フーリエ変換を次のように解釈します。
多項式 \(f(x) = f_0 + f_1 x + f_2 x^2 + \dots + f_{N-1} x^{N-1}\) を考えます。
このとき上式の \(F_k\) は \(f(W^K)\) です。よってフーリエ変換とは、 \(f(x)\) が与えられたときに \(f(W^0), f(W^1), \dots, f(W^{N-1})\) を計算する関数と考えられます。
競技プログラミングではフーリエ変換は多項式の畳み込みに利用することが多いので (以下の説明でも言及無しに列 \(f\) を \(f(x)\) とみなす部分が多々あります) 、フーリエ変換をこのような定義で理解しておくと、理論と(競技での)実用の乖離が少なくわかりやすいのではないかと感じています。
また、フーリエ変換の逆変換である逆フーリエ変換は次のように定められます。(この式が逆変換になっていることは、式の \(F_k\) の部分にフーリエ変換の式を代入して両辺が一致することを確かめれば証明できます。)
\[f_n = \frac{1}{N} \sum_{k=0}^{N-1} F_k W_N^{nk}\]
逆フーリエ変換もフーリエ変換と同様に多項式の言葉で解釈すると「多項式の補間」になります。すなわち次の通りです。
多項式 \(f(x) = f_0 + f_1 x + f_2 x^2 + \dots + f_{N-1} x^{N-1}\) を \(N\) 点で評価した値 \(f(W^0), f(W^1),\dots,f(W^{N-1})\) が与えられます。
このとき、多点評価した値から元の関数 \(f(x)\) を補間する関数が逆フーリエ変換です。
長さ \(N\) のフーリエ変換・逆フーリエ変換は 高速フーリエ変換(FFT) と通称されるアルゴリズムを用いて \(\mathrm{O}(N \log N)\) で計算することができます。
特に \(N\) が \(2\) べきのときに定数倍の良いアルゴリズムが存在して広く実用されているため、競技プログラミングで FFT と呼ばれる場合は \(N\) が \(2\) べきの場合を意味することが多いです。
フーリエ変換を利用した畳み込み
次に、競技プログラミングにおけるフーリエ変換の一番の応用先である 畳み込み の説明をします。
畳み込みとは、「\(2\) つの列が入力として与えられたときに、添え字の和が一定となるような組を掛けて足し合わせることで新たな列を作る」という操作です。すなわち、厳密に言うと、列 \(f, g\) および二項演算 \(\circ\) が与えられたとき、
\[h_k = \sum_{i \circ j = k} f_i g_j\]
を満たすような列 \(h\) を出力する操作です。
AtCoder では特に \(\circ\) が \(+\) である場合を一番よく見かけるのではないかと思います。\(\circ\) が \(+\) の場合、
\[h_k = \sum_{i + j = k} f_i g_j\]
となりますが、ここで \(f, g, h\) の母関数 \(f(x) = \sum_i f_i x^i, g(x) = \sum_j g_j x^j, h(x) = \sum_k h_k x^k\) を考えると
\[h(x) = f(x) g(x) \]
が成り立ちます。すなわち、\(\circ\) が \(+\) の場合の畳み込みは多項式の積になるということです。
他の種類の畳み込み, 及びそれに関連する問題は ABC-Ex(H) で何問か出題されています。例を挙げると次の通りです。
- \(\circ\) が bitwise xor である場合：XOR 畳み込み (関連：ABC212H)
- \(\circ\) が bitwise or / and である場合：OR 畳み込み, AND 畳み込み(関連:ABC220H)
- \(\circ\) が \(\times\) である場合：ディリクレ畳み込み (関連：ABC239Ex)
- その他：Concave Max Plus convolution (関連：ABC218H)
いずれの出題例も 「愚直に畳み込むと \(\mathrm{O}(N^2)\) かかるが、うまく工夫することで \(\mathrm{o}(N^2)\) に計算量を落とす」という計算量改善の部分がテーマの 1 つになっています。また、その他の畳み込みの例は noshi91 氏による “畳み込めるものまとめ” にある程度まとまっています。
通常の畳み込み(多項式の積)は フーリエ変換を利用すると \(N = \deg(f) + \deg(g)\) として \(\mathrm{O}(N \log N)\) で計算できます。どのような方法で畳み込めるのかを見てみましょう。
以下では長さ \(N\) のフーリエ変換を意味する関数を \(\mathcal{F}_N\) (あるいは単に \(\mathcal{F}\)) 、逆変換を \(\mathcal{F}_N^{-1}\) と表します。また、列 \(f=(f_0, f_1, \dots, f_{N-1}), g=(g_0, g_1, \dots, g_{N-1})\) が与えられたときに \(f \ast g\) を次のように定めます。(\(f \ast g\) は「各点積」と呼ばれることが多い演算です。)
\[(f \ast g) = (f_0 g_0, f_1 g_1, \dots, f_{N-1} g_{N-1})\]
突然ですが、次のような変換によって列 \(f, g\) から列 \(h\) を得ることを考えてみましょう。
\[h = \mathcal{F}^{-1} (\mathcal{F}(f) \ast \mathcal{F}(g))\]
さて、この操作によって得られる \(h\) と \(f, g\) の間にはどのような関係があるでしょうか？
まずは簡単な例、\(N=2\) の場合で考えてみましょう。
\(f = (f_0, f_1)\) と \(g = (g_0, g_1)\) がある。
\[h = \mathcal{F}^{-1} (\mathcal{F}(f) \ast \mathcal{F}(g))\]
を満たす \(h\) はどのような値か？
長さ \(2\) のフーリエ変換 \(\mathcal{F}(f)\) は \(f(x)\) から \(f(W^0), f(W^1)\) を得る操作でした。よって次のような関係が成り立ちます。
\[\mathcal{F}(f) \ast \mathcal{F}(g) = (f(W^0) g(W^0), f(W^1)g(W^1))\]
この両辺に \(\mathcal{F}^{-1}\) を作用させれば \(h\) になります。逆フーリエ変換は \(\mathcal{F}^{-1}(F)\) は \(F_ 0 = f(W^0),F_1 = f(W^1)\) から元の多項式 \(f_0 + f_1 x\) を復元する操作でした。
よって、\(h\) を求める問題を多項式の言葉に直すと次のようになります。
\(h(W^0) = f(W^0)g(W^0), h(W^1) = f(W^1)g(W^1)\) であるような \(1\) 次式 \(h\) を求めよ。
\(1\) 次式という条件を無視すると、高校数学で学んだ 剰余の定理 を思い出せば多項式 \(h(x)\) は次の式で一般項が表せるのが示せます。
- \(h(x) = f(x) g(x) + C(x)(x - W^0)(x - W^1)\), \(C(x)\) は任意の多項式
\(N=2\) のとき \(W_2=-1\) なので上の式は整理すると次のように書けます。
\[h(x) = f(x) g(x) + C(x) (x^2 -1)\]
よって、\(h\) は \(1\) 次式であるという条件を加味すると、\(h(x)\) は \(f(x)g(x)\) を \(x^2-1\) で割ったあまり、すなわち以下の式で表せることが分かります。
\[h(x) = f(x) g(x) \bmod{(x^2 - 1)}\]
よって、\(N=2\) の場合の \(h\) は
\[ \begin{aligned} h(x) &= f(x) g(x) \bmod{(x^2 - 1)}\\ &= (f_0 + f_1 x)(g_0 + g_1 x) \bmod{(x^2-1)} \\ &= (f_0 g_0 + f_1 g_1) + (f_0 g_1 + f_1 g_0) x \end{aligned} \]
になることがわかりました。
長さ \(N\) が一般の場合も同様の議論が成り立ちます。剰余の定理より \(h\) に関して次の式が立って (\(C(x)\) は任意の多項式)、
\[h(x) = f(x) g(x) + C(x)\prod_{i=0}^{N-1}(x-W_N^i)\]
第 2 項の \(\prod_{i=0}^{N-1}(x-W_N^i)\) の部分は
\[\prod_{i=0}^{N-1}(x-W_N^i) = x^N - 1\]
なのが証明できるので、
\[h(x) = f(x) g(x) \bmod{(x^N - 1)}\]
という関係式を得ることができます。(ここでの \(\bmod\) は C++ の % に相当する二項演算の mod です。)
右辺の \(\bmod{(x^N - 1)}\) という部分を深掘りしてみましょう。
\[x^{i + N} \equiv x^i \pmod{x^N - 1}\]
なので、「\(x^N - 1\) で剰余を取る」という操作は、「\(x^d, d \geq N\) である項が存在する限り、その項の係数を \(x^{d-N}\) に足して項を消す」という操作に読み替えられます。よって、\(h(x) = f(x) g(x) \bmod{(x^N - 1)}\) を満たす \(h(x)\) を列として表現すると、各要素は
\[h_k = \sum_{i + j \equiv k \pmod{N}} f_i g_j\]
という畳み込みの式で表せます。このような \(\mod N\) 上の加法上の畳み込みを「周期 \(N\) の 巡回畳み込み 」と呼びます。
まとめ：周期 \(N\) の巡回畳み込み
長さ \(N\) の列 \(f, g\) が与えられる。
\[h = \mathcal{F}_N^{-1} (\mathcal{F}_N(f) \ast \mathcal{F}_N(g))\]
によって得られる (すなわち \(f, g\) をフーリエ変換して各点積を取って逆フーリエ変換することによって得られる)列 \(h\) は、次の関係式を満たす。
\[h_k = \sum_{i + j \equiv k \pmod{N}} f_i g_j\]
\(f, g\) から \(h\) を得る操作を 「周期 \(N\) の巡回畳み込み」と呼ぶ。
例えば \(f(x) = 1 + 2x^2, g(x) = 1 + 2x + 3x^2\) を周期 \(3\) で巡回畳み込みすると \(h(x) = 5 + 8x + 5x^2\) を得ます。これを手計算で求めたい場合は、次のような画像の筆算によって求められます。
- このように、周期 \(N\) の巡回畳み込みは、俗な言い方をすると、「\(N\) 次以上の項をちぎって下位の項と足し合わせる」というイメージで理解できると思います。
さて、巡回畳み込みを利用して通常の多項式の積 \(h(x) = f(x) g(x)\) を計算してみましょう。
上の図のイメージでもわかる通り、巡回畳み込みはくだけた言い方をすると「\(h\) は \(N\) 次以上の項があると変なことが起こる、多項式の積」という感じになります。よって、周期 \(N\) が \(\deg(f) + \deg(g)\) よりも大きければ、変なことは起こらず、通常の多項式の積になるわけです！
よって、次のアルゴリズムによって多項式の積を \(\mathrm{O}(N \log N)\) で計算することができます。
多項式の積を計算するアルゴリズム
入力：\(f, g\)
出力：\(h\), s.t. \(h_k = \sum_{i+j=k} f_i g_j\)
- \(|f| + |g| - 1\) 以上の整数 \(N\) を取る。
- 長さ \(f\) の列の次数は \(|f|\) ではなく\(|f| - 1\) なのに注意してください。
- \(f, g\) を長さ \(N\) になるようゼロ埋めする。
- FFT を用いて、\(f, g\) の周期 \(N\) の巡回畳み込み \(h'\) を得る。
- \(h'\) の先頭 \(|f| + |g| - 1\) 項を \(h\) とする。
実装例として AtCoder Library の該当箇所を引用します。ここで internal::butterfly は離散フーリエ変換, internal::butterfly_inv は逆離散フーリエ変換(の最後に \(\frac{1}{N}\) 倍をしないバージョン)に相当する関数です。
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
多次元フーリエ変換・多次元畳み込み
(この項は執筆中で、後日掲載される見込みです。)
XOR 畳み込みとアダマール変換
XOR 畳み込みとは、長さ \(2^n\) の列 \(f, g\) から次の式を満たす長さ \(2^n\) の列 \(h\) を得る畳み込みです。 (\(\oplus\) は bit ごとの排他的論理和)
\[h_k = \sum_{i \oplus j = k} f_i g_j\]
競技プログラミングの文脈では、XOR 畳み込みはフーリエ変換とは独立に理解されることが多い印象がありますが、実は XOR 畳み込みは多次元フーリエ変換を利用した畳み込みです。
いったんの長さ \(2\) の巡回畳み込みの話に戻りましょう。
長さ \(2\) の列 \(f = (f_0, f_1), g = (g_0, g_1)\) の巡回畳み込みによって得られる列は
\[h = (f_0 g_0 + f_1 g_1, f_0 g_1 + f_1 g_0)\]
でした。この \(h\) はよく見ると
\[h_k = \sum_{0 \leq i \lt 2, 0 \leq j \lt 2, i \oplus j} f_i g_j\]
になっています。つまり長さ \(2\) の巡回畳み込みは 1 bit 版の XOR 畳み込みになるのです！
bitwise xor は当然ビットごとに独立なので、長さ \(2\) の巡回畳み込みを \(n\) 次元に拡張したものは \(n\) bit の XOR 畳み込みになります。
この長さ \(2\), \(n\) 次元の離散フーリエ変換には アダマール変換(ウォルシュ・アダマール変換) という名前がついていて、こちらの名前の方が広く知られていると思います。
アダマール変換の一般的な実装例は次の通りです。実装を凝視すると、処理が多次元 FFT と一致しているのが確認できると思います。
template <typename T>
void walsh_hadamard_transform(vector<T>& f, bool inverse = false) {
int n = f.size();
for (int i = 1; i < n; i <<= 1) {
for (int j = 0; j < n; j++) {
if ((j & i) == 0) {
T x = f[j], y = f[j | i];
f[j] = x + y, f[j | i] = x - y;
}
}
}
if (inverse) {
T invn = T{1} / T{f.size()};
for (auto& x : f) x *= invn;
}
}
この問題の解説
さて、これで道具は一通りそろったので、問題の解説をはじめましょう。
まず、全ての香車を並べ終わった状態が与えられたときに、その盤面が先手勝ちである条件を考えてみましょう。
各行ごとに、その行の状態に対応する評価値を次のように定義します。
先手の香車が \((i, j)\), 後手の香車が \((i, k)\) におかれているとする。このとき、\(i\) 行目の評価値となる値の組 \((s_i, g_i)\) を次のように定義する。
- \(k \lt j\) のとき : \((s_i, g_i) = (0, j - k - 1)\)
- \(k \gt j\) のとき：\((s_i, g_i) = ((j-1) - (W-k), 0)\)
そして、ゲーム全体の評価値 \((S, G)\) を次のように定義します。
\[(S, G) = (\sum_{i=1}^H s_i, \bigoplus_{i=1}^H g_i)\]
このとき、盤面が先手勝ちである条件は次の式で表せます。
\[(\text{先手勝ち}) \iff (S \gt 0) \vee \left\lbrace (S = 0) \wedge (G \gt 0) \right\rbrace\]
正当性は丁寧に議論すれば証明できますが、 \(s_i, g_i\) がそれぞれ非不偏ゲームの評価値に使われる超現実数 (Surreal Number) , および不偏ゲームの評価値に使われる Grundy 数に対応している事実からも確認できます。(超現実数の解説は ABC229-H を参照ください。)
この事実を元にナイーブな DP を行えば \(\mathrm{O}(H^2 W^3)\) でこの問題を解くことができます。さらに、 第 \(1\) 軸で通常の畳み込み, 第 \(2\) 軸で XOR 畳み込みを行う 2 次元畳み込みを利用すれば \(\mathrm{O}(HW^2 \log (HW))\) に高速化することができます。
- これは \(\left\lceil \log_2{W} \right\rceil + 1\) 次元 FFT を利用した畳み込みと解釈できるので、今までに説明した内容をそのまま適用すれば実装できます。
なお、問題の性質に注目してより丁寧に考察を進めると \(\mathrm{O}(HW \text{poly}(\log(HW)))\) 程度の計算量で解くこともできますがここでは割愛します。
posted:
last update: