Ex - Flipping Coins 2 Editorial by nok0
解説目次
Multipoint Evaluation の解説
問題の言い換え
包除原理の適用
\(\mathrm{O}(N^2)\) 解法
\(\mathrm{O}(N\log^2 N)\) 解法
[1] Multipoint Evaluation
はじめに、この問題を解くのに必要な Multipoint Evaluation（多点評価）と呼ばれるテクニックの概要を説明します。
Multipoint Evaluation とは？
\(N\) 次多項式 \(f(x)\) と長さ \(M\) の整数列 \(x=(x_1,x_2,\ldots,x_M)\) にたいし、\(f(x_1),f(x_2),\ldots,f(x_M)\) を求めるのを \(\mathrm{O}(M\log^2M + N\log N)\) で行うテクニックです。
剰余の定理を使います。 \(f(a)=f(x)\bmod(x-a)\) を用いると、 \(f(x) \bmod(x-x_1),f(x)\bmod(x-x_2),\ldots,f(x)\bmod(x-x_M)\) が求まれば良いです。
これは分割統治が適用できます。はじめに、subproduct tree と呼ばれる二分木を葉から構築していきます。葉には \((x-x_1),(x-x_2),\ldots,(x-x_M)\) を書き、その一段上には子二つの積、すなわち \((x-x_1)(x-x_2),(x-x_3)(x-x_4),\ldots\)を書き、… というのを繰り返します。
次に、多項式 \( f,g,h\) にたいして \(f\bmod g = (f\bmod gh) \bmod g\) であることを用いて、subproduct tree を使いながら計算を行います。
subproduct tree の根を用いて、まず \(f \bmod\big((x-x_1)(x-x_2)\ldots(x-x_M)\big)\) を計算します。次に、その計算結果及び subproduct tree の根の子を用いて \(\big(f \bmod\big((x-x_1)(x-x_2)\ldots(x-x_M)\big)\big) \bmod \big((x-x_1)(x-x_2)\ldots(x-x_\frac{M}{2})\big)\) を計算します。（簡単のため、 \(M\) が二冪であるとしています。）
subproduct tree 上で根から葉にかけてこのような計算をすることで、\(f(x) \bmod(x-x_1),f(x)\bmod(x-x_2),\ldots,f(x)\bmod(x-x_M)\) が全て計算できます。計算量解析については省略しますが、\(\mathrm{O}(M\log^2M + N\log N)\) になります。
より詳しくは、以下に挙げる参考文献をご覧ください。
37zigen さん Multipoint Evaluation の アルゴリズム
えびちゃん さん 非再帰で多項式の多点評価をするよ
[2] 問題の言い換え
以下、この問題の解説を行います。
\(A\) は昇順であると仮定して問題ありません。
はじめに、対称性よりどのコインも \(N\) 回の操作終了時に表である確率は等しいので、 コイン \(N-1\) が操作終了時に表である確率が求まれば良いです。
証明
$p$ を rotate すると、各コインのひっくり返る回数も rotate することから従います。
コイン \(N-1\) がちょうど \(K\) 回ひっくり返されるような順列の個数を \(F(K)\) として、 \(K=0,1,\ldots,N\) について \(F(K)\) が求まればよいです。
\(F(K)\) は、\(P_i \geq N-1-A_i\) を満たす \(i\) の個数がちょうど \(K\) 個であるような順列 \(P\) の個数と等しいです。便利のため、 \(B_i = N-1-A_i\) とします。このとき \(B\) は単調減少になります。
[3] 包除原理の適用
[2] で述べた \(F(K)\) は直接求めるのは難しいです。\(\lbrace 1,2,\ldots,N\rbrace\) の部分集合 \(S\) であって \(|S|=L\) を満たすもの全てに対して、
- \(i \in S \Rightarrow P_i \geq B_i\)
を満たす順列 \(P\) の個数を求め、その総和を \(G(L)\) とおくことにします。
このとき、 \(F\) と \(G\) には以下の関係式が成り立ちます。
\(\displaystyle G(L)=\sum_{L \leq K} \binom{K}{L}F(K)\)
上記の関係式を用いれば、\(G\) が求まれば \(F\) を復元できます。なお、この復元の部分はARC140-Fでも出ていますので、適宜そちらの解説も参考にしてください。
\(a_i = (N-i)!G(N-i), b_i = (N-i)!F(N-i)\) と置き、その母関数を \(a(x),b(x)\) とします。
このとき \(a_{i} = \sum_{j =0} ^ {i} b_j\frac{1}{(i-j)!} \) です。このことより \(a(x)=b(x)e^{x}\) と表せるので、\(b(x)=a(x)e^{-x}\) から \(\mathrm{O}(N\log N)\) で \(F\) を求められます。
以下 \(G\) を求めることとします。
[4] \(\mathrm{O}(N^2)\) 解法
\(G\) は以下のような動的計画法で求められます。
- \(\mathrm{dp}[i][j]:\) 順列 \(P\) のうち先頭の \(i\) 個の index まで見て、意図的に \(P_i \geq B_i\) を満たす \(i\) の個数が \(j\) 個であるような決め方の個数
この dp の遷移を考えます。
\(i\) で意図的に \(P_i \geq B_i\) を満たすようにするとき
- \((N-B_i-(j-1))\mathrm{dp}[i-1][j-1]\) 通り
\(i\) で意図的に \(P_i \geq B_i\) を満たすようにはしないとき
- \(\mathrm{dp}[i-1][j]\) 通り
よって遷移は以下で表されます。
\(\mathrm{dp}[i][j] = (N-B_i-(j-1))\mathrm{dp}[i-1][j-1]+ \mathrm{dp}[i-1][j]\)
最終的に、 \(G(K) = \mathrm{dp}[N][K] (N-K)!\) と求められます。
計算量は \(\mathrm{O}(N^2)\) であり、実行時間に間に合わせるのは極めて困難です。
なお、この動的計画法は俗に箱根駅伝DPと呼ばれています。
箱根駅伝DP の練習問題
[5] \(\mathrm{O}(N\log^2N)\) 解法
[4]での dp を、形式的冪級数で考えることとします。
はじめに、 \(\mathrm{dp2}[i][i-j] \coloneqq \mathrm{dp}[i][j]\) とします。（この式変形をする嬉しさは、後ほどわかります）
このとき
\(\mathrm{dp2}[i][j] = (N-B_i-(i-j-1))\mathrm{dp2}[i-1][j]+ \mathrm{dp2}[i-1][j-1] = (N-B_i + 1 -i+ j)\mathrm{dp2}[i-1][j]+ \mathrm{dp2}[i-1][j-1]\)
が成り立ちます。
さらに \(f_i(x)\) を \(\mathrm{dp2}[i]\) の母関数とし、簡単のため \(C_i \coloneqq N-B_i +1-i\) と定めます。
このとき、\(f_i(x)\) の関係式は以下となります。
\[f_i(x) = C_i f_{i-1}(x) +xf'_{i-1}(x) +xf_{i-1}(x)=x(f_{i-1}(x)+f'_{i-1}(x)) + C_i f_{i-1}(x)\]
唐突ですが、両辺に \(e^x\) をかけてみます。
\[f_i(x)e^x = x(f_{i-1}(x)e^x+f'_{i-1}(x)e^x) + C_i f_{i-1}(x)e^x = x(f_{i-1}(x)e^x)' + C_i f_{i-1}(x)e^x\]
\(g_i(x) \coloneqq f_i(x)e^x\) とおけば、\(g_i(x)=xg'_{i-1}(x)+C_i g_{i-1}(x)\) を得ます。\([x^j]g_i(x)\) を \(g_{i,j}\) と書くと、\(g_{i,j}=jg_{i-1,j}+C_i g_{i-1,j} = (j + C_i) g_{i-1,j}\) です。
以上より \(g_{N,j} = g_{0,j}\prod_{i=1}^N(j + C_i)\) が得られます。ここまでくると、[1]の多点評価が適用できる形になります。
多項式 \(h\) を \(h(x)=\prod_{i=1}^N(x+ C_i)\) で定めると、\(j=0,1,\ldots,N\) を \(h\) に代入すれば \(\prod_{i=1}^N(j + C_i)\) が全ての \(j\) について得られます。多点評価により \(\mathrm{O}(N\log^2N)\) で \(g_{N,j}\) が列挙でき、\(g_N(x)\) が求まりました。\(g_N(x)\) に \(e^{-x}\) を掛けることで \(f_N(x)\) も求まり、ここから \(G(K)\) も求まります。
以上より、この問題を \(\mathrm{O}(N\log^2N)\) で解くことができました。
posted:
last update: