Submission

Score: 20

User: devilpoohs

Problemset: Chocolate

Language: cpp

Time: 0.070 second

Submitted On: 2026-03-08 15:46:17

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,c,K,l,h;;
#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>K>>c;
    int dp[n+1][K+1];
    int ar[n],powi[n];
    for(int i=0;i<n;i++){
        cin>>ar[i];
        powi[i]=1;
        for(int j=0;j<c;j++){
            powi[i]*=i;
            powi[i]%=mod;
        }
        // cout<<i<<','<<powi[i]<<'\n';
    }
    cin>>l>>h;
    dp[n][0]=1;
    for(int k=1;k<=K;k++){
        dp[n][k]=0;
    }
    for(int i=n-1;i>=0;i--){
        for(int k=1;k<=K;k++){
            int cnt=0;
            int sum=0;
            for(int j=i,mul=0;j<n;j++,mul++){
                sum+=(ar[j]*powi[mul]);
                if(sum>h) break;
                if(sum>=l){
                    cnt+=dp[j+1][k-1]%mod;
                    // cout<<j+1<<''
                    cnt%=mod;
                }
            }
            cnt%=mod;
            dp[i][k]=cnt;
        }
    }
    cout<<dp[0][K];
    return 0;
}
/*
8 3 2
7 9 1 3 3 6 2 9
4 64
*/