代码

#include <bits/stdc++.h>

using namespace std;

unsigned solve(int n, char *s) {
  int nsz = 1;
  unsigned pool[266672] = {};
  unsigned *dp = pool + 133336;
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    int sz = min(i + 1, n - i - 1) / 2 + 1;
    if (s[i] == '(') {
      if (i & 1) {
        --dp;
        dp[0] = 0;
      }
    } else if (s[i] == ')') {
      if (~i & 1) {
        ++dp;
        dp[sz] = 0;
      }
    } else {
      if (i & 1) {
        --dp;
        dp[0] = 0;
        int i;
        for (i = 0; i + 1 < nsz; i += 2) {
          dp[i] += dp[i + 1];
          dp[i + 1] += dp[i + 2];
        }
        for (; i < nsz; ++i) {
          dp[i] += dp[i + 1];
        }
        dp[sz] = 0;
      } else {
        int i;
        for (i = 0; i + 1 < sz; i += 2) {
          dp[i] += dp[i + 1];
          dp[i + 1] += dp[i + 2];
        }
        for (; i < sz; ++i) {
          dp[i] += dp[i + 1];
        }
        dp[sz] = 0;
      }
    }
    nsz = sz;
  }
  return dp[0];
}

评测结果