← 返回题目列表

AtCoder · utpc2024_b

B. 括号字符频率

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

配点 : 100 点

問題文

(, ) 仅由…构成的字符串 S 关于以下任一条件满足时,且仅在该情况下 S 该值应乘以正确的括号顺序。 如

  • S 是空字符串。
  • 一些正确的括号序列 A 存在, 由S 是 您也可以写 (, A, ) 是按照此顺序连接的字符串。
  • 有效的非空括号序列 A, B 存在, 由S 是 您也可以写 A, B 是按照此顺序连接的字符串。

整数 N,K 和长度 给出了 2K 整数序列 给出 A=(A_1,A_2,\dots,A_{2K}) 。 对于

满足以下条件 一套 N 请判定是否存在个正确的括号序列的组合。

  • N 个正确的括号序列的长度都是 2K 。
  • 各 i=1, 2, \dots, 2K , 当我输入 N 个正确的括号序列中, i 第一个字母是 ( 是恰好 A_i 。

T 测试用例,因此请逐一回答。

制約

  • 所有输入均为整数
  • 1 \leq T \leq 10^{5}
  • 1 \leq N \leq 10^{12}
  • 1 \leq K \leq 2\times 10^{5}
  • 0 \leq A_i \leq N
  • 1 对于一个输入中包含的测试用例,K 的总和为 5 \times 10^{5} 以下

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case_1}
\mathrm{case_2}
\vdots
\mathrm{case_T}

每个案例均按以下格式给出。 打印

N K
A_1 A_2 \ldots A_{2K}

出力

T 行。i 在线 i 号测试用例中,如果存在满足条件的正确括号序列的组合, Yes ,不存在时为 No 。


入力例 1

2
3 3
3 2 2 0 2 0
3 3
3 0 2 3 1 0

出力例 1

Yes
No

1 个测试用例, ()()(), ((())), (())() 可以得到第 3 对满足条件。 2 号测试用例中,不存在满足条件的正确括号序列的组合。