Ecasdqina's MEMO

-!=x=!-

ゆふふ．

yukicoder No.1325 Subsequence Score 解説

yukicoder tutorial

公式解説では各添字の値についての寄与について、それより左側のものが選ばれるたびに加算するという言い換えを用いていた。それに対して、ぼくはその添字が k 番目に選ばれる場合について考え、 k についての総和を取ることで解いたので、それについて書く。

解説

いま、添字 i(0 \le i < n) について考えているとする（かんたんのため 0-indexed とする）。この寄与は以下の式で表される。

\begin{equation} \displaystyle a_i2^{n - i - 1}\sum_{k = 0}^i (k + 1)\binom{i}{k} \end{equation}

総和の中身をかんたんな式に変形したい、以下のように多項式を変形することで総和の単純な式を導出できる。

\begin{align} x(1 + x)^i &= \sum_{k = 0}^i \binom{i}{k}x^{k + 1} \\ \dfrac{dx(1 + x)^i}{dx} &= \sum_{k = 0}^i (k + 1)\binom{i}{k}x^k = (1 + x)^i + ix(1 + x)^{i - 1} \\ \sum_{k = 0}^i (k + 1)\binom{i}{k} &= 2^i + i2^{i - 1} = (2 + i)2^{i - 1} \end{align}

よって以下の値が答え。

\begin{equation} \displaystyle \sum_{i = 0}^{n - 1} a_i2^{n - 2}(2 + i) \end{equation}