Submission #5441174

---

Source Code Expand

// atcoder/tdpc/F/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  while (cin >> n >> k) {
    const int N = 1000000 + 5;
    lli dp[N];
    fill(dp, dp + N, 0);
    dp[0] = 1;
    const lli mod = 1e9 + 7;
    lli sum = 0;
    for (int i = 1; i <= n; ++i) {
      (sum += dp[i - 1]) %= mod;
      if (0 <= i - k + 1) {
        dp[i] = (sum - dp[i - k + 1] + mod) % mod;
      } else {
        dp[i] = sum;
      }
    }
    cout << dp[n-1] << endl;
  }

  return 0;
}

Submission Info

Judge Result