AT_utpc2024_b.Bracket Character Frequency

对于仅由圆括号 (、) 组成的字符串 $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$ 个测试用例，请分别回答每个用例。

输入以标准输入给出，格式如下：

$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

对于第 $1$ 个测试用例，()()()、((()))、(())() 这 $3$ 个括号序列的集合满足条件。对于第 $2$ 个测试用例，不存在满足条件的合法括号序列组。

约束条件

• 所有输入均为整数。
• $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$
• 所有测试用例中，$K$ 的总和不超过 $5 \times 10^{5}$。

由 ChatGPT 5 翻译