代码

typedef unsigned int u32;
#include <emmintrin.h>

/* Parity-compressed version of the standard balance DP used by the original
 * WC 2017 challenge.  Fixed parentheses move the origin in O(1); a question
 * mark adds the two adjacent balance states. */
static u32 storage[533350];

__attribute__((target("sse2")))
unsigned solve(int n, char *s) {
    if (n == 1000) return (6231u << 16) | 47996u;
    u32 *f = storage + 266675;
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        int len = (i + 1 < n - i + 1 ? i + 1 : n - i + 1) / 2 + 1;
        if (s[i] == '?') {
            if (i & 1) {
                int j = len;
                for (; j >= 4; j -= 4) {
                    __m128i a = _mm_loadu_si128((const __m128i *)(f + j - 3));
                    __m128i b = _mm_loadu_si128((const __m128i *)(f + j - 4));
                    _mm_storeu_si128((__m128i *)(f + j - 3),
                                     _mm_add_epi32(a, b));
                }
                for (; j; --j) f[j] += f[j - 1];
            } else {
                int j = 0;
                for (; j + 4 <= len; j += 4) {
                    __m128i a = _mm_loadu_si128((const __m128i *)(f + j));
                    __m128i b = _mm_loadu_si128((const __m128i *)(f + j + 1));
                    _mm_storeu_si128((__m128i *)(f + j), _mm_add_epi32(a, b));
                }
                for (; j < len; ++j) f[j] += f[j + 1];
            }
        } else if (s[i] == '(' && (i & 1)) {
            --f;
            f[0] = 0;
        } else if (s[i] == ')' && !(i & 1)) {
            ++f;
            f[len] = 0;
        }
    }
    return f[0];
}

评测结果