C++(clang++11) 解法, 执行用时: 103ms, 内存消耗: 3032K, 提交时间: 2021-05-09 20:42:20

#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#ifdef XLor
  #include <iostream>
  #define dbg(args...) cout << "\033[32;1m" << #args << " -> ", err(args)
  void err() { std::cout << "\033[39;0m" << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
const int mod = 998244353;
const int maxn = 10000 + 5;

inline int add(int x, int y) {
  x += y;
  return x >= mod ? x -= mod : x;
}
inline int mul(int x, int y) {
  return 1ll * x * y % mod;
}

namespace Comb {
  const int maxc = 100000 + 5;
  int f[maxc], inv[maxc], finv[maxc];
  void init() {
    inv[1] = 1;
    for (int i = 2; i < maxc; i++)
      inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
    f[0] = finv[0] = 1;
    for (int i = 1; i < maxc; i++) {
      f[i] = f[i - 1] * 1ll * i % mod;
      finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
    }
  }
  int C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
  }
}
using Comb::C;

int n, siz[maxn * 4];
char s[maxn * 4];

namespace Parser {
  vector<int> edge[maxn * 4];
  int i, tot;

  int factor();
  int term();
  int expr();

  void clear() {
    for (int i = 0; i <= tot; i++) {
      edge[i].clear();
    }
    tot = 0;
    i = 1;
  }

  int factor() {
    if (s[i] == '(') {
      i++;
      int rt = expr();
      assert(s[i] == ')');
      i++;
      return rt;
    } else {
      i++;
      return ++tot;
    }
  }
  int term() {
    int first = factor();
    if (s[i] != '*') {
      return first;
    } else {
      int rt = ++tot;
      edge[rt].push_back(first);
      while (i <= n && s[i] == '*') {
        i++;
        edge[rt].push_back(factor());
      }
      return rt;
    }
  }
  int expr() {
    int first = term();
    if (s[i] != '+') {
      return first;
    } else {
      int rt = ++tot;
      edge[rt].push_back(first);
      while (i <= n && s[i] == '+') {
        i++;
        edge[rt].push_back(term());
      }
      return rt;
    }
  }
}
using Parser::edge;

int f[maxn * 2], g[maxn * 2];
int solve(int u, const vector<int>& a) {
  int sum = 0;
  for (int i = 0; i <= siz[u] + 1; i++) {
    f[i] = g[i] = 0;
  }
  for (int i = 0; i < a.size(); i++) {
    int x = a[i];
    if (i == 0) {
      sum = x;
      f[sum] = 1;
    } else {
      for (int i = 1; i <= sum; i++) {
        f[i] = add(f[i], f[i - 1]);
      }
      g[sum] = f[sum];
      for (int i = sum - 1; i >= 0; i--) {
        g[i] = add(f[i], g[i + 1]);
      }
      for (int i = 0; i <= sum; i++) {
        f[i] = 0;
      }
      if (x == 0) {
        f[0] = g[0];
      } else {
        for (int i = 0; i <= sum; i++) {
          f[i + x] = mul(C(i + x - 1, i), g[i]);
        }
      }
      sum += x + 1;
    }
  }
  int ans = 0;
  for (int i = 0; i <= sum; i++) {
    ans = add(ans, f[i]);
  }
  return ans;
}

int dfs(int u) {
  if (edge[u].empty()) {
    siz[u] = 0;
    return 1;
  }
  siz[u] = (int)edge[u].size() - 1;
  int ans = 1;
  vector<int> vec;
  for (int i = 0; i < edge[u].size(); i++) {
    int v = edge[u][i];
    ans = mul(ans, dfs(v));
    siz[u] += siz[v];
    vec.push_back(siz[v]);
  }
  return mul(ans, solve(u, vec));
}

int main() {
  Comb::init();
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    Parser::clear();
    printf("%d\n", dfs(Parser::expr()));
  }
  return 0;
}