Submission

PPPPPTPPPP-PPPPP

Score: 140

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 1.087 second

Submitted On: 2025-03-13 15:41:17

#include <bits/stdc++.h>
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod (int)(1e9 + 7)
#define MAXN (int)5005
#define sum(a, b) ((a%mod) + (b%mod))%mod
#define mul(a, b) ((a%mod) * (b%mod))%mod
#define HAVE_TESTCASE false
#define pb push_back
#define eb emplace_back
#define conan cin.tie(nullptr)->sync_with_stdio(false)

using namespace std;

void solve() {
    int N, K, c;
    cin >> N >> K >> c;
    
    
    vector<int> A(N + 1);
    vector<vector<int>> dp(2, vector<int>(N + 2, 0));
    vector<int> i2c(N + 1);
    
    FOR(i, 1, N) cin >> A[i];
    int L, H;
    cin >> L >> H;
    if (c == 0) i2c[0] = 1;
    FOR(i, 1, N) {
        i2c[i] = 1;
        FOR(j, 0, c - 1) {
            if (1LL * i2c[i] * i > H) break;
            i2c[i] *= i;
        }
    }
    
    dp[0][N + 1] = 1;
    FOR(k, 1, K) {
        int now = k % 2, nxt = now ^ 1;
        
        FOR(i, 1, N + 1) dp[now][i] = 0;
        
        rep(i, N - k + 1, 1) {
            int pl = -1, pr = -1;
            int curr_sum = 0;
            
            for (int j = i; j <= min(N - k + 1, N); j++) {
                if (j == i) {
                    curr_sum = i2c[0] * A[j];
                } else {
                    curr_sum += i2c[j - i] * A[j];
                }
                
                if (curr_sum > H) break;
                
                if (curr_sum >= L && curr_sum <= H) {
                    if (pl == -1) pl = j;
                    pr = j;
                }
            }
            
            if (pl != -1 && pr != -1) dp[now][i] = (dp[nxt][pr + 1] - dp[nxt][pl] + mod) % mod;
        }
        FOR(i, 2, N - k + 1) dp[now][i] = (dp[now][i] + dp[now][i - 1]) % mod;
    }
    ANS(dp[K % 2][1], '\n');
}

int32_t main() {
    conan;
    int t = 1;
    if (HAVE_TESTCASE) cin >> t;
    while (t--) solve();
}