問題概要
$N$ 項からなる整数列 $\{ A_i \}$ が与えられる.valid な $i, j$ ($i < j$) についての $\sum A_i A_j$ の値を求めよ.
制約
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$
解法
$j$ を固定した場合の答えへの寄与を考えると,$$A_0 A_j + A_1 A_j \dots + A_{ j - 1 } A_j$$ となります.ここから $A_j$ をくくり出すと $$( A_0 + A_1 + \dots + A_{ j - 1 } )A_j$$ となります.このことから,各 $j$ について,そこから左の総和が分かっていれば答えへの寄与が求められると分かります.よって,左からの総和をもちながら $j$ を動かしていけば,答えを求めることができます.
コード
main = do getLine as <- readIntegers let psum = scanl (+%) 0 as print $ foldl1 (+%) $ zipWith (*%) psum as a +% b = ( a + b ) `mod` 1000000007 a *% b = a * b `mod` 1000000007