Submission #1180550
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+1 >= 0) {
dp[1][i] -= dp[1][i-k+1];
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 |
0 |
Code Size |
1335 Byte |
Status |
WA |
Exec Time |
15 ms |
Memory |
15872 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 4 |
Status |
|
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 |
WA |
8 ms |
10496 KB |
03 |
WA |
7 ms |
10496 KB |
04 |
WA |
14 ms |
15232 KB |
90 |
AC |
2 ms |
2304 KB |
91 |
AC |
2 ms |
2304 KB |