結果
問題 | No.2106 Wild Cacco |
ユーザー |
👑 ![]() |
提出日時 | 2022-10-21 22:20:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 1,555 bytes |
コンパイル時間 | 2,662 ms |
コンパイル使用メモリ | 115,284 KB |
最終ジャッジ日時 | 2025-02-08 10:13:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 30 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <atcoder/modint> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ string S; cin >> S; int N = S.size(); vector<Modint> dp0(N+1, 0); vector<Modint> dp1(N+1, 0); dp0[0] = 1; vector<Modint> tmp0(N+1, 0); vector<Modint> tmp1(N+1, 0); auto goL = [&](){ for(int i=N; i>=1; i--) tmp0[i] += dp0[i-1]; for(int i=N; i>=1; i--) tmp1[i] += dp1[i-1]; }; auto goR = [&](){ for(int i=N; i>=1; i--) tmp0[i-1] += dp0[i]; for(int i=N; i>=1; i--) tmp1[i-1] += dp1[i]; }; auto goQ = [&](){ for(int i=N; i>=1; i--) tmp0[i] += dp0[i-1]; for(int i=N; i>=1; i--) tmp1[i-1] += dp1[i]; for(int i=N; i>=1; i--) tmp1[i-1] += dp0[i]; }; for(char c : S){ if(c == '('){ goL(); } if(c == ')'){ goR(); } if(c == '?'){ goQ(); } if(c == '.'){ goL(); goR(); goQ(); } swap(dp0, tmp0); swap(dp1, tmp1); for(auto& a : tmp0) a = 0; for(auto& a : tmp1) a = 0; } Modint ans = dp0[0] + dp1[0]; cout << ans.val() << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;