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

思路

首先发现对于内层的求和，

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。不会可以百度。

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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