mayoko’s diary

プロコンとかいろいろ。

DDPC C - 特別講演「括弧列と塗り分け」

解法

valid な括弧列は木構造になっています。例えば入力例 3 では, でっかい括弧から, 小さい括弧 2 つに向かって辺が伸びている木グラフであると考えることが出来ます。一つの頂点は 2 つの括弧 () に対応している感じです。

すると, 問題は dp[v][b] = (頂点 v から, 青い括弧が b 個あるようなものの場合の数) というのを解ければ解決です。これを素直にやると O(N^3) ですが, ケチケチやると O(N^2) で解けます。yukicoder の問題を参考に。というかこの問題とほとんど同じだったと言っても良いかもしれません。
No.196 典型DP (1) - yukicoder

const int MAXN = 3030;
const ll MOD = 1e9+7;
int to[MAXN];
int K;

vector<int> G[MAXN];

vector<ll> dfs(int v, int p) {
    vector<ll> ret(1, 1);
    for (int ch : G[v]) {
        if (ch == p) continue;
        vector<ll> tmp = dfs(ch, v);
        int n = ret.size(), m = tmp.size();
        vector<ll> nret(n+m-1);
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            nret[i+j] += ret[i] * tmp[j] % MOD;
            nret[i+j] %= MOD;
        }
        ret = nret;
    }
    vector<ll> x = ret;
    ret.push_back(0); ret.push_back(0);
    fill(ret.begin(), ret.end(), 0);
    for (int i = 0; i < (int)(x.size()); i++) {
        ret[i] += x[i];
        ret[i+1] += 2*x[i];
        ret[i+2] += x[i];
    }
    int n = ret.size();
    n--;
    for (int b = 0; b <= n; b++) {
        int r = n-b;
        if (abs(r-b) > K) ret[b] = 0;
        ret[b] %= MOD;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    cin >> K;
    stack<pair<char, int> > st;
    int N = s.size();
    for (int i = 0; i < N; i++) {
        if (s[i] == '(') st.push(make_pair(s[i], i));
        else {
            auto p = st.top(); st.pop();
            to[p.second] = i;
            to[i] = p.second;
        }
    }
    map<pii, int> mp;
    int size = 0;
    for (int i = 0; i < N; i++) {
        if (i < to[i]) mp.insert(make_pair(pii(i, to[i]), size++));
    }
    // グラフを作る
    for (int l = 0; l < N; l++) {
        int r = to[l];
        if (r-l <= 1) continue;
        int index = mp[pii(l, r)];
        for (int nl = l+1; nl < r; nl++) {
            G[index].push_back(mp[pii(nl, to[nl])]);
            nl = to[nl];
        }
    }
    ll ans = 1;
    for (int l = 0; l < N; l++) {
        int index = mp[pii(l, to[l])];
        vector<ll> tmp = dfs(index, -1);
        ll mult = 0;
        for (ll el : tmp) mult += el;
        (ans *= mult%MOD) %= MOD;
        l = to[l];
    }
    cout << ans << endl;
    return 0;
}