結果

問題 No.1677 mæx
コンテスト
ユーザー sak
提出日時 2021-08-05 14:04:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 4,133 bytes
コンパイル時間 2,725 ms
コンパイル使用メモリ 213,740 KB
最終ジャッジ日時 2025-01-23 14:14:57
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

const ll MOD = 998244353;
struct MLL {
  ll x, mod;
  MLL(ll y=0, ll m=MOD) { x = (y%m+m)%m; mod = m; }

  MLL &operator+= (const MLL &p) { x = (x+p.x)%mod;       return *this; }
  MLL &operator-= (const MLL &p) { x = (x-p.x+mod)%mod;   return *this; }
  MLL &operator*= (const MLL &p) { x = (x*p.x)%mod;       return *this; }
  MLL &operator/= (const MLL &p) { x = (x*p.inv().x)%mod; return *this; }
  MLL  operator+  (const MLL &p) const { return MLL(*this)+=p; }
  MLL  operator-  (const MLL &p) const { return MLL(*this)-=p; }
  MLL  operator*  (const MLL &p) const { return MLL(*this)*=p; }
  MLL  operator/  (const MLL &p) const { return MLL(*this)/=p; }
  bool operator== (const MLL &p) const { return x==p.x; }
  bool operator!= (const MLL &p) const { return x!=p.x; }
  bool operator<  (const MLL &p) const { return x< p.x; }
  bool operator<= (const MLL &p) const { return x<=p.x; }
  bool operator>  (const MLL &p) const { return x> p.x; }
  bool operator>= (const MLL &p) const { return x>=p.x; }
  MLL pow(MLL n) const { MLL result(1), p(x); ll tn = n.x; while(tn){ if (tn&1) result*=p; p*=p; tn>>=1; } return result; }
  MLL inv() const { return pow(MOD-2); }
};

MLL operator+ (ll x, MLL p) { return (MLL)x+p; }
MLL operator- (ll x, MLL p) { return (MLL)x-p; }
MLL operator* (ll x, MLL p) { return (MLL)x*p; }
MLL operator/ (ll x, MLL p) { return (MLL)x/p; }

vector<MLL> fac;
void c_fac(ll x=pow(10,7)+10) { fac.resize(x); rep(i,x) fac[i] = i ? fac[i-1]*i : 1; }
MLL nck(MLL n, MLL k) { return fac[n.x]/(fac[k.x]*fac[(n-k).x]); };

ostream &operator<< (ostream &ost, const MLL &p) { return ost << p.x; }
istream &operator>> (istream &ist, MLL &p) { return ist >> p.x; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

vector<MLL> cmax(vector<MLL> v1, vector<MLL> v2) {
  return {
    v1[0]*v2[0],
    v1[0]*v2[1] + v1[1]*v2[0] + v1[1]*v2[1],
    v1[0]*v2[2] + v1[1]*v2[2] + v1[2]*v2[0] + v1[2]*v2[1] + v1[2]*v2[2],
  };
}

vector<MLL> cmex(vector<MLL> v1, vector<MLL> v2) {
  return {
    v1[1]*v2[1] + v1[1]*v2[2] + v1[2]*v2[1] + v1[2]*v2[2],
    v1[0]*v2[0] + v1[0]*v2[2] + v1[2]*v2[0],
    v1[0]*v2[1] + v1[1]*v2[0]
  };
}

vector<MLL> cm_x(vector<MLL> v1, vector<MLL> v2) {
  vector<MLL> ma = cmax(v1, v2), me = cmex(v1, v2);
  return {
    ma[0] + me[0],
    ma[1] + me[1],
    ma[2] + me[2]
  };
}

int main() {
  string S; cin >> S;
  ll K; cin >> K;
  assert(1<=S.size() && S.size()<=2*pow(10,5));
  assert(K==0||K==1||K==2);

  stack<string> op;
  stack<vector<MLL>> dp;
  for (int i=0; i<S.size();) {
    if (S[i]==',') { i++; continue; }
    else if (S[i]=='m') { op.push(S.substr(i,3)); i+=4; }
    else if (S[i]==')') {
      vector<MLL> n1 = dp.top(); dp.pop();
      vector<MLL> n2 = dp.top(); dp.pop();
      string o = op.top(); op.pop();
      if      (o=="max") dp.push(cmax(n1,n2)); 
      else if (o=="mex") dp.push(cmex(n1,n2)); 
      else if (o=="m?x") dp.push(cm_x(n1,n2));
      else assert(false);
      i++;
    }
    else {
      if      (S[i]=='?') dp.push({1,1,1});
      else if (S[i]=='0') dp.push({1,0,0});
      else if (S[i]=='1') dp.push({0,1,0});
      else if (S[i]=='2') dp.push({0,0,1});
      else assert(false);
      i++;
    }
  }

  assert(op.size()==0 && dp.size()==1);
  MLL result = dp.top()[K];
  cout << result << endl;
  return 0;
}
0