Submission

PPPPPxPPPPPPPPPP

Score: 150

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.127 second

Submitted On: 2025-03-13 14:56:24

#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;
vector<vector<ll>> dp;
unordered_map<ll, ll> power_cache;


ll poww(ll x, ll y)
{
    
    if (y <= 1) return y == 0 ? 1 : x;
    
    
    ll key = (x << 32) | y;
    auto it = power_cache.find(key);
    if (it != power_cache.end()) return it->second;
    
    
    ll res = 1;
    while (y > 0) {
        if (y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    
    return power_cache[key] = res;
}

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