A22497.平衡奶牛品种

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 2012;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int max_diff = n;  // 差值的最大可能值为字符串长度

    // 滚动数组优化：只保留前一步的状态 prev[h][g]
    vector<vector<int>> prev(max_diff + 2, vector<int>(max_diff + 2, 0));
    prev[0][0] = 1;  // 初始状态：h=0, g=0，方案数为1

    for (char c : s) {
        // 当前状态 curr[h][g]，初始化为0
        vector<vector<int>> curr(max_diff + 2, vector<int>(max_diff + 2, 0));
        for (int h = 0; h <= max_diff; ++h) {
            for (int g = 0; g <= max_diff; ++g) {
                if (prev[h][g] == 0) {
                    continue;  // 无方案，跳过
                }
                // 情况1：当前字符分配给 H
                if (c == '(') {
                    if (h + 1 <= max_diff) {
                        curr[h + 1][g] = (curr[h + 1][g] + prev[h][g]) % MOD;
                    }
                } else {
                    if (h >= 1) {
                        curr[h - 1][g] = (curr[h - 1][g] + prev[h][g]) % MOD;
                    }
                }
                // 情况2：当前字符分配给 G
                if (c == '(') {
                    if (g + 1 <= max_diff) {
                        curr[h][g + 1] = (curr[h][g + 1] + prev[h][g]) % MOD;
                    }
                } else {
                    if (g >= 1) {
                        curr[h][g - 1] = (curr[h][g - 1] + prev[h][g]) % MOD;
                    }
                }
            }
        }
        // 滚动更新：当前状态变为下一步的前状态
        prev.swap(curr);
    }

    // 最终答案：h=0 且 g=0 的方案数
    cout << prev[0][0] % MOD << endl;
    return 0;
}