Submission

Score: 140

User: august

Problemset: Chocolate

Language: cpp

Time: 1.084 second

Submitted On: 2026-03-22 20:37:01

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int,int>
const int N = 5001, MOD = 1e9+7;

int n,k,c,l,r;

int a[N];

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>> n>> k>> c;
    for (int i=1; i<=n; i++) cin>> a[i];
    cin>> l>> r;

    long long pow[N]={};
    for (int i=0; i<=n; i++) {
        int ans = 1;
        for (int j=1; j<=c; j++) ans*=i;
        if (c!=0) pow[i] = ans;
        else pow[i]=1;
        if (pow[i] > 2000000000) break;
    }

    vector<int> dp(N,0);
    dp[0] = 1;
    for (int part=1; part<=k; part++) {
        vector<int> ndp(N,0);
        for (int i=0; i<n; i++) {
            if (dp[i] == 0) continue;

            int curval = 0;
            for (int j=i+1; j<=n; j++) {
                int add = pow[j-i-1]*a[j];
                curval += add;

                if (curval < l) continue;
                if (curval > r) break;
                ndp[j] = (dp[i] + ndp[j])%MOD; 
            }
        }
        swap(dp,ndp);
    }
    cout<< dp[n];
}