题解：AT_abc177_c [ABC177C] Sum of product of pairs

tangible_love · 2025-09-22 23:18:09 · 题解

思路

首先发现对于内层的求和，a_i 是不会发生变化的，考虑提出来，变成 \sum_{i=1}^{N-1} A_i \sum_{j=i+1}^{N} A_j 再对内层的求和做一个前缀和 s，变成 \sum_{i=1}^{N-1} A_i (s_n-s_i)，不会前缀和的左转。

于是就可以 O(n) 解决这个题。

还有一点就是取模。

• 加法：分别取模再加和之后再取模。
• 减法：类似加法，但是被减数要加上模数，防止变成负数之后取模不正确。
• 乘法：类似加法。
• 除法：求逆元。用 exgcd。不会可以百度。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,ans,mod,a[200010],sum[200010];
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    mod=1e9+7;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%mod;
    }
    for(int i=1;i<=n-1;i++) ans=(ans+a[i]*(sum[n]+mod-sum[i])%mod)%mod;
    cout<<ans;
    return 0;
}