Submission

Score: 140

User: C12

Problemset: Chocolate

Language: cpp

Time: 0.073 second

Submitted On: 2026-03-16 20:02:10

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
#define ll long long
#define pii pair<ll,int>

// ll dp[5001][5001];

ll calibrate(ll a){
    while(a < 0) a += mod;
    while(a >= mod) a -= mod;
    return a;
}

ll pow_ll(ll a,ll p){
    ll res = 1;
    while(p){
        if(p & 1) res = (res * a);
        a = (a * a);
        p >>= 1;
        if(res < 0) return LLONG_MAX/2;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n,m,c;

    cin >> n >> m >> c;

    vector<ll>vec(n);

    vector<vector<ll>> dp(m, vector<ll>(n,0));

    for(int i = 0;i < n;i++) cin >> vec[i];

    vector<vector<ll>>pre(n, vector<ll>(n,0));
    vector<ll>mul(n+1);

    for(int i = 0;i <= n;i++){
        mul[i] = pow_ll(i,c);
    }

    // return 0;

    for(int i = 0;i < n;i++){
        pre[i][i] = vec[i] * mul[0];
        for(int j = i-1;j >= 0;j--){
            if(mul[i-j] == LLONG_MAX/2 || pre[i-1][j] > LLONG_MAX/2)
                pre[i][j] = LLONG_MAX/2;
            else
                pre[i][j] = pre[i-1][j] + (vec[i] * mul[i-j]);
        }
    }
    
    // for(int i = 0;i < n;i++){
    //     for(int j = 0;j < n;j++){
    //         cout << pre[i][j] << '\t';
    //     }
    //     cout << '\n';
    // }

    ll lo;
    ll hi;

    cin >> lo >> hi;

    int i = 0;

    while(i < n && pre[i][0] < lo){
        i++; 
    }

    while(i < n && pre[i][0] <= hi){
        dp[0][i] = 1;
        i++;
    }

    for(int k = 1;k < m;k++){
        for(int i = 1;i < n;i++){
            for(int j = i;j < n;j++){
                if(pre[j][i] >= lo && pre[j][i] <= hi){
                    dp[k][j] += dp[k-1][i-1];
                    dp[k][j] = calibrate(dp[k][j]);
                }
            }
        }
    }

    // for(int k = 0;k < m;k++){
    //     for(int i = 0;i < n;i++){
    //         cout << dp[k][i] << '\t';
    //     }
    //     cout << '\n';
    // }
    
    cout << dp[m-1][n-1];

    return 0;
}