結果
問題 | No.2926 Botaoshi |
ユーザー |
![]() |
提出日時 | 2024-10-12 15:32:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,666 bytes |
コンパイル時間 | 5,723 ms |
コンパイル使用メモリ | 312,996 KB |
実行使用メモリ | 14,504 KB |
最終ジャッジ日時 | 2024-10-12 15:32:53 |
合計ジャッジ時間 | 6,242 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define rep(i, n) for(long long i = 0; i < n; i++) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() using namespace std; using lint = long long; using ld = long double; using mint = atcoder::modint998244353; int main() { int n; string s; cin >> n >> s; rep(i, (int)s.size() - 1) { if (s[i] == 'R' && s[i + 1] == 'L') { cout << 0 << endl; return 0; } } vector<vector<mint>> dp(n, vector<mint>(3)); if (s[0] == 'L') { dp[0][0] = mint(1); } else if (s[0] == 'R') { dp[0][1] = mint(1); } else if (s[0] == 'U') { dp[0][2] = mint(1); } else { dp[0][0] = dp[0][1] = dp[0][2] = mint(1); } for (int i = 1; i < n; i++) { if (s[i] == 'L') { dp[i][0] += (dp[i - 1][0] + dp[i - 1][2]); dp[i][1] = dp[i][2] = mint(0); } else if (s[i] == 'R') { dp[i][1] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]); dp[i][0] = dp[i][2] = mint(0); } else if (s[i] == 'U') { dp[i][2] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]); dp[i][0] = dp[i][1] = mint(0); } else { dp[i][0] += (dp[i - 1][0] + dp[i - 1][2]); dp[i][1] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]); dp[i][2] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]); } } /*rep(i, n) { rep(j, 3) { cout << i << " " << j << " " << dp[i][j].val() << endl; } }*/ mint ans = accumulate(ALL(dp[n - 1]), mint(0)); cout << ans.val() << endl; }