結果
問題 | No.533 Mysterious Stairs |
ユーザー |
|
提出日時 | 2021-12-16 08:33:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 221 ms / 5,000 ms |
コード長 | 780 bytes |
コンパイル時間 | 1,843 ms |
コンパイル使用メモリ | 174,500 KB |
実行使用メモリ | 104,808 KB |
最終ジャッジ日時 | 2024-09-13 01:39:55 |
合計ジャッジ時間 | 3,750 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long mod = 1000000007;vector<vector<long long>> memo;long long rec(long long n, int cur){if (memo[n][cur] >= 0) return memo[n][cur];memo[n][cur] = 0;if (n- cur - 1 == 0) memo[n][cur] += memo[0][0];if (0 < n - cur - 1){for (int i = 0; i < 3; ++i){if (0 < rec(n - cur - 1, i) && i != cur){memo[n][cur] = (memo[n][cur] + memo[n - cur - 1][i])%mod;}}}return memo[n][cur];}int main(){long long n; cin >> n;memo.assign(n + 1, vector<long long>(3, -1));memo[0][0] = memo[0][1] = memo[0][2] = 1;long long res = 0;for (int i = 0; i < 3; ++i){res = (res + rec(n, i))%mod;}cout << res << endl;}