Submission

Score: 0

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.001 second

Submitted On: 2025-03-13 14:54:42

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,no-stack-protector,inline-small-functions,inline,unsafe-math-optimizations,omit-frame-pointer,inline-functions-called-once")
#include <bits/stdc++.h>
#pragma GCC target("avx2,fma,popcnt,lzcnt,bmi,bmi2,sse4.2,tune=native")
using namespace std;
#define ll long long
ll mod = 1e9 + 7, dp[5005][5005], vis[5005], ddp[5005];

ll poww(ll x, ll y)
{
    if (vis[x])
        return ddp[x];
    vis[x] = 1;
    ll sum = 1;
    for (int i = 0; i < y; i++)
        sum *= x;
    return ddp[x] = sum;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k, c;
    cin >> n >> k >> c;
    ll a[n], lo, hi;
    for (auto &e : a)
        cin >> e;
    cin >> lo >> hi;
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        ll sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += poww(j - i, c) * a[j];
            if (sum >= lo && sum <= hi)
            {
                for (int l = 0; l < k; l++)
                    dp[i][l + 1] += dp[j + 1][l], dp[i][l + 1] %= mod;
            }
        }
    }
    cout << dp[0][k] << '\n';
}