Official

E - Eternal Dice Editorial by maroonrk_admin


この解説では厳密性を気にしません.また,重要な式も証明しません.

まずこちらをご覧ください. これを見ると,この問題は,\(\left(\frac{\sin(\pi \sqrt{1-x})}{\pi \sqrt{1-x}}\right)^A\)\(N\) 次の係数を求める問題だとわかります.

別の言い方をすると,上の式を \(N\) 回微分して \(x=0\) を代入した値が知りたいです. そのためには,\(\left(\frac{d}{dx}\right)^N \left(\frac{\sin(\sqrt{x})}{\sqrt{x}}\right)^A\)\(x=\pi^2\) を代入した値が分かればよいです.

\(f=\sin(x)^A\) とおき,\(\left(\frac{d}{dx}\right)^N \frac{f(\sqrt{x})}{\sqrt{x}^A}\) を求めることを考えます. \(f_i(x):=\left(\frac{d}{dx}\right)^i f(x)\) と定義します. すると,ある有理数列 \(c_{A,i}\) を用いて,\(\left(\frac{d}{dx}\right)^N \frac{f(\sqrt{x})}{\sqrt{x}^A}=\frac{1}{2^N} \sum_{0 \leq i \leq N} (-1)^i \times c_{A,i} \times f_{N-i}(\sqrt{x}) \times \sqrt{x}^{-(A+2i+(N-i))}\) とかけます. この \(c_{A,i}\) を,\(A,i\) を動かしてテーブルを作って眺めると,\(c_{A,i}=c_{A-1,i}+c_{A,i-1}\times (N-i+1)\) という関係性が見えます.これは頑張ると証明できます. また,\(c_{1,i}\) の値は,OEIS に入れると一般項が出てきます.これも頑張ると証明できます. 以上を合わせると,畳み込みを使うことで,\(c_{A,i}\) の値を効率よく求められます.

\(f_i(\pi)\) の値も,多項式の pow を使うことで高速に計算できます. これらの計算は,すべて \(O(N\log N)\) または \(O(N \log^2N)\) で行えます.

posted:
last update: