# P3058 [USACO12NOV]平衡的奶牛品种Balanced Cow Breeds

• 69通过
• 136提交
• 题目提供者 FarmerJohn2
• 评测方式 云端评测
• 标签 USACO 2012 高性能
• 难度 提高+/省选-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目背景

征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

## 题目描述

Farmer John usually brands his cows with a circular mark, but his branding iron is broken, so he instead must settle for branding each cow with a mark in the shape of a parenthesis -- (. He has two breeds of cows on his farm: Holsteins and Guernseys. He brands each of his cows with a

parenthesis-shaped mark. Depending on which direction the cow is facing, this might look like either a left parenthesis or a right parenthesis.

FJ's N cows are all standing in a row, each facing an arbitrary direction, so the marks on the cows look like a string of parentheses of length N. Looking at this lineup, FJ sees a remarkable pattern: if he scans from left to right through just the Holsteins (in the order they appear in the sequence), this gives a balanced string of parentheses; moreover, the same is true for the Guernseys! To see if this is truly a rare event, please help FJ compute the number of possible ways he could assign breeds to his N cows so that this property holds.

There are several ways to define what it means for a string of parentheses to be "balanced". Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, the following strings are all balanced:

() (()) ()(()())

while these are not:

)( ())( ((())))

给一个只有左右括号的字符串，然后用H,G两种字符来标记这个序列，所有标记H的括号可以组成一个正确的括号序列，所有G标记的括号也组成一个正确的括号序列，然后输出这种标记方案的总数mod2012的值。

## 输入输出格式

输入格式：

* Line 1: A string of parentheses of length N (1 <= N <= 1000).

输出格式：

* Line 1: A single integer, specifying the number of ways FJ can assign breeds to cows so that the Holsteins form a balanced subsequence of parentheses, and likewise for the Guernseys. Since the answer might be a very large number, please print the remainder of this number when divided by 2012 (i.e., print the number mod 2012). Breed assignments involving only one breed type are valid.

## 输入输出样例

输入样例#1： 复制
(())

输出样例#1： 复制
6


## 说明

The following breed assignments work:

(()) HHHH (()) GGGG (()) HGGH (()) GHHG (()) HGHG (()) GHGH

感谢@CREEPER_ 提供翻译

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。