Submission

xxxxxxxxxxxxxxxx

Score: 0

User: PakinDioxide

Problemset: Chocolate

Language: cpp

Time: 0.001 second

Submitted On: 2025-03-13 13:25:02

/*
    author  : PakinDioxide
    created : 13/03/2025 13:05
    task    : c2_su65_chocolate
*/
#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

ll mod = 1e9+7, dp[5005][5005], vis[5005], ddp[5005];

ll poww(ll x, ll y) {
    if (vis[x]) return ddp[x];
    vis[x] = 1;
    ll sum = 1;
    for (int i = 0; i < y; i++) sum *= x;
    return ddp[x] = sum;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, c;
    cin >> n >> k >> c;
    ll a[n], lo, hi;
    for (auto &e : a) cin >> e;
    cin >> lo >> hi;
    dp[n][0] = 1;
    for (int i = n-1; i >= 0; i--) {
        ll sum = 0;
        for (int j = i; j < n; j++) {
            sum += poww(j-i, c)*a[j];
            if (sum >= lo && sum <= hi) {
                for (int l = 0; l < k; l++) dp[i][l+1] += dp[j+1][l], dp[i][l+1] %= mod;
            }
        }
    }
    cout << dp[0][k] << '\n';
}