Submission #1798164

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
const int INF = 1 << 29;
const ll LINF = 1l << 61;
const ld PI = abs(acos(-1));
#define pq priotity_queue
#define mp make_pair
#define P pair
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i >= b; i--)
#define cbuf(buf, init) memset(buf, init, sizeof(buf))
#define modp(x, y) (((y) + (x) % (y)) % (y))
#define divd(x, y) (static_cast<double>(x) / static_cast<double>(y))

const ll MOD = 1'000'000'007;

ll K, N;
ll S[200000];

int main()
{
    //
    cin >> N >> K;
    S[0] = 1;
    rep(i, 0, N)
    {
        S[i + 1] = modp(S[i] * 2, MOD);
        ll j = i - K;
        if (j == -2)
            S[i + 1] -= modp(1, MOD);
        else if (j >= 0)
            S[i + 1] -= modp(S[j], MOD);
        S[i + 1] = modp(S[i + 1], MOD);
    }
    cout << S[N - 1] - S[N - 2] << endl;
}

Submission Info

Judge Result