Subsequence Score
a_i の答えへの寄与を調べる
これは、答えが Σ★a_i の形になるので、係数部分を求めるということ
0-indexed で a_0, a_1, ... a_{N-1} とする
a_i より前にある a_0, ..., a_{i-1} から j 個 (0 ≦ j ≦ i) 選んだときは (j + 1) * a_i だけ答えに寄与する
j 個の選び方全てについて和を取る:$ \sum_{j = 0}^{i} (j + 1) {}_iC_j a_i
a_i より後ろにある a_{i+1}, ..., a_{N-1} は自由に選べるから、結局 a_i の答えへの寄与は$ 2^{N-i-1}\sum_{j = 0}^{i} (j + 1) _{i}C_j a_i
シグマ部分を式変形する:$ \sum_{j=0}^i j_{i}C_j + \sum_{j=0}^i \\_{i}C_j
後半は「二項係数 総和」で検索して 2^i
前半は$ \sum_{j=0}^i j _{i}C_j = \sum_{j=1}^i j _{i}C_j = \sum_{j=1}^i i _{i-1}C_{j-1} = i \sum_{j=0}^{i-1} \\_iC_j = i \times 2^{i-1}
以上より答えは$ 2^{N-i-1}(i \times 2^{i-1} + 2^i)a_i = 2^{N-2}(i + 2)a_iを i = 0, 1, ..., N-1 に渡って和を取れば OK
N=1 に注意