Submission #1180562


Source Code Expand

// http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp
#include<bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long ll;
typedef pair<ll,ll> P;
const int INF=INT_MAX / 3;
const ll LINF=LLONG_MAX / 3LL;
#define CONST 1000000007LL
#define EPS (1e-8)
#define PB push_back
#define MP make_pair
#define sz(a) ((int)(a).size())
#define reps(i,n,m) for(int i=(n);i<int(m);i++)
#define rep(i,n) reps(i,0,n)
#define SORT(a) sort((a).begin(),(a).end())
ll mod(ll a,ll m){return (a%m+m)%m;}
int dx[9]={0,1,0,-1,1,1,-1,-1,0},dy[9]={1,0,-1,0,1,-1,1,-1,0};
ll n,m, k;

/*
  dp[0][i] = {i番目の駅に止まらない場合の数}
  dp[1][i] = {i番目の駅に止まる場合の数}
  参考: http://kenkoooo.hatenablog.com/entry/2015/03/24/152721
 */
ll dp[2][1000100];

int main(){
  cin >> n >> k;

  dp[0][0] = 1;
  dp[1][1] = 1;
  reps(i, 2, n+1) {
    dp[0][i] = (dp[0][i-1] + dp[1][i-1]) % CONST;
    dp[1][i] = (dp[0][i-1] + dp[1][i-1]) % CONST;
    if(i-k >= 0) {
      dp[1][i] -= dp[0][i-k];
      dp[1][i] += CONST*2;
      dp[1][i] %= CONST;
    }
  }
  assert(dp[1][n] > 0);
  cout << dp[1][n] << endl;
  return 0;
}

Submission Info

Submission Time
Task F - 準急
User udondon
Language C++14 (GCC 5.4.1)
Score 4
Code Size 1331 Byte
Status AC
Exec Time 15 ms
Memory 15872 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 15 ms 15872 KB
01 AC 11 ms 15872 KB
02 AC 8 ms 10496 KB
03 AC 7 ms 10496 KB
04 AC 14 ms 15232 KB
90 AC 2 ms 2304 KB
91 AC 2 ms 2304 KB