Submission

P----x----------

Score: 10

User: pxsit

Problemset: Chocolate

Language: cpp

Time: 0.128 second

Submitted On: 2025-03-15 12:12:30

#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")
#define emb emplace_back
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

using namespace std;

const int mod = 1e9 + 7;
const int N = 5005;

int dp[2][N];
int a[N];
vector<pair<int, int>> inter[N]; 

long long power(int base, int exp) {
    if (exp == 0) return 1;
    if (exp == 1) return base;
    if (exp == 2) return 1LL * base * base;
    if (exp == 3) return 1LL * base * base * base;
    if (exp == 4) return 1LL * base * base * base * base;
    return 1LL * base * base * base * base * base; 
}

int main() {
    iShowSpeed;
    int n, k, c; 
    cin >> n >> k >> c;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ll, rr; 
    cin >> ll >> rr;

    
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j <= n; j++) {
            int len = j - i;
            long long val = power(len, c);
            sum += a[j] * val;
            
            if (sum > rr) break;
            if (sum >= ll && sum <= rr) {
                inter[j].emb(make_pair(i, sum));
            }
        }
    }

    
    for (const auto& in : inter[1]) {
        dp[1][1] = 1;
    }

    
    for (int i = 2; i <= n; i++) {
        for (const auto& in : inter[i]) {
            int start = in.first;
            
            if (start == 1) {
                dp[1][i] = (dp[1][i] + 1) % mod;
            }
        }
    }

    
    for (int i = 2; i <= k; i++) {
        int curr = i & 1, prev = curr ^ 1;
        
        
        for (int j = 1; j <= n; j++) {
            dp[prev][j] = (dp[prev][j] + dp[prev][j-1]) % mod;
        }
        
        for (int j = i; j <= n; j++) {
            dp[curr][j] = 0;
            for (const auto& in : inter[j]) {
                int start = in.first;
                if (start <= j - i + 1) {
                    int eee = start - 1;
                    if (eee >= 1) {
                        dp[curr][j] = (dp[curr][j] + dp[prev][eee]) % mod;
                    } else if (i == 2) { 
                        dp[curr][j] = (dp[curr][j] + 1) % mod;
                    }
                }
            }
        }
    }
    cout << dp[k & 1][n];
}