Submission

Score: 90

User: august

Problemset: Chocolate

Language: cpp

Time: 0.007 second

Submitted On: 2026-03-22 20:14:22

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

#define int long long
#define pi pair<int,int>
const int INF = 1e18, N = 1500, MOD = 1e9+7;

int n,k,c,l,r;

int a[N], dp[N][N];

int pow(int base, int ex) {
    if (base == 0 && ex == 0) return 1;
    if (base == 1) return 1;

    int ans=1;
    while (ex >= 1) ans *=base,ex--;
    return ans;
}

int fnd(int ind, int partitioned) {
    if (ind>n) {
        if (partitioned == k) return 1;
        return 0;
    }

    if (dp[ind][partitioned] != -1) return dp[ind][partitioned];

    int sm=0, val=0;
    for (int i=ind; i<=n; i++) {
        val+= pow(i-ind, c)*a[i];
        //cout<< ind<< ' '<<i<< ' '<< val<< '\n'; 
        if (val < l) continue;
        if (val > r) break;

        sm = (sm + fnd(i+1, partitioned+1))%MOD;
    }
    return dp[ind][partitioned] = sm;
}

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;

    memset(dp, -1, sizeof(dp));
    cout<< fnd(1, 0);
}