Submission #1453739

---

Source Code Expand

#include <bits/stdc++.h>


using namespace std;


// Powered by caide (code generator, tester, and library code inliner)

int n, k;
const int INF = 1e9 + 7;

static int dp[1000003];

class Solution {
public:

  int dfs(int now)
  {
    if (now >= n - 1) {
      return now <= n + 1;
    }
    if (~dp[now]) return dp[now];

    int res = 0;
    
    for (int i = !now; i < k && now + i < n + 1; i++) {
      if (now + i != n - 1) {
        res += dfs(now + i + 1);
      }
      res %= INF;
    }
    return dp[now] = res;
  }

  void solve(std::istream& in, std::ostream& out)
  {
    memset(dp, -1, sizeof dp);
    in >> n >> k;
    out << dfs(0) << "\n";
  }
};

void solve(std::istream& in, std::ostream& out)
{
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}


#include <fstream>
#include <iostream>


int main() {
  
  ios_base::sync_with_stdio(0);
  cin.tie(0);


  istream& in = cin;


  ostream& out = cout;

  solve(in, out);
  return 0;
}

Submission Info

Judge Result