[ACM]【prefix/求和/取余】牛客练习赛64 序列卷积之和

序列卷积之和

传送门
题意：求$\sum_{l=1}^n\sum_{r=l}^n\sum_{i=l}^r\sum_{j=i}^ra_i\times a_j\mod 1e9+7$∑l=1n​∑r=ln​∑i=lr​∑j=ir​ai​×aj​mod1e9+7

思路：

本弱鸡只会找规律（。看到题解恍然大悟。
就是强行用前缀和把循环一层一层剥掉。
一开始是

for(int l=1;l<=n;l++)
	for(int r=l;r<=n;r++)
		for(int i=l;i<=r;i++)
			for(int j=i;j<=r;j++)
				sum+=a[i]*a[j];

把最内层循环展开，是
$a[i]*a[i]+a[i]*a[i+1]+...+a[i]*a[r]$a[i]∗a[i]+a[i]∗a[i+1]+...+a[i]∗a[r]
即
$a[i]*(a[i]+a[i+1]+...+a[r])$a[i]∗(a[i]+a[i+1]+...+a[r])
我们求$a[i]$a[i]的前缀和，设为$b[i]$b[i]
即
$a[i]*(b[r]-b[i-1])$a[i]∗(b[r]−b[i−1])

for(int l=1;l<=n;l++)
	for(int r=l;r<=n;r++)
		for(int i=l;i<=r;i++)
			sum+=a[i]*(b[r]-b[i-1]);

把最内层循环展开，是
$a[l]*(b[r]-b[l-1])+a[l+1]*(b[r]-b[l+1-1])+...+a[r]*(b[r]-b[r-1])$a[l]∗(b[r]−b[l−1])+a[l+1]∗(b[r]−b[l+1−1])+...+a[r]∗(b[r]−b[r−1])
拆开小括号，重新组合，得
$b[r]*(a[l]+a[l+1]+...+a[r])-(a[l]*b[l-1]+a[l+1]*b[l+1-1]+...+a[r]*a[r-1])$b[r]∗(a[l]+a[l+1]+...+a[r])−(a[l]∗b[l−1]+a[l+1]∗b[l+1−1]+...+a[r]∗a[r−1])
即
$b[r]*(b[r]-b[l-1])-(a[l]*b[l-1]+a[l+1]*b[l+1-1]+...+a[r]*a[r-1])$b[r]∗(b[r]−b[l−1])−(a[l]∗b[l−1]+a[l+1]∗b[l+1−1]+...+a[r]∗a[r−1])
我们求$a[i]*b[i-1]$a[i]∗b[i−1]的前缀和，设为$c[i]$c[i]
即
$b[r]*(b[r]-b[l-1])-(c[r]-c[l-1])$b[r]∗(b[r]−b[l−1])−(c[r]−c[l−1])

for(int l=1;l<=n;l++)
	for(int r=l;r<=n;r++)
		sum+=b[r]*(b[r]-b[l-1])-(c[r]-c[l-1]);

把最内层循环展开，是
$b[l]*(b[l]-b[l-1])-(c[l]-c[l-1])+b[l+1]*(b[l+1]-b[l-1])-(c[l+1]-c[l-1])+...+b[n]*(b[n]-b[l-1])-(c[n]-c[l-1])$b[l]∗(b[l]−b[l−1])−(c[l]−c[l−1])+b[l+1]∗(b[l+1]−b[l−1])−(c[l+1]−c[l−1])+...+b[n]∗(b[n]−b[l−1])−(c[n]−c[l−1])
拆开小括号，重新组合，得
$(b[l]^2+b[l+1]^2+...+b[n]^2)-b[l-1]*(b[l]+b[l+1]+...+b[n])-(c[l]+c[l+1]+...+c[n])+(n-l+1)*c[l-1]$(b[l]2+b[l+1]2+...+b[n]2)−b[l−1]∗(b[l]+b[l+1]+...+b[n])−(c[l]+c[l+1]+...+c[n])+(n−l+1)∗c[l−1]
我们求$b[i]^2$b[i]2的前缀和，设为$d[i]$d[i]
求$b[i]$b[i]的前缀和，设为$e[i]$e[i]
求$c[i]$c[i]的前缀和，设为$f[i]$f[i]
即
$(d[n]-d[l-1])-b[l-1]*(e[n]-e[l-1])-(f[n]-f[l-1])+(n-l+1)*c[l-1]$(d[n]−d[l−1])−b[l−1]∗(e[n]−e[l−1])−(f[n]−f[l−1])+(n−l+1)∗c[l−1]

for(int l=1;l<=n;l++)
	sum+=(d[n]-d[l-1])-b[l-1]*(e[n]-e[l-1])-(f[n]-f[l-1])+(n-l+1)*c[l-1];

现在复杂度就简化为$O(n)$O(n)了。
接下来我们要对求余进行常规操作：
在求bcdef数组的时候，直接每求一个都取余，这个没所谓。
但是在sum里面，存在减法和乘法，事态就变得不同寻常了。
遇到减法之后，我们可以在减法进行的地方加mod，也可以在减法进行的地方做了乘法之后加mod，是一样的。
那么代码就写出来了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=2e5+4;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn],d[maxn],e[maxn],f[maxn];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=(b[i-1]+a[i])%mod;
		c[i]=(c[i-1]+a[i]*b[i-1])%mod;
		d[i]=(d[i-1]+b[i]*b[i])%mod;
		e[i]=(e[i-1]+b[i])%mod;
		f[i]=(f[i-1]+c[i])%mod;
	}
	ll ans=0;
	for(int l=1;l<=n;l++){
		ans+=(d[n]-d[l-1]-b[l-1]*(e[n]-e[l-1]))%mod+mod-(f[n]-f[l-1]+mod)+(n-l+1)*c[l-1];
		ans=(ans+mod)%mod;
	}
	printf("%lld\n",ans);
}