Submission

PPPPPPPPPPPPPPPP

Score: 160

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.725 second

Submitted On: 2025-03-13 15:37:29

/*
    Author : detective conan
    Problem : Chocolate
    created : 13/03/2025 15:03
*/
#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;

int A[MAXN], dp[2][MAXN], i2c[MAXN];
vector<int> sum[MAXN];

void solve() {
    int N, K, c;
    cin >> N >> K >> c;
    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;
        }
    }
    FOR(l, 1, N) {
        if (1LL * i2c[0] * A[l] > H) sum[l].push_back(H + 1);
        else {
            sum[l].push_back(i2c[0] * A[l]);
            FOR(r, l + 1, N) {
                if (sum[l].back() + 1LL * i2c[r - l] * A[r] > H) {
                    sum[l].push_back(H + 1);
                    break;
                }
                sum[l].push_back(sum[l].back() + i2c[r - l] * A[r]);
            }
        }
    }
    dp[0][N + 1] = 1;
    FOR(k, 1, K) {
        int now = k % 2, nxt = now ^ 1;
        rep(i, N - k + 1, 1) {
            int l = i, r = min(N - k + 1, (int)sum[i].size() + i - 1), pl = -1, pr = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (sum[i][mid - i] >= L) pl = mid, r = mid - 1;
                else l = mid + 1;
            }
            l = i, r = min(N - k + 1, (int)sum[i].size() + i - 1);
            while (l <= r) {
                int mid = (l + r) / 2;
                if (sum[i][mid - i] <= H) pr = mid, l = mid + 1;
                else r = mid - 1;
            }
            if (pl != -1 && pr != -1) dp[now][i] = (dp[nxt][pr + 1] - dp[nxt][pl] + mod) % mod;
            else dp[now][i] = 0;
        }
        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();
}