[AtCoder] ABC 177 C – Sum of product of pairs
問題
方針
与えられた式は、
\[
\sum_{i = 1}^{n – 1} \sum_{j = i + 1}^{n} A_iA_j= \sum_{i = 1}^{n – 1}A_i \sum_{j = i + 1}^{n} A_j\\
\]
となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、
\[
\sum_{i = 1}^{n – 1} \sum_{j = i + 1}^{n} A_iA_j= \sum_{i = 1}^{n – 1}A_i(B_n – B_{i})\\
\]
となります。よって、あらかじめ累積和を計算してから求めます。注意として、\( B_n – B_{i} \) が計算仕方によってマイナスとなる可能性があるので、
\[(B_n – B_i + 10^9 + 7 \bmod (10^9+7))\]
とします。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; ll A[N]; for (int i = 0; i < N; i++) { cin >> A[i]; } ll mod = 1000000007; ll B[N + 1]{}; for (int i = 0; i < N; i++) { B[i + 1] = (B[i] + A[i]) % mod; } ll ans = 0; for (int i = 0; i < N - 1; i++) { ans += A[i] * (B[N] - B[i + 1] + mod); ans %= mod; } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません