Submission

Score: 160

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.024 second

Submitted On: 2026-08-04 00:24:45

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;

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

    int n, k, c;
    cin >> n >> k >> c;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l, h;
    cin >> l >> h;

    int comb[6][6] = {};
    for (int i = 0; i <= 5; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }

    vector<vector<__int128>> pref(c + 1, vector<__int128>(n + 1));
    for (int i = 1; i <= n; i++) {
        __int128 p = 1;
        for (int j = 0; j <= c; j++) {
            pref[j][i] = pref[j][i - 1] + p * a[i];
            p *= i;
        }
    }

    auto get = [&](int x, int y) {
        __int128 res = 0;
        __int128 p[6];
        p[0] = 1;
        for (int i = 1; i <= c; i++) p[i] = p[i - 1] * x;

        for (int i = 0; i <= c; i++) {
            __int128 cur = pref[i][y] - pref[i][x - 1];
            cur *= comb[c][i];
            cur *= p[c - i];
            if ((c - i) & 1) res -= cur;
            else res += cur;
        }
        return res;
    };

    vector<int> lo(n + 1), hi(n + 1);

    for (int i = 1; i <= n; i++) {
        int x = 1, y = i, ans = i + 1;
        while (x <= y) {
            int m = (x + y) / 2;
            if (get(m, i) <= h) {
                ans = m;
                y = m - 1;
            } else {
                x = m + 1;
            }
        }
        lo[i] = ans;

        x = 1;
        y = i;
        ans = 0;
        while (x <= y) {
            int m = (x + y) / 2;
            if (get(m, i) >= l) {
                ans = m;
                x = m + 1;
            } else {
                y = m - 1;
            }
        }
        hi[i] = ans;
    }

    vector<int> dp(n + 1), ndp(n + 1), sum(n + 1);
    dp[0] = 1;

    for (int i = 1; i <= k; i++) {
        sum[0] = dp[0];
        for (int j = 1; j <= n; j++) {
            sum[j] = sum[j - 1] + dp[j];
            if (sum[j] >= mod) sum[j] -= mod;
        }

        fill(ndp.begin(), ndp.end(), 0);

        for (int j = i; j <= n; j++) {
            int x = lo[j] - 1;
            int y = hi[j] - 1;

            if (x > y || lo[j] > j || hi[j] == 0) continue;

            ndp[j] = sum[y];
            if (x > 0) {
                ndp[j] -= sum[x - 1];
                if (ndp[j] < 0) ndp[j] += mod;
            }
        }

        dp.swap(ndp);
    }

    cout << dp[n] << '\n';
}