結果
問題 | No.1677 mæx |
ユーザー |
![]() |
提出日時 | 2022-11-15 23:18:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,095 bytes |
コンパイル時間 | 4,173 ms |
コンパイル使用メモリ | 254,248 KB |
最終ジャッジ日時 | 2025-02-08 20:28:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using mint = modint998244353; int mex(int x, int y) { if( x > y ) swap(x, y); if( x == 0 ) { if( y == 1 ) { return 2; }else { return 1; } }else { return 0; } } bool isnumber(char c) { return ( c == '?' || isdigit(c) ); } vector<mint> number(string& S, int& i) { vector<mint> dp(3); for( int j = 0; j < 3; j++ ) { if( S[i] == '?' || S[i]-'0' == j ) dp[j]++; } i += 1; return dp; } vector<mint> expression(string& S, int& i) { vector<mint> dp(3), lp(3), rp(3); if( isnumber(S[i]) ) { return number(S, i); }else { char op = S[i+1]; i += 4; lp = expression(S, i); i += 1; rp = expression(S, i); for( int j = 0; j < 3; j++ ) { for( int k = 0; k < 3; k++ ) { if( op != 'e' ) dp[max(j, k)] += lp[j]*rp[k]; if( op != 'a' ) dp[mex(j, k)] += lp[j]*rp[k]; } } } i += 1; return dp; } int main() { int K, i = 0; string S; cin >> S >> K; cout << expression(S, i)[K].val() << endl; }