$

題目描述

給定一個序列(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);
}

總結

以上是生活随笔為你收集整理的Suffix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。