結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2021-09-07 16:21:34 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 5,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 1,732 ms |
コンパイル使用メモリ | 141,416 KB |
実行使用メモリ | 34,620 KB |
最終ジャッジ日時 | 2024-12-23 13:30:39 |
合計ジャッジ時間 | 2,977 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <queue>#include <set>#include <string.h>#include <vector>using namespace std;typedef long long ll;const ll MOD = 1000000007;int main() {int N;cin >> N;ll dp[N + 4][4];memset(dp, 0, sizeof(dp));dp[1][1] = 1;dp[2][2] = 1;dp[3][3] = 1;for (int i = 0; i < N; ++i) {for (int j = 1; j <= 3; ++j) {switch(j) {case 1:dp[i + 2][2] += dp[i][1];dp[i + 3][3] += dp[i][1];dp[i + 2][2] %= MOD;dp[i + 3][3] %= MOD;break;case 2:dp[i + 1][1] += dp[i][2];dp[i + 3][3] += dp[i][2];dp[i + 1][1] %= MOD;dp[i + 3][3] %= MOD;break;case 3:dp[i + 1][1] += dp[i][3];dp[i + 2][2] += dp[i][3];dp[i + 1][1] %= MOD;dp[i + 2][2] %= MOD;break;}}}cout << (dp[N][1] + dp[N][2] + dp[N][3]) % MOD << endl;return 0;}