Submission

xxxxxxxxxxxxxxxx

Score: 0

User: PakinDioxide

Problemset: Chocolate

Language: cpp

Time: 0.000 second

Submitted On: 2025-03-13 15:29:14

/*
    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, dp[5005][5005], pdp[5005][5005];

ll poww(ll x, ll y) {
    if (y == 0) return 1;
    ll k = poww(x, y/2);
    k *= k;
    if (y & 1LL) k *= x;
    return 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;
    dp[n][0] = 1;
    for (int i = 0; i < n; i++) {
        pdp[i][i] = poww(0, c)*a[i];
        for (int j = i+1; j < n; j++) pdp[i][j] = pdp[i][j-1] + poww(j-i, c) * a[j];
    }
    for (int i = n-1; i >= 0; i--) {
        ll idx1 = lower_bound(pdp[i]+i, pdp[i]+n, lo) - pdp[i];
        ll idx2 = upper_bound(pdp[i]+i, pdp[i]+n, hi) - pdp[i] - 1;
        for (int l = 0; l <= k; l++) dp[i][l] += dp[i+1][l], dp[i][l]%=mod;
        if (idx1 > idx2) continue;
        for (int l = 0; l < k; l++) dp[i][l+1] += (dp[idx1+1][l] - dp[idx2+2][l] + mod) % mod, dp[i][l+1]%=mod;
    }
    cout << (dp[0][k]-dp[1][k]+mod)%mod << '\n';
}