Submission #6345691

---

Source Code Expand

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

int K; ll N;

vector<ll> memo;

ll dp( ll a){
  if( a < 0){ return 0;}
  if( memo[a] != -1){ return memo[a];}
  
  ll res = 0;
  for(ll i = 1; i <= K; i++){
    res += dp(a-i); res %= MOD;}
  
  return memo[a] = res % MOD;}

int main(){
  cin >> K >> N; memo = vector<ll> (N+10,-1);
  for(ll i = 0; i < K; i++){
    memo[i] = 1;}
  cout << dp(N) << endl;
  return 0;}

Submission Info

Judge Result