#2713. 「BalkanOI 2018 Day2」Parentrises

内存限制:256 MiB 时间限制:300 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

如何将两题拼成一题.jpg

翻译自 BalkanOI 2018 Day2 T1「Parentrises

「括号串」是一个仅由 () 构成的字符串。如果在括号串中插入一些 1+ 可以将其转化为正确的表达式,该字符串就是一个「良括号串」。例如,(())(()) 是良括号串,而 )(( 不是。空字符串可视为良括号串。(就是你们学 Catalan 数时学的那个啊)
将一个括号串(不是良括号串)的每个括号都涂成红绿蓝三种颜色之一,如果有一种方案同时满足:

  • 忽略该串的所有蓝色括号后它是良括号串
  • 忽略该串的所有红色括号后它是良括号串;

该串就是 RGB 可读的。

你会接到两类任务之一。任务类型用一个整数 P 表示, P=1 2

  • P=1 :你会接到 T 组询问,每组询问包含一个括号串,试问该串是否 RGB 可读,如果是,请输出一种染色方案,如果否请输出 impossible
  • P=2 :你会接到 T 组询问,每组询问包含一个数 N ,试求:有多少个长度为 N 的 RGB 可读的良括号串。输出答案模 (10^9+7) 的结果。

输入格式

第一行有一个整数 P
第二行有一个整数 T

  • 如果 P=1 ,在接下来的 T 行中,每行有一个括号串,表示询问。
  • 如果 P=2 ,在接下来的 T 行中,每行有一个数 N ,表示询问。

输出格式

如果 P=1 ,对于每组询问,

  • 如果该串是 RGB 可读的,请输出一种染色方案;
  • 如果该串不是 RGB 可读的,请输出 impossible

如果 P=2 ,对于每组询问,请输出长度为 N 的 RGB 可读的良括号串的个数模 (10^9+7) 的结果。

样例

样例输入 1

1
3
())(()
()(()
()))

样例输出 1

GRBRBG
BBRBG
impossible

样例解释 1

对于查询 1,忽略原串的所有蓝色括号后它变为 ()();忽略原串的所有红色括号后它也变为 ()()
对于查询 2,忽略原串的所有蓝色括号后它变为 ();忽略原串的所有红色括号后它变为 ()()

样例输入 2

2
2
6
100

样例输出 2

12
959772055

数据范围与提示

P = 1
L 为字符串总长。

  • 子任务 #1(5 分): 1 ≤ T ≤ 5, 1 ≤ len(S) ≤ 13
  • 子任务 #2(11 分): 1 ≤ L ≤ 100
  • 子任务 #3(6 分): 1 ≤ L ≤ 1000
  • 子任务 #4(28 分): 1 ≤ L ≤ 10^6

P = 2

  • 子任务 #5(6 分): 1 ≤ N, T ≤ 15
  • 子任务 #6(16 分): 1 ≤ N, T ≤ 30
  • 子任务 #7(28 分): 1 ≤ N, T ≤ 300

感谢 applese 提供 SPJ。