Submission

PPPPPPPPPPPPPPPP

Score: 160

User: pppppppppppp

Problemset: Chocolate

Language: cpp

Time: 0.088 second

Submitted On: 2025-04-17 09:08:08

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 1000000007;

// fast power j^e
inline __int128 ipow128(ll j, int e) {
    __int128 r = 1, b = j;
    while (e) {
        if (e & 1) r *= b;
        b *= b;
        e >>= 1;
    }
    return r;
}

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

    int N, K, C;
    cin >> N >> K >> C;
    vector<ll> B(N);
    for(int i = 0; i < N; i++) cin >> B[i];
    ll L, R;
    cin >> L >> R;

    // 1) Precompute prefix sums P[d][i] = sum_{m=0..i-1} m^d * B[m], stored as __int128
    vector<vector<__int128>> P(C+1, vector<__int128>(N+1, 0));
    for(int i = 0; i < N; i++){
        __int128 pow_m = 1;
        for(int d = 0; d <= C; d++){
            P[d][i+1] = P[d][i] + pow_m * B[i];
            pow_m *= i;
        }
    }

    // 2) build binomial coefficients comb[c][d]
    vector<vector<ll>> comb(C+1, vector<ll>(C+1,0));
    for(int n=0; n<=C; n++){
      comb[n][0] = comb[n][n] = 1;
      for(int k=1; k<n; k++)
        comb[n][k] = comb[n-1][k-1] + comb[n-1][k];
    }

    // 3) for each start j, binary‑search the minimal and maximal end i so that
    //    S(j,i) = sum_{t=0..i-j-1} t^C * B[j+t]  lies in [L..R].
    //
    //    Using the binomial shift:
    //      S(j,i) = sum_{m=j..i-1} (m-j)^C * B[m]
    //             = sum_{d=0..C}  comb[C][d] * (-j)^(C-d) *
    //                            ( P[d][i] - P[d][j] )
    //
    vector<int> lo(N), hi(N);
    for(int j = 0; j < N; j++){
      // precompute (-j)^e for e=0..C
      vector<__int128> negpow(C+1,1);
      for(int e = 1; e <= C; e++)
        negpow[e] = negpow[e-1] * -(__int128)j;

      // lambda to compute S(j,i):
      auto segval = [&](int i){
        __int128 v = 0;
        for(int d = 0; d <= C; d++){
          __int128 diff = P[d][i] - P[d][j];
          v += (__int128)comb[C][d] * negpow[C-d] * diff;
        }
        return v;
      };

      // find lo[j] = smallest i in [j+1..N] with segval(j,i) >= L
      int a = j+1, b = N, ans_lo = N+1;
      while(a <= b){
        int mid = (a+b)>>1;
        if(segval(mid) >= (__int128)L){
          ans_lo = mid; 
          b = mid-1;
        } else a = mid+1;
      }
      lo[j] = ans_lo;

      // find hi[j] = largest i in [j..N] with segval(j,i) <= R
      // i=j yields empty segment => S=0; but we enforce i>j so start at j+1
      a = j+1; b = N; 
      int ans_hi = j;  // no valid if stays j
      while(a <= b){
        int mid = (a+b)>>1;
        if(segval(mid) <= (__int128)R){
          ans_hi = mid;
          a = mid+1;
        } else b = mid-1;
      }
      hi[j] = ans_hi;
    }

    // 4) DP: dp[t][i] = #ways to cut first i bars into t segments,
    //    we'll only keep two rows and do range‑updates via a difference array.
    vector<ll> prev(N+1,0), curr(N+1,0);
    prev[0] = 1;  // zero bars, zero segments → 1 way

    for(int t = 1; t <= K; t++){
      // diff array of size N+2 to do range add on [lo[j]..hi[j]] of prev[j]
      vector<ll> diff(N+2,0);
      for(int j = 0; j < N; j++){
        if(prev[j]==0) continue;
        int l = lo[j], r = hi[j];
        if(l <= r && l <= N){
          diff[l] = (diff[l] + prev[j]) % MOD;
          diff[r+1] = (diff[r+1] - prev[j] + MOD) % MOD;
        }
      }
      // prefix‑sum diff → curr
      ll run = 0;
      for(int i = 0; i <= N; i++){
        run = (run + diff[i]) % MOD;
        curr[i] = run;
      }
      swap(prev, curr);
      fill(curr.begin(), curr.end(), 0);
    }

    // answer = prev[N] (exactly K segments, using all N bars)
    cout << prev[N] << "\n";
    return 0;
}