代码

unsigned dp[1<<20];
const int DX = 2;
void solve100(int n, char* L, char* R) {
    static unsigned dqb[1<<20];
    unsigned* dq = dqb+DX;
    for (int i=-DX; i<n+DX; ++i) {
        dq[i] = 0;
    }
    for (int i=0; i<DX; ++i) {
        dq[i] = dp[i];
    }
    int shift = 0, qmark = 0;
    for (int i=0; i<DX; ++i) {
        switch (L[i]) {
        case '(':
            --dq;
            ++shift;
            break;
        case ')':
            0[++dq]=0;
            --shift;
            break;
        case '?':
            for (int j=-1; j<DX; ++j)
                dq[j] += dq[j+2];
            --dq;
            ++qmark;
            break;
        }
    }
    //puts("DEBUGa");for (int i=0; i<10; ++i) printf("dq[%d]=%u\n", i, dq[i]);
    int z[2*DX+2] = {};
    z[qmark*2] = 1;
    //printf ("qmark=%d shift=%d\n", qmark, shift);
    while (qmark--) {
        for (int i=0; i<2*DX; ++i) {
            z[i] += z[i+2];
        }
        --shift;
    }
    for (int i=0; i<2*DX+2; ++i) {
        if (z[i]) {
            for (int j=DX; j<n; ++j)
                dq[j+shift+i] += z[i] * dp[j];
            //printf("DEBUGq %d %u\n", i, z[i]);for (int i=0; i<10; ++i) printf("dq[%d]=%u\n", i, dq[i]);
        }

    }
    for (int i=0; i<n; ++i) {
        dp[i] = dq[i];
    }
    //puts("DEBUGb");for (int i=0; i<10; ++i) printf("dq[%d]=%u\n", i, dq[i]);
}
unsigned solve(int n, char* s) {
    dp[0] = 1;
    int i;
    for (i=0; i<n-DX; i+=DX) solve100(n, s+i, s+i+DX);
    solve100(n, s+i, s+n);
    return dp[0];
}

评测结果