Submission #1797389

---

Source Code Expand

#include <iostream>
#include <cstdio>

typedef long long ll;

using namespace std;

#define MAX_N 1000000
#define MAX_K 1000000
#define mod(x, y) ((x % y) + y) % y
#define MOD 1000000007
#define modp(x) mod(x, MOD)

int main(int argc, const char * argv[]) {
    // a[i] : 駅1から駅iまでの停まり方(駅iには必ず止まる)の総数
    ll a[MAX_N];
    // b[i] : 駅1から駅iまでの停まり方(駅iには止まらない)の総数
    ll b[MAX_N];
    
    int N, K;
    cin >> N >> K;
    
    a[1] = 1;
    b[1] = 0;
    for (int i = 1; i < K-1; i++) {
        a[i+1] = modp(a[i] + b[i]);
        b[i+1] = modp(a[i] + b[i]);
    }
    
    a[K] = modp(a[K-1] + b[K-1] - 1);
    b[K] = modp(a[K-1] + b[K-1]);
    
    for (int i = K; i < N; i++) {
        a[i+1] = modp((a[i] - b[i-(K-1)]) + b[i]);
        b[i+1] = modp((a[i] - b[i-(K-1)]) + b[i] + b[i-(K-1)]);
    }
    cout << a[N] << endl;
    return 0;
}

Submission Info

Judge Result