結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2018-05-13 22:01:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 929 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 65,144 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 10:40:27 |
合計ジャッジ時間 | 1,430 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <numeric>#include <map>#include <set>using namespace std;#define REP(i,n) for(int i=0;i<(n);++i)#define REPS(i,s,t) for(int i=(s);i<(t);++i)#define INF 2000000007#define MOD 1000000007#define MAX 1000005typedef unsigned int uint;typedef unsigned long long int ull;typedef long long int ll;int main(){int N;cin>>N;ull DP[5][5];DP[1][0]=1;DP[1][1]=0;DP[1][2]=1;DP[1][3]=2;DP[2][0]=0;DP[2][1]=1;DP[2][2]=1;DP[2][3]=0;DP[3][0]=0;DP[3][1]=0;DP[3][2]=1;DP[3][3]=1;REPS(i,5,N+1){DP[1][4] = (DP[2][3]+DP[3][3])%MOD;DP[2][4] = (DP[1][2]+DP[3][2])%MOD;DP[3][4] = (DP[1][1]+DP[2][1])%MOD;REPS(j,1,4){DP[j][1]=DP[j][2];DP[j][2]=DP[j][3];DP[j][3]=DP[j][4];}}int pos = (N>4) ? 4 : N-1;ull ans = ((DP[1][pos]+DP[2][pos])%MOD+DP[3][pos])%MOD;cout << ans << endl;return 0;}