代码

unsigned dp[1<<20];
void solve100(int n, unsigned* L, unsigned* R) {
    static unsigned dqb[1<<20];
    unsigned* dq = dqb+100;
    for (int i=-100; i<n+100; ++i) {
        dq[i] = 0;
    }
    for (int i=0; i<100; ++i) {
        dq[i] = dp[i];
    }
    int shift = 0, qmark = 0;
    for (int i=0; i<100; ++i) {
        switch (L[i]) {
        case '(':
            --dq;
            ++shift;
            break;
        case ')':
            0[++dq]=0;
            --shift;
            break;
        case '?':
            for (int j=-1; j<100; ++j)
                dq[j] += dq[j+2];
            --dq;
            ++qmark;
            break;
        }
    }
    int z[202] = {1};
    while (qmark--) {
        for (int i=0; i<200; ++i) {
            z[i+2] += z[i];
        }
        --shift;
    }
    for (int i=0; i<202; ++i) {
        if (z[i])
        for (int j=100; j<n; ++j)
            dq[j] += z[i] * dp[i+shift];
    }
    for (int i=0; i<n; ++i) {
        dp[i] = dq[i];
    }
}
unsigned solve(int n, char* s) {
    dp[0] = 1;
    int i;
    for (i=0; i<n; i+=100) solve100(n, s+i, s+i+100);
    solve100(n, s+i, s+n);
    return dp[0];
}

评测结果