結果

問題 No.1677 mæx
コンテスト
ユーザー t98slider
提出日時 2026-10-18 13:01:36
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 19 ms / 2,000 ms
+ 159µs
コード長 2,342 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,958 ms
コンパイル使用メモリ 380,148 KB
実行使用メモリ 17,152 KB
最終ジャッジ日時 2026-10-18 13:01:44
合計ジャッジ時間 7,469 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

vector<array<ll,3>> dp(200001, array<ll,3>({-1, -1, -1}));
vector<int> T;
vector<vector<int>> g(200001);
string s;
int all, cnt = 1, i;
//type0:m?x
//type1:max
//type2:mex
//type3:?
//type4:0
//type5:1
//type6:2
void dfs(int v){
    i++;
    vector<int> children;
    while(s[i]!=')'){
        if(s[i]=='m'){
            i++;
            if(s[i]=='?')T.push_back(0),g[v].push_back(cnt),dfs(cnt++);
            else if(s[i]=='a')T.push_back(1),g[v].push_back(cnt),dfs(cnt++);
            else if(s[i]=='e')T.push_back(2),g[v].push_back(cnt),dfs(cnt++);
        }else{
            if(s[i]=='?')T.push_back(3),g[v].push_back(cnt++);
            else if(s[i]=='0')T.push_back(4),g[v].push_back(cnt++);
            else if(s[i]=='1')T.push_back(5),g[v].push_back(cnt++);
            else if(s[i]=='2')T.push_back(6),g[v].push_back(cnt++);
        }
        i++;
    }
}

ll rec(int v,int value){
    if(T[v] >= 3){
        if(T[v] == 3) return 1;
        else return (value == T[v] - 4);
    }
    if(dp[v][value] != -1) return dp[v][value];
    mint maxv, mexv, l = 1, r = 1, l2;
    //max処理
    if(T[v] == 0 || T[v] == 1){
        for(auto u : g[v]){
            if(value == 0)r *= rec(u,0);
            else if(value == 1)r *= rec(u,1) + rec(u,0), l *= rec(u,0);
            else if(value == 2)r *= rec(u,2) + rec(u,1) + rec(u,0), l *= rec(u,1) + rec(u,0);
        }
        if(value == 0) l = 0;
        maxv = r - l;
    }
    l = 1, r = 1, l2 = 1;
    if(T[v] == 0 || T[v] == 2){
        for(auto u : g[v]){
            if(value == 0)r *= rec(u,1) + rec(u,2);
            else if(value == 1)r *= rec(u,0) + rec(u,2),l *= rec(u,2);
            else if(value == 2)r *= rec(u,0) + rec(u,1),l *= rec(u,0), l2 *= rec(u,1);
        }
        if(value == 0) l = 0;
        if(value <= 1) l2 = 0;
        mexv = r - l - l2;
    }
    return dp[v][value] = (maxv + mexv).val();
}


int main(){
    cin >> s >> all;
    if(s.size() == 1){
        if(s[0] == '?' || s[0] - '0' == all) cout << "1\n";
        else cout << "0\n";
        return 0;
    }
    if(s[1] == '?') T.push_back(0);
    if(s[1] == 'a') T.push_back(1);
    if(s[1] == 'e') T.push_back(2);
    i = 1;
    dfs(0);
    cout << rec(0, all) << '\n';
}
0