主客転倒について

※本稿を執筆しているのは競プロ初心者であるため、読みづらかったり間違いを含んでいる可能性があります。ご了承下さい。またABCの過去問のネタバレを含んでいます。

競プロの問題の典型に、盤面に対してコストが設定されるときあらゆる盤面に対してコストを計算しその和を出力せよ、というものがある。例えば以下のような問題。

例題

長さ$N$の数列$A=(a_1,a_2,…,a_n)$が与えられる。うぇかりー君は数列から連続した部分列を選ぶのが好きであり、数列$A$から$a_l,a_{l+1},…,a_r$を選んだときうぇかりー君の喜び度は$\sum_{i=l}^r a_i$と定義される。数列$A$のあらゆる連続した部分列の選び方に対してうぇかりー君の喜び度を計算しその和を$10^9+7$で割った余りを出力せよ。

制約

$1{\leq}N{\leq}10^5,1{\leq}a_i{\leq}10^5$

例題に対する入力として$N=3,A=(1,2,3)$が与えられたとすると、$A$に対する連続した部分列の選び方は$(1,2,3)$、$()$(何も選ばない)、$(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$で全てであり、答えは$6+0+1+2+3+3+5=20$となる。
長さに関する制約から選び方をすべて列挙して計算するのは$O(N^2)$かかって厳しい。なので、かわりに$a_i$を含む連続する部分列の選び方が何通りあるかを数える。$a_i$が含まれる連続する部分列の個数は$i\times{(N-i+1)}$個であるので、答えのコストのうち$a_i$が選ばれることによるコストは$i\times{(N-i+1)}\times{a_i}$となる。よって例題の答えは以下のコードで計算出来る。(入力は省略)

const int MOD = 1e9+7;
long long ans = 0;
int n;
vector<long long> a(n);
for(int i = 0;i < n;i++){
　ans += a[i] * (i+1) % MOD * (n-i) % MOD;
　ans %= MOD;
}
cout << ans << endl;

答えに含まれる回数などを数え上げることで計算量をへらすのは典型でABCの過去問にもちょこちょこあったりするので、なんとなく覚えておくといいかもしれません。
類題:ABC058-E ABC127-E