牛客练习赛63-C

题目链接
题目描述：

题解：dalao的写法都是找规律哒，作为萌新的我，只能暴力，先上一个暴力的代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
const int mod = 1e9 + 7;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    long long ans=0;
    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++){
                      ans+=(a[i]*a[j])%mod;
                      ans%=mod;                
              }
            }
        }
    }
    cout<<ans;
}

很容易的能根据题意模拟出题意，但是。。交上去会T啊，那。只能优化它一手了
观察最内层循环

               for(int j=i;j<=r;j++){
                 ans+=(a[i]*a[j])%mod;
                 ans%=mod;                
              }

这个部分可以写作a[i]*（a[i]+a[i+1]+a[i+2]+...a[r]）
那就很容易想到用前缀和来写后面的这一大块（a[i]+a[i+1]+a[i+2]+...a[r]）
然后（开心的）用前缀和去优化这一层循环(这里用数组b表示数组a的前缀和

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn],b[maxn];
const int mod = 1e9 + 7;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=b[i-1]+a[i];
        b[i]%=mod;
    }
    long long ans=0;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            for(int i=l;i<=r;i++){
             ans+=a[i]*(b[r]-b[i-1]);
             ans%=mod;
            }
        }
    }
    cout<<ans;
}

发现还是会T，那只好继续优化辣
继续观察内层循环：

  for(int i=l;i<=r;i++){
      ans+=a[i]*(b[r]-b[i-1]);
      ans%=mod;
   }

这个东西可以写作a[i] * b[r] -a[i] * b[i-1]
即：（a[l]+a[l+1]+a[l+2]+...+a[r]）* b[r] -(a[l] * b[l-1] + a[l+1] * b[l]+...+a[r] * b[r-1])
令 d[i]=a[i] * b[i-1]
原式=(b[r]-a[l-1]) * b[r] -(d[l]+d[l+1]...+d[r])
再对数组d进行计算前缀和：即c[i]=c[i-1]+a[i]*b[i-1]
原式=(b[r]-a[l-1]) *b[r] -(c[r]-c[l-1]);

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

发现还是会T
继续观察循环内部
拆开写为：b[r] * b[r] -b[l-1] * b[r] -c[r] +c[l-1]
对其求和为：(b[l] * b[l]+b[l+1] * b[l+1]+...+b[n] * b[n] )
-b[l-1] * (b[l]+b[l+1]+..+b[n]))
-(c[l]+c[l+1]+...+c[n])
+(n-l+1) * c[l-1]
发现有三个前缀和需要计算
令e[i]=e[i-1]+b[i]*b[i]
f[i]=f[i-1]+b[i]
g[i]=g[i-1]+c[i]
即循环可以写作:e[n]-e[l-1]-(b[l-1] * (f[n]-f[l-1]))-(g[n]-g[l-1])+(n-l+1) * c[l-1]
namo：

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

这样子就不会t了，
然后考虑int相乘可能会爆精度，全改成longlong (再加上各种取模操作

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

然后就能过辣