Submission #1243436

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

long long M=1000000007;
int main(int argc, char const *argv[]) {
  long long n,k;cin>>n>>k;
  vector<long long> dp(n+1),dp0(n+1),dp1(n+1);
  dp[0]=0;
  // dp[1]=1;
  // dp[2]=(k!=2);
  // dp0[2]=1;
  for(int i=1;i<n+1;++i){
    dp[i]=dp[i-1]+dp0[i-1];
    if(i==1)dp[i]++;
    if(i==k)dp[i]--;
    dp[i]%=M;
    dp0[i]=dp0[i-1]+dp[i-1];
    if(i-k>-1)dp0[i]-=dp[i-k];
    // dp0[i]-=(i==k-1);
    dp0[i]%=M;
    // cout<<dp[i]<<endl;
  }
  // dp
  // for(int i=2;i<n+1;++i){
  //   dp1[i]=dp1[i-1]*2+dp[i-1];
  //   dp1[i]%=M;
  //   if(i<k)dp[i]=0;
  //   else if(i<=k+1)dp[i]=1;
  //   else{
  //     dp[i]+=dp0[i-k+1];
  //     dp[i]+=dp[i-k-1];
  //     dp[i]+=dp1[i-k-1];
  //   }
  //   dp[i]=dp0[i]-dp[i];
  //   dp[i]%=M;
  //   dp[i]+=M;
  //   dp[i]%=M;
  // }
  cout<<dp[n]<<endl;
  return 0;
}

Submission Info

Judge Result