Submission

PPPPPxPPPPPPPPPP

Score: 150

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.053 second

Submitted On: 2025-03-13 15:08:58

/*
    Author : detective conan
    Problem : Chocolate
    created : 13/03/2025 15:03
*/
#include <bits/stdc++.h>
#define int long long
#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();
}