$

题目描述

给定一个序列\(A\),请你输出\(\sum_{1< i< j < k < h}A_iA_jA_kA_h(mod ~~1e9+7)\)

\(Solution\)

这个题顾名思义，就是一道考察前缀和的题，但是这其中竟然还涉及了\(DP\)和递推的思想，首先，我们可以令\(sum[i][j]\)表示\(i\)这个位置乘了\(j\)个数所得的结果,并且防止刚刚更新的值继续更新接下来要更新的值，就需要用到01背包的方法，从后往前滚动数组来防止这一结果，那我们就可以从这个位置的上一个位置来转移过来。

#include <bits/stdc++.h>

#define mod 1000000007

using namespace std;

long long sum[1000100][6];

long long ans = 0;

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = 0; i <= n; i++)

        sum[i][0] = 1LL;

    for (int i = 1; i <= n; i++)

    {

        int a;

        cin >> a;

        for (int j = 4; j >= 1; j--)

        sum[i][j] = (long long) ((long long) sum[i - 1][j] % mod + (long long) sum[i - 1][j - 1] % mod * a) % mod;

    }

    printf("%lld", sum[n][4] % mod);

}