序列卷积之和

链接：https://ac.nowcoder.com/acm/contest/5633/C
解法1：这题看到一个不停使用前缀和优化最后达成O(n)计算的方法，感觉很有趣
他的分析过程是这样：
首先暴力4重循环

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

令b[i]=a[1]+a[2]+...+a[i]
减掉一层循环

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]);
        }
    }
}

再令d[i]=a[i]*b[i-1]
c[i]=d[1]+d[2]+...+d[i]
再去掉一层循环

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

再把式子展开，发现预处理bb的前缀和，b的前缀和，c的前缀和即可O（n）实现计算。
解法2：
这种题要立刻想到打表找规律。

i j：a[i]a[j]出现的次数
前缀和预处理a[j]，
s[i] = a[1]n+a[2](n-1)+...+a[i](n-i+1)的话
答案就是a[i](s[n]-s[i-1])*i
代码：

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define debug(x) cout << #x << ": " << x << endl;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define SZ(x) ((int)(x).size())
#define pb push_back
#define pii pair<int, int>
#define mem(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int N = 2e5+10;

int n;
ll a[N], s[N];
int main()
{
    n = read();
    for(int i=1; i<=n; i++){
        a[i] = read(); s[i] = (s[i-1] + a[i] * (n-i+1) % MOD) % MOD;
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans = (ans + a[i] * ((s[n]-s[i-1]+MOD)%MOD) % MOD * i % MOD) % MOD;
    }
    print(ans);
}