Submission #1798235

---

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))

template <ll MOD>
class ModLL {
private:
    ll d_;

private:
    void normalize() { d_ = (MOD + d_ % MOD) % MOD; }

public:
    ModLL() {}
    ModLL(ll d) : d_(d % MOD) {}

    ll get() const { return d_; }

    operator ll() { return d_; }

    ModLL& operator=(const ModLL& rhs)
    {
        d_ = rhs.d_;
        normalize();
    }

    ModLL& operator+=(const ModLL& rhs)
    {
        d_ += rhs.d_;
        normalize();
        return *this;
    }

    ModLL& operator-=(const ModLL& rhs)
    {
        d_ -= rhs.d_;
        normalize();
        return *this;
    }

    ModLL& operator*=(const ModLL& rhs)
    {
        d_ *= rhs.d_;
        normalize();
        return *this;
    }
};

template <ll MOD>
ostream& operator<<(ostream& os, const ModLL<MOD>& rhs)
{
    os << rhs.get();
    return os;
}

using LL = ModLL<1'000'000'007>;

ll K, N;
LL S[2000000];

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

Submission Info

Judge Result