fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAX = 1e6+5;
  6. const int MOD = 1e9+7;
  7. int n, k;
  8. int t[MAX*4], lazy[MAX*4];
  9. void push(int id, int l, int r){
  10.     if(lazy[id]!=0){
  11.         int mid = (l+r)/2;
  12.         (t[id*2] += (mid-l+1) * lazy[id] % MOD) %= MOD;
  13.         (lazy[id*2] += lazy[id]) %= MOD;
  14.         (t[id*2+1] += (r-mid) * lazy[id] % MOD) %= MOD;
  15.         (lazy[id*2+1] += lazy[id]) %= MOD;
  16.         lazy[id] = 0;
  17.         return;
  18.     }
  19. }
  20. void update(int id, int l, int r, int u, int v, int w){
  21.     if(v<l || r<u) return;
  22.     if(u<=l && r<=v){
  23.         (t[id] += (r-l+1) * w % MOD) %= MOD;
  24.         (lazy[id] += w) %= MOD;
  25.         return;
  26.     }
  27.     push(id, l, r);
  28.     int mid = (l+r)/2;
  29.     update(id*2, l, mid, u, v, w);
  30.     update(id*2+1, mid+1, r, u, v, w);
  31.     t[id] = (t[id*2] + t[id*2+1]) % MOD;
  32. }
  33. ll get(int id, int l, int r, int u, int v){
  34.     if(v<l || r<u) return 0;
  35.     if(u<=l && r<=v) return t[id];
  36.     push(id, l, r);
  37.     int mid = (l+r)/2;
  38.     ll t1 = get(id*2, l, mid, u, v);
  39.     ll t2 = get(id*2+1, mid+1, r, u, v);
  40.     return (t1+t2)%MOD;
  41. }
  42. signed main(){
  43.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  44.     cin >> n >> k;
  45.     update(1, 1, n, 1, 1, 1);
  46.     for(int i = 1; i<=n; i++){
  47.         ll val = get(1, 1, n, i, i);
  48.         update(1, 1, n, i+1, min(n, i+k), val);
  49.     }
  50.     cout << get(1, 1, n, n, n);
  51. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
6 3
stdout
copy 
13
https://ideone.com/0VigPj
language:
C++14 (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!