Submission

Score: 0

User: C12

Problemset: Chocolate

Language: cpp

Time: 0.000 second

Submitted On: 2026-03-16 19:52:09

#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 *= a;
        a *= a;
        p >>= 1;
    }
    return res;
}

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

    int n,m,c;

    cin >> n >> m >> c;

    vector<int>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--){
            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';
    // }

    int lo;
    int hi;

    cin >> lo >> hi;

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

    int i = 0;

    while(i < n && pre[i][0] < lo){
        i++; 
    }
    // cout << i << '\n';
    
    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;
}