Submission

PPPPPxPPPPPPPPPP

Score: 150

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.036 second

Submitted On: 2025-03-13 15:00:07

#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
constexpr ll mod = 1e9 + 7;


ll* dp_flat;

vector<vector<ll>> precomputed_powers;

inline ll poww_fast(ll x, ll y) {
    if (y <= 1) return y == 0 ? 1 : x;
    
    ll res = 1;
    while (y > 0) {
        if (y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return 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;
    
    
    const int dp_size = (n+1) * (k+1);
    dp_flat = new ll[dp_size]();
    
    
    dp_flat[n * (k+1) + 0] = 1;
    
    
    precomputed_powers.resize(n);
    for (int diff = 0; diff < n; diff++) {
        precomputed_powers[diff].resize(c+1);
        for (int power = 0; power <= c; power++) {
            precomputed_powers[diff][power] = poww_fast(diff, power);
        }
    }
    
    #pragma omp parallel for schedule(dynamic) if(n > 1000)
    for (int i = n - 1; i >= 0; i--) {
        ll sum = 0;
        for (int j = i; j < n; j++) {
            sum += precomputed_powers[j-i][c] * a[j];
            
            if (sum >= lo && sum <= hi) {
                const int idx_i = i * (k+1);
                const int idx_j = (j+1) * (k+1);
                
                
                int l = 0;
                const int limit = min(k, 4); 
                
                
                for (; l < limit; l++) {
                    dp_flat[idx_i + l+1] = (dp_flat[idx_i + l+1] + dp_flat[idx_j + l]) % mod;
                }
                
                
                for (; l < k; l++) {
                    dp_flat[idx_i + l+1] = (dp_flat[idx_i + l+1] + dp_flat[idx_j + l]) % mod;
                }
            }
        }
    }
    
    cout << dp_flat[0 + k] << '\n';
    
    
    delete[] dp_flat;
    return 0;
}