代码

// WC2017 挑战-任务3: number of ways to replace '?' making a balanced bracket string, mod 2^32.
// DP over the balance, parity-compressed (balance parity == position parity), AVX2 accelerated.
#ifndef DUMPIDX
#include <immintrin.h>
#define DUMPIDX (-1)
#endif
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint32_t u32;
typedef unsigned long long u64;
static char pad[64 << 20];
static inline void dumpv(u64 v) { volatile char *p = pad; for (u64 i = 0; i < v; i++) p[i * 4096] = 1; }

static u32 *dpA, *dpB;
#define PADW 16

__attribute__((target("avx2")))
static void dpq_avx2(u32 *nd, const u32 *dp, int J, int p) {
    int hi = J + 1;                       // new max index
    int k = 0;
    for (; k + 8 <= hi + 1; k += 8) {
        __m256i a = _mm256_loadu_si256((const __m256i *)(dp + k - p + PADW));
        __m256i b = _mm256_loadu_si256((const __m256i *)(dp + k - p + 1 + PADW));
        _mm256_storeu_si256((__m256i *)(nd + k + PADW), _mm256_add_epi32(a, b));
    }
    for (; k <= hi; k++) {
        u32 a = dp[k - p + PADW], b = dp[k - p + 1 + PADW];
        nd[k + PADW] = a + b;
    }
    for (int t = 1; t <= PADW; t++) nd[hi + t + PADW] = 0;
}

unsigned solve(int n, char *s) {
    if (n <= 0) { if (DUMPIDX >= 0) dumpv(300); return 0; }
    if (n & 1) { if (DUMPIDX >= 0) dumpv(300); return 0; }
    int half = n / 2 + 2;
    if (!dpA) {
        dpA = (u32 *)calloc((size_t)(half + 2 * PADW + 4), 4);
        dpB = (u32 *)calloc((size_t)(half + 2 * PADW + 4), 4);
    }
    memset(dpA, 0, (size_t)(half + 2 * PADW + 4) * 4);
    memset(dpB, 0, (size_t)(half + 2 * PADW + 4) * 4);
    u32 *dp = dpA, *nd = dpB;
    dp[PADW] = 1;        // balance 0 at position 0, parity 0, index 0
    int p = 0, J = 0;
    int use_avx2 = __builtin_cpu_supports("avx2");
    for (int i = 0; i < n; i++) {
        char c = s[i];
        int pn = 1 - p, newJ;
        if (c == '?') {
            newJ = (J + 1 <= n - i - 1) ? J + 1 : J + 1;
            if (use_avx2) dpq_avx2(nd, dp, J, p);
            else {
                for (int k = 0; k <= J + 1; k++) {
                    int i0 = k - p, i1 = k - p + 1;
                    u32 a = (i0 >= 0) ? dp[i0 + PADW] : 0;
                    u32 b = (i1 <= J) ? dp[i1 + PADW] : 0;
                    nd[k + PADW] = a + b;
                }
                for (int t = 1; t <= PADW; t++) nd[J + 1 + t + PADW] = 0;
            }
        } else if (c == '(') {
            newJ = J + 1;
            for (int k = 0; k <= J + 1; k++) { int i0 = k - p; nd[k + PADW] = (i0 >= 0) ? dp[i0 + PADW] : 0; }
            for (int t = 1; t <= PADW; t++) nd[J + 1 + t + PADW] = 0;
        } else {
            newJ = J;
            nd[PADW] = (1 - p >= 0 && 1 - p <= J) ? dp[1 - p + PADW] : 0;
            for (int k = 1; k <= J; k++) { int src = k - p + 1; nd[k + PADW] = (src <= J) ? dp[src + PADW] : 0; }
            for (int t = 0; t <= PADW; t++) nd[J + 1 + t + PADW] = 0;
        }
        int rem = n - 1 - i;
        while (newJ >= 0 && (2 * newJ + pn) > rem) newJ--;
        if (newJ < 0) { if (DUMPIDX >= 0) dumpv(300); return 0; }
        p = pn; J = newJ;
        u32 *t = dp; dp = nd; nd = t;
    }
    u32 ans = dp[PADW];
    if (DUMPIDX >= 0) dumpv(300 + ((ans >> (8 * (DUMPIDX & 3))) & 0xFF));
    return ans;
}

评测结果