yukicoder No.1325 Subsequence Score - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

長さ ${N}$ の整数列 ${A}$ が与えられる. ${A}$ の部分列 ${B}$ におけるスコアを ${\sum_{i=1}^{|B|}(i×B_i)}$ と定義する. ${B}$ としてあり得るすべての数列のスコアの総和を求めよ.

${1\leq N\leq 5×10^5\\ 1\leq A_i\leq 10^9}$

思考の流れ

${B}$ を全て列挙するのは無理なので ${j×A_i}$ の寄与分を考えると, ${A_1}$ から ${A_{i-1}}$ までで ${j-1}$ 個選び ${A_{i+1}}$ 以降は好きに選ぶような方法の数は ${\binom{i-1}{j-1}2^{N-i}}$ なので求める答えは
${\begin{array}{} \displaystyle \sum_{i=1}^{N}\sum_{j=1}^{i}\binom{i-1}{j-1}×2^{N-i}×j×A_i\\ =\displaystyle \sum_{i=1}^{N}\sum_{j=1}^{i}\frac{(i-1)!}{(j-1)!(i-j)!}×2^{N-i}×j×A_i\\ =\displaystyle \sum_{i=1}^{N}\left(A_i×(i-1)!×2^{N-i}×\sum_{j=1}^{i}\left(\frac{j}{(j-1)!}×\frac{1}{(i-j)!}\right)\right)\\ =\displaystyle \sum_{i=1}^{N}\left(A_i×(i-1)!×2^{N-i}×\sum_{s+t=i-1}\left(\frac{s+1}{s!}×\frac{1}{t!}\right)\right)\\ \end{array}}$

すべての ${i}$ について ${\displaystyle\sum_{s+t=i-1}\left(\frac{s+1}{s!}×\frac{1}{t!}\right)}$ はNTTを用いて ${O(N\log{N})}$ で計算できる.

${\downarrow}$

また, (形式的冪級数的に)
${\displaystyle (x+1)e^x = \sum_{i=0}^{\infty}\frac{i+1}{i!}x^i\\ \displaystyle e^x = \sum_{i=0}^{\infty}\frac{1}{i!}x^i\\ \displaystyle (x+1)e^{2x}=xe^{2x}+e^{2x}=1+\sum_{i=1}^{\infty}\left(\frac{2^i}{i!}+\frac{2^{i-1}}{(i-1)!}\right) x^i\\}$
なので
${\begin{array}{} & \displaystyle \sum_{i=1}^{N}\left(A_i×(i-1)!×2^{N-i}×\sum_{s+t=i-1}\left(\frac{s+1}{s!}×\frac{1}{t!}\right)\right)\\ =& \displaystyle 2^{N-1}A_1 + \sum_{i=2}^{N}\left(A_i×(i-1)!×2^{N-i}×\left(\frac{2^{i-1}}{(i-1)!}+\frac{2^{i-2}}{(i-2)!}\right)\right)\\ =& \displaystyle 2^{N-1}A_1 + 2^{N-2}\sum_{i=2}^{N}(i+1)A_i\\ =& \displaystyle 2^{N-2}\sum_{i=1}^{N}(i+1)A_i\\ \end{array}}$
となり, 公式解説と同じ式になる.

提出プログラム

https://yukicoder.me/submissions/596648 (NTT解)

感想

むずくね？形式的冪級数までが無理やり感あるのでいい感じのやつ思いついたら更新します.