Submission #1797125

---

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;
P<ll, ll> dp[2000000];

int main()
{
    //
    cin >> N >> K;
    dp[1] = mp(1, 0);
    rep(i, 1, N)
    {
        dp[i + 1].second = modp(dp[i].first + dp[i].second, MOD);
        if (i - K + 1 >= 0)
            dp[i + 1].first +=
                modp(modp(dp[i - K + 1].second *
                              modp(static_cast<ll>(pow(2, K - 1) - 1), MOD),
                          MOD) +
                         dp[i - K + 1].first,
                     MOD);
        else
            dp[i + 1].first = modp(dp[i].first + dp[i].second, MOD);
    }
    ll ans = dp[N].first;
    if (N == K) ans--;
    ans = modp(ans, MOD);
    cout << ans << endl;
}

Submission Info

Judge Result