A2786 | 平衡奶牛品种
来源USACO / 2012
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
农夫约翰通常用圆形标记给他的奶牛打上烙印，但他的烙铁坏了，所以他必须满足于用括号形状的标记给每头奶牛打上烙印——（。他的农场里有两种奶牛：荷斯坦奶牛和根西奶牛。他给每头奶牛打上烙印
括号形标记。根据奶牛面向的方向，这可能看起来像左括号或右括号。
FJ 的 N 头奶牛都站成一排，每头都面向任意方向，因此奶牛上的标记看起来像一串长度为 N 的括号。 这给出了一个平衡的括号字符串;而且，根西岛也是如此！要了解这是否真的是一个罕见的事件，请帮助 FJ 计算他可以为他的 N 头奶牛分配品种的可能方法的数量，以便该属性成立。
有几种方法可以定义一串括号“平衡”的含义。也许最简单的定义是，（'s 和 ）的总数必须相同，并且对于字符串的任何前缀，必须至少有与 ） 一样多的 （'s）。例如，以下字符串都是平衡的：
() (()) ()(()())
显然这些不是：
)( ())( ((())))
结果 mod 2012
括号形标记。根据奶牛面向的方向，这可能看起来像左括号或右括号。
FJ 的 N 头奶牛都站成一排，每头都面向任意方向，因此奶牛上的标记看起来像一串长度为 N 的括号。 这给出了一个平衡的括号字符串;而且，根西岛也是如此！要了解这是否真的是一个罕见的事件，请帮助 FJ 计算他可以为他的 N 头奶牛分配品种的可能方法的数量，以便该属性成立。
有几种方法可以定义一串括号“平衡”的含义。也许最简单的定义是，（'s 和 ）的总数必须相同，并且对于字符串的任何前缀，必须至少有与 ） 一样多的 （'s）。例如，以下字符串都是平衡的：
() (()) ()(()())
显然这些不是：
)( ())( ((())))
结果 mod 2012
输入格式
* 第 1 行：长度为 N （1 <= N <= 1000） 的括号字符串。
输出格式
* 第 1 行：单个整数，指定 FJ 可以将品种分配给奶牛的方式数量，以便荷斯坦奶牛形成括号的平衡子序列，根西岛也是如此。由于答案可能是一个非常大的数字，请在除以 2012 时打印该数字的余数（即打印数字 mod 2012）。仅涉及一种品种类型的品种分配是有效的。
输入输出样例
输入 #1
(())
输出 #1
6
以下品种分配有效：
(()) HHHH (()) GGGG (()) HGGH (()) GHHG (()) HGHG (()) GHGH
(()) HHHH (()) GGGG (()) HGGH (()) GHHG (()) HGHG (()) GHGH
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？