Submission #486530

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int N,K;
	cin >> N >> K;
	vector<vector<long long> > dp(N,vector<long long>(K,0));//dp[i][j]=i+1駅にj連続で止まる
	dp[0][1]=1;
	for(int i=0;i<N-1;i++)
		for(int j=0;j<K;j++){
			if(j+1<K){
				dp[i+1][j+1]+=dp[i][j];
				dp[i+1][j+1]%=1000000007;
			}
			dp[i+1][0]+=dp[i][j];
			dp[i+1][0]%=1000000007;
		}
	long long answer=0;
	for(int i=1;i<K;i++){
		answer+=dp[N-1][i];
		answer%=1000000007;
	}
	cout << answer << endl;
	return 0;
}

Submission Info

Judge Result