結果
問題 | No.1811 EQUIV Ten |
ユーザー |
![]() |
提出日時 | 2024-11-30 19:22:42 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 911 bytes |
コンパイル時間 | 2,110 ms |
コンパイル使用メモリ | 206,916 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-11-30 19:22:48 |
合計ジャッジ時間 | 3,325 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;using ll = long long;using mint = modint1000000007;int main(){int n; cin >> n;if(n <= 3){cout << 0 << endl;return 0;}vector<vector<mint> > dp(n + 1, vector<mint>(8));for(int j = 0; j < 8; ++j){dp[3][j] = 1;}for(int i = 3; i < n; ++i){dp[i + 1][0] = (dp[i][0] + dp[i][4]);dp[i + 1][1] = (dp[i][0] + dp[i][4]);dp[i + 1][2] = dp[i][1];dp[i + 1][3] = (dp[i][1] + dp[i][5]);dp[i + 1][4] = (dp[i][2] + dp[i][6]);dp[i + 1][5] = (dp[i][2] + dp[i][6]);dp[i + 1][6] = (dp[i][3] + dp[i][7]);dp[i + 1][7] = (dp[i][3] + dp[i][7]);}mint s = 0;for(mint& x : dp[n]){s += x;}mint ans = ((mint)2).pow(n) - s;cout << ans.val() << endl;return 0;}