ABC177に参加してみた - インフラエンジニアの備忘録とか色々

初めに

ABC177はAB完でした。C問題はほぼほぼ解けていたんですが
問題文を読み間違えている事に最後まで気づかず回答できませんでしたorz
はい、ということで今回はC問題について書いていきます。。。

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Sum of product of pairs

N個の整数 $A_1 ～ A_N$ が与えられるので $1 \le i \lt j \le N$ を満たす
すべての $(i,j)$ についての $A_i × A_j$ の和を $mod(10^9+7)$ で割った数を求める問題です。

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

  ll N;
  ll ans = 0;
  ll mod = 1e9 + 7;
  cin >> N;

  vector<ll> A(N);
  vector<ll> S(N + 1);

  for (ll i = 0; i < N;++i)
    cin >> A[i];

  S[0] = 0;

  for (ll i = 0; i <N;++i){

    // 累積和を求める
    S[i+1] = (S[i] + A[i]);

  }

  for (ll i = 0; i < N;++i){
    // 区間和を求める
    ll sum = (S[N] - S[i + 1]) % mod;
    // AiAjの計算を行い変数ansに加算し、mod計算を行う
    ans += sum*A[i];
    ans %= mod;
  }

  cout << ans << endl;

  return 0;

}

この問題は愚直に2重ループで計算を行っていくとNの制約が $2 \le N \le 2×10^5$ のため、
制限時間内に計算を行う事が出来ません。