結果
問題 |
No.314 ケンケンパ
|
ユーザー |
![]() |
提出日時 | 2020-01-10 12:55:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 1,000 ms |
コード長 | 1,451 bytes |
コンパイル時間 | 983 ms |
コンパイル使用メモリ | 101,344 KB |
実行使用メモリ | 57,984 KB |
最終ジャッジ日時 | 2024-11-23 21:54:40 |
合計ジャッジ時間 | 1,831 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include<algorithm> #include<cmath> #include<cstdio> #include<functional> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<set> #include<string> #include<utility> #include<vector> using namespace std; typedef long long ll; const ll mod = 1000000007; #define rep(i,n) for(int i=0;i<n;i++) #define repl(i,s,e) for(int i=s;i<e;i++) #define reple(i,s,e) for(int i=s;i<=e;i++) #define revrep(i,n) for(int i=n-1;i>=0;i--) #define all(x) (x).begin(),(x).end() int main() { int N; cin >> N; //ケン:0、パ:1とすると2歩分のパターンは //00→可 //01→可 //10→可 //11→不可 //よって、ケンケンパのコースの末尾が00、01、10のパターンを使用して //動的計画法で計算すればよい if (N == 1) { cout << 1 << endl; return 0; } //dp[i][j][k] := 長さがkで末尾がijのケンケンパのコースの個数を10^9+7で割った数 vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(2, vector<ll>(N + 1, 0))); //auto dp = new vector<vector<vector<ll>>>(2, vector<vector<ll>>(2, vector<ll>(N, 0))); //初期化 dp[0][0][2] = 1; dp[0][1][2] = 1; dp[1][0][2] = 0; //dp[1][1][2] = 1; reple(i, 3, N) { //ケンは2回まで dp[0][0][i] = dp[1][0][i - 1] % mod; dp[0][1][i] = (dp[0][0][i - 1] + dp[1][0][i - 1]) % mod; dp[1][0][i] = dp[0][1][i - 1] % mod; } cout << (dp[0][0][N] + dp[0][1][N] + dp[1][0][N]) % mod << endl; return 0; }