代码

#include <bits/stdc++.h>

using namespace std;

void add_n(const unsigned *a, int n, unsigned *b) {
  int i = 0;
  for (; i < n - 7; i += 8) {
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
    *b++ += *a++;
  }
  for (; i < n; ++i) {
    *b++ += *a++;
  }
}

unsigned solve(int n, char *s) {
  int nsz = 1;
  unsigned *dp = new unsigned[n / 2 + 1]();
  unsigned *pd = new unsigned[n / 2 + 1];
  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) {
        move_backward(dp, dp + sz - 1, dp + sz);
        dp[0] = 0;
      }
      nsz = sz;
    } else if (s[i] == ')') {
      if (~i & 1) {
        move(dp + 1, dp + 1 + sz, dp);
      }
      nsz = sz;
    } else {
      if (i & 1) {
        move_backward(dp, dp + sz, dp + sz + 1);
        dp[0] = 0;
        add_n(dp + 1, sz, dp);
        dp[sz] = 0;
        nsz = sz;
      } else {
        copy_n(dp, sz, pd);
        add_n(dp + 1, sz, pd);
        swap(pd, dp);
        nsz = sz;
      }
    }
  }
  return dp[0];
}

评测结果