代码

#pragma GCC target("avx2,tune=native")
#include "immintrin.h"
#include <bits/stdc++.h>

using namespace std;

void _add_n(const __m256i *a, int n, __m256i *b) {
  for (int i = 0; i < n; ++i) {
    b[i] = _mm256_add_epi32(a[i], b[i]);
  }
}
void add_n(const unsigned *a, int n, unsigned *b) {
  _add_n((const __m256i *)a, n / 8, (__m256i*)b);
  for (int i = n - n % 8; i < n; ++i) {
    b[i] += a[i];
  }
}
void add_n_1(const unsigned *a, int n, unsigned *b) {
  for (int i = 0; i < min(n, 7); ++i) {
    b[i] += a[i + 1];
  }
  if (n >= 8) {
    add_n(a + 8, n - 7, b);
  }
}

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) {
        copy_n(dp, sz - 1, pd + 1);
        pd[0] = 0;
      } else {
        copy_n(dp, sz, pd);
      }
    }
    if (s[i] != '(') {
      if (i & 1) {
        add_n(dp, nsz, pd);
      } else {
        add_n_1(dp, nsz, pd);
      }
    }
    swap(pd, dp);
    nsz = sz;
  }
  return dp[0];
}

评测结果