Codeforces Round #404 (Div.2) D. Anton and School - 2

問題文

http://codeforces.com/contest/785/problem/D

解法

条件に合う部分列の，一番右端の "(" の位置を総当りして計算します．
その位置から左に（その位置自体も含めて）"(" が $x$ 個あり，右に ")" が $y$ 個ある時，求める答えは $\displaystyle \sum_{i = 1}^{\min (x, y)}({_{x-1}C_{i-1}} \times {_yC_i})$ となります．簡単のため $x < y$ の時を考えます．
右辺の各 i についての式 $_{x-1}C_{i-1} \times _yC_i$ が意味するものを考えます．式変形して，$_{x-1}C_{x-i} \times _yC_i$ としておきます．
これは $x - 1$ 人からなるグループから $x - i$ 人を選び，$y$ 人からなるグループから $i$ 人を選ぶ組み合わせに対応します．つまり，$x - 1 + y$ 人から $x$ 人を選ぶ方法のうち，$x - 1$ 人の方から $x - i$ 人を選ぶときの組み合わせに対応します．
すると，$i$ を $1$ から $x$ まで動かした時，$x - 1 + y$ 人から $x$ 人を選ぶ方法すべてを網羅することになります．よって，
$\displaystyle \sum_{i = 1}^{x}({_{x-1}C_{i-1}} \times {_yC_i}) = _{x+y-1}C_x$
が成り立ち，求めたい値を O(1) で求めることができます．（前計算は必要です．）

・おまけ
ちょっと一般化すると
$\displaystyle \sum_{i=0}^z{_xC_i}{_yC_{z-i}} = _{x+y}C_{z}~ (z \leq x)$
で，$z = x$ とすれば
$\displaystyle \sum_{i=0}^x{_xC_i}{_yC_i} = _{x+y}C_{x}$

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// modulo は略

const int MOD = 1000000007;
using mod = modulo<MOD, true>;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> left(n + 1), right(n + 1);
    for(int i = 0; i < n; ++i) {
        left[i + 1] = left[i] + (s[i] == '(');
        right[n - i - 1] = right[n - i] + (s[n - i - 1] == ')');
    }
    mod res = 0;
    for(int i = 1; i <= n; ++i) {
        if(s[i - 1] != '(') {
            continue;
        }
        if(right[i] != 0) {
            res += comb<MOD>(left[i] + right[i] - 1, left[i]);
        }
    }
    cout << (ll)res << endl;
}

感想

式はすぐ出て来るが，変形で詰まった．