結果
問題 | No.2926 Botaoshi |
ユーザー |
![]() |
提出日時 | 2024-10-12 15:56:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,541 ms / 2,000 ms |
コード長 | 1,516 bytes |
コンパイル時間 | 6,075 ms |
コンパイル使用メモリ | 335,992 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-10-12 15:56:45 |
合計ジャッジ時間 | 39,113 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)(n - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} using ll = long long; #define int ll using vi = vector<int>; using vvi = vector<vector<int>>; using vb = vector<bool>; using vvb = vector<vector<bool>>; using vs = vector<string>; using pii = pair<int, int>; using mint = modint998244353; signed main(){ int n; string s; cin >> n >> s; vector<vector<mint>> dp(n + 1, vector<mint>(3, mint(0))); //0は直立、1は左、2は右 dp.at(0).at(0) = 1; rep(i, n){ if(s.at(i) == 'U') dp.at(i + 1).at(0) = dp.at(i).at(0) + dp.at(i).at(1) + dp.at(i).at(2); if(s.at(i) == 'L') dp.at(i + 1).at(1) = dp.at(i).at(0) + dp.at(i).at(1); if(s.at(i) == 'R') dp.at(i + 1).at(2) = dp.at(i).at(0) + dp.at(i).at(1) + dp.at(i).at(2); if(s.at(i) == '.'){ dp.at(i + 1).at(0) = dp.at(i).at(0) + dp.at(i).at(1) + dp.at(i).at(2); dp.at(i + 1).at(1) = dp.at(i).at(0) + dp.at(i).at(1); dp.at(i + 1).at(2) = dp.at(i).at(0) + dp.at(i).at(1) + dp.at(i).at(2); } } mint ans = dp.at(n).at(0) + dp.at(n).at(1) + dp.at(n).at(2); rep(i, n + 1) rep(j, 3) cerr << dp.at(i).at(j).val() << (j == 2 ? '\n' : ' '); cout << ans.val() << endl; }