《牛客练习赛63-C》

思路：前缀和优化.
一层层去优化掉循环.
至于怎么优化？写成L,r的形式就可以慢慢优化成
ans += (sum4[n]-sum4[L-1])-sum[L-1](sum3[n]-sum3[L-1])-(sum5[n]-sum5[L-1])+sum2[L-1](n-L+1);这样的一维循环.
细节讲一下：因为涉及到了减的操作,所以注意+Mod然后%Mod来防负数.
然后因为我这代码里把后面分开来下了，那个+应该是-.
Code:

LL a[N];
LL sum[N];//a值的前缀和
LL sum2[N];//a[i]*sum[i-1]的前缀和
LL sum3[N];//sum[i]的前缀和
LL sum4[N];//sum[i]^2的前缀和
LL sum5[N];//sum2的前缀和.
/*
ans += (sum4[n]-sum4[L-1])-sum[L-1]*(sum3[n]-sum3[L-1])-(sum5[n]-sum5[L-1])+sum2[L-1]*(n-L+1);
*/
int main()
{
    int n;sd(n);
    for(int i=1;i<=n;++i) 
    {
        sld(a[i]);
        sum[i] = (sum[i-1]+a[i])%Mod;
        sum2[i] = (sum2[i-1]+(a[i]*sum[i-1])%Mod)%Mod;
        sum3[i] = (sum3[i-1]+sum[i])%Mod;
        sum4[i] = (sum4[i-1]+(sum[i]*sum[i])%Mod)%Mod;
        sum5[i] = (sum5[i-1]+sum2[i])%Mod;
    }
    LL ans = 0;
    for(int L=1;L<=n;++L)
    {
        LL ma1 = ((sum4[n]-sum4[L-1])%Mod-(sum[L-1]*((sum3[n]-sum3[L-1])%Mod))%Mod)%Mod;
        ma1 = (ma1+Mod)%Mod;
        LL ma2 = ((sum5[n]-sum5[L-1])%Mod-(sum2[L-1]*(n-L+1))%Mod)%Mod;//注意因为是直接-ma2,所以中间应该是-,才能像原式一样,-ma2时变成+.
        LL ma = ((ma1-ma2)%Mod+Mod)%Mod;//防负数
        ans = (ans+ma)%Mod;
    }
    plr(ans);
    system("pause");
    return 0;
}