BOOM！

于是我们又要想办法优化内存

我们发现状态转移不会用到i-2及之前的状态，所以考虑滚动数组

这题由于奇偶性的原因，本人用判断奇偶的方法实现滚动数组，当然不排除有其它的实现方法。

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mod = 1000000007LL;

int n, f[310][100010], k, a[100010];

signed main() {

    scanf("%lld%lld", &n, &k);

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

        scanf("%lld", &a[i]);

    }

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

        // f[1][i] = f[1][i - 1] + a[i];

        f[0][i] = 1LL;

    }

    for(int i = 1; i <= k; i++) {

        f[i & 1][0] = 0LL;

        for(int j = 1; j <= n; j++) {

            f[i & 1][j] = (f[i & 1][j - 1] + a[j] * f[(i - 1) & 1][j - 1]) % mod;

            // cout << f[i & 1][j] << " ";

        }

        // cout << endl;

    }

    printf("%lld", f[k & 1][n]);

    return 0;

}

巴特西

洛谷P5087 数学

BOOM！

最新文章

热门文章