← 返回题目列表

AtCoder · discovery_2016_final_c

C. 特别讲座“括号序列和着色”

中文机器翻译题面 查看原题

問題文

您是特别讲座“括号序列和着色”的演讲者。今天是 仅由(和)组成的字符串 我决定介绍如何着色 S 。 S 保证括号内不存在矛盾。

S 考虑将所有字符涂成红色或蓝色。 那时 是第 i 个字符 如果支持(和 j 个字符 如果支持),则 S 的 i 从第一个字符开始 j 直到字符的子字符串 计算 S[i,j] 中红色字符的数量 R,蓝色字符的数量 B 当 必须对其进行涂漆以满足 |R-B|≦K 。

计算满足条件的应用颜色的方式总数。 1,000,000,007 求余数。

本题中,括号一致的字符串定义如下。

  1. 空字符串是括号中没有矛盾的字符串。
  2. 括号内无矛盾的字符串 对于 A,B , 通过组合 A 和 B 形成的字符串 AB 也是一个带有一致括号的字符串。 对于
  3. 括号内无矛盾的字符串 对于 A ,字符串(A) 是一个带有一致括号的字符串。另外,这两端(和)据说是对应的。
  4. 不满足上述任一条件的字符串是括号对应关系不一致的字符串。

入力

输入将以以下形式从标准输入给出。

S
K
  • 1 括号行 S (2≦|S|≦3,000) 被给予。 S 保证括号内不存在矛盾。
  • 2 一个整数,表示对行着色时的约束。 打印除以 K(0≦K≦3,000) 被给予。

出力

计算满足条件的应用颜色的方式总数。 1,000,000,007 后的余数。不要忘记最后的换行符。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 2≦|S|≦8 的数据集 如果对满足 10 点。
  • 2≦|S|≦100 的数据集给出正确答案,除了上述部分点外, 10 点。
  • 如果答案对于没有附加约束的数据集是正确的,则进一步 50 获得的总积分 获得 70 点。

入力例 1

()()
0

出力例 1

4
  • 1 信(和 2 信)是3 信(和 4 信)是对应关系。
  • 为了方便起见,红色括号是<>,括号为蓝色。 我们将其表示为[]。
  • 答案是 如何像<]<]、<][>、[><]、[>[>的 4 没错。
  • <><]一样绘画 在S[1,2] 中 |R-B|≦K 不满足约束。
  • 这个案例是 1 满足第二部分点约束。

入力例 2

()()
2

出力例 2

16
  • 答案是 如何像<><>、<><]、<>[]、<>[>、<]<>、<]<]、<][]、<][>、[><>、[><]、[>[]、[>[>、[]<>、[]<]、[][]、[][>的 16 没错。
  • 这个案例是 1 满足第二部分点约束。

入力例 3

(()())
2

出力例 3

50
  • 1 信(和 6 信)、2 信(和 3 信)、4 信(和 5 信)是对应关系。
  • 这个案例是 1 满足第二部分点约束。

入力例 4

()()()()()()()()()()()()()()()()
2

出力例 4

294967268
  • 着色方法总数为 4,294,967,296 但是, 除以 1,000,000,007 所得的余数 294,967,268 。
  • 这个案例是 2 满足第二部分点约束。