問題文
您是特别讲座“括号序列和着色”的演讲者。今天是
仅由(和)组成的字符串
我决定介绍如何着色 S 。 S 保证括号内不存在矛盾。
S 考虑将所有字符涂成红色或蓝色。
那时
是第 i 个字符
如果支持(和 j 个字符
如果支持),则 S 的 i 从第一个字符开始 j 直到字符的子字符串
计算 S[i,j] 中红色字符的数量 R,蓝色字符的数量 B 当
必须对其进行涂漆以满足 |R-B|≦K 。
计算满足条件的应用颜色的方式总数。 1,000,000,007 求余数。
本题中,括号一致的字符串定义如下。
- 空字符串是括号中没有矛盾的字符串。
- 括号内无矛盾的字符串 对于 A,B , 通过组合 A 和 B 形成的字符串 AB 也是一个带有一致括号的字符串。 对于
- 括号内无矛盾的字符串
对于 A ,字符串
(A)是一个带有一致括号的字符串。另外,这两端(和)据说是对应的。 - 不满足上述任一条件的字符串是括号对应关系不一致的字符串。
入力
输入将以以下形式从标准输入给出。
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 满足第二部分点约束。