Ecasdqina's MEMO

-!=x=!-

ゆふふ．

エイシング プログラミング コンテスト 2020 F - Two Snuke O(1) 解法

tutorial 多項式

O(1) 解法

問題を見た瞬間多項式だと直感したので多項式で問題を表します。

{\displaystyle \begin{eqnarray} \begin{array}{l} f &= {\displaystyle \sum_{u = 0}^{\infty}\sum_{k = 1}^{\infty} kx^{2u + k}} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \sum_{k = 1}^{\infty} kx^k\right)} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \times x\dfrac{d}{dx}\left(\dfrac{1}{1 - x}\right)\right)} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \times \dfrac{x}{(1 - x)^2}\right)} \\ &= {\displaystyle \dfrac{x}{(1 - x)^2} \sum_{u = 0}^{\infty} x^{2u}} \\ &= {\displaystyle \dfrac{x}{(1 - x)^2} \dfrac{1}{1 - x^2}} \\ &= {\displaystyle \dfrac{x}{(1 - x)^3(1+x)}} \end{array} \end{eqnarray} }

上記のように f を定義すると、答えは次のように表せる。

{\displaystyle \begin{equation} [x^N]\dfrac{f^5}{1 - x} = [x^{N - 5}]\dfrac{1}{(1-x)^{16}(1+x)^5} \end{equation} }

さらに、Wolfram Alpha へこの式を突っ込んで部分分数分解すると下のように表せる（1/((1-x)^16(1+x)^5) 部分分数分解 - Wolfram|Alpha）。

\dfrac{1}{(1-x)^{16}(1+x)^5} = 1/(32 (-1 + x)^{16}) - 5/(64 (-1 + x)^{15}) + 15/(128 (-1 + x)^{14}) - 35/(256 (-1 + x)^{13}) + 35/(256 (-1 + x)^{12}) - 63/(512 (-1 + x)^{11}) + 105/(1024 (-1 + x)^{10}) - 165/(2048 (-1 + x)^9) + 495/(8192 (-1 + x)^8) - 715/(16384 (-1 + x)^7) + 1001/(32768 (-1 + x)^6) - 1365/(65536 (-1 + x)^5) + 455/(32768 (-1 + x)^4) - 595/(65536 (-1 + x)^3) + 765/(131072 (-1 + x)^2) - 969/(262144 (-1 + x)) + 1/(65536 (1 + x)^5) + 1/(8192 (1 + x)^4) + 17/(32768 (1 + x)^3) + 51/(32768 (1 + x)^2) + 969/(262144 (1 + x))

負の二項定理を用いると、各項の m 項目を次のように計算することができる。

{\displaystyle \begin{eqnarray} \begin{array}{l} [x^m]\dfrac{1}{(1 + x)^a} &= {\displaystyle (-1)^m\binom{m + a - 1}{a - 1}} \\ [x^m]\dfrac{1}{(1 - x)^a} &= {\displaystyle \binom{m + a - 1}{a - 1}} \end{array} \end{eqnarray} }

よって、部分分数分解した結果の項ごとに N - 5 項目を計算して総和を取ることでこの問題を解くことができる。項数および次数は定数なので、二項係数は定数時間で計算することができる、よって全体でも定数時間で答えることができる。