Submission

PPPPPxPPPPPPPPPP

Score: 150

User: PakinDioxide

Problemset: Chocolate

Language: cpp

Time: 0.963 second

Submitted On: 2025-03-13 13:16:07

/*
    author  : PakinDioxide
    created : 13/03/2025 13:05
    task    : c2_su65_chocolate
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll mod = 1e9+7;
map <pair <ll, ll>, ll> dp, vis;

ll poww(ll x, ll y) {
    if (vis[{x, y}]) return dp[{x, y}];
    vis[{x, y}] = 1;
    if (y == 0) return dp[{x, y}] = 1;
    ll k = poww(x, y/2);
    k *= k;
    if (y % 2 == 1) k *= x;
    return dp[{x, y}] = k;
}

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;
    ll dp[n+1][k+1];
    memset(dp, 0, sizeof(dp));
    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';
}