P11883 [RMI 2024] 信号 / Signals

2025/04/16：加入一份 hack 数据（#34）（[source](https://www.luogu.com.cn/ticket/XQRX670885)）。

给定长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 和正整数 $k$。 你需要构造一个长度为 $n$ 的非负整数序列 $b_1,b_2,\ldots,b_n$，满足： - $\forall 1\le i\le n$，$b_i\in [0, 2^k)$； - $\forall 1\le i\le n$，$\operatorname{popcount}(b_i \oplus b_{i\bmod n+1})=a_i$。 或者报告不存在合法解。 这里，$\oplus$ 代表按位异或运算，$\operatorname{popcount}(n)$ 表示非负整数 $n$ 二进制表示下 $1$ 的个数。 特别地，如果你正确地判断了解的存在性，也可以得到部分分，见【计分方式】。

**本题单个测试点内含有多组测试数据。** 第一行，正整数 $T$，表示测试数据组数。 接下来描述 $T$ 组测试数据： 每组数据第一行，两个正整数 $n,k$。 每组数据第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

对于每组数据，如果无解，输出一行一个 $\texttt{NO}$； 否则输出 $(n+1)$ 行，第一行输出 $\texttt{YES}$，接下来 $n$ 行，第 $i$ 行一个长度为 $k$ 的 $\texttt{01}$ 串，表示 $b_i$ 二进制表示下的低 $k$ 位。

### 数据范围 对于 $100\%$ 的数据，保证： - $1\le T\le 10^5$； - $2\le n$； - $1\le k$； - $2\le nk,\sum nk\le 5\times 10^6$； - $0\le a_i\le k$。 --- - $\text{Subtask 0 (0 pts)}$：样例。 - $\text{Subtask 1 (5 pts)}$：$T,n,k\le 5$。 - $\text{Subtask 2 (2 pts)}$：$k=1$。 - $\text{Subtask 3 (8 pts)}$：$k=2$。 - $\text{Subtask 4 (32 pts)}$：$a_i\le k/2$。 - $\text{Subtask 5 (24 pts)}$：$n\le 5\times 10^4$，$k\le 20$。 - $\text{Subtask 6 (29 pts)}$：无额外约束。 ### 计分方式 如果你正确地判断了解的存在性，但是构造的解不正确，你可以获得 $50\%$ 的分数。 如果你只想获得 $50\%$ 的分数，也要保证输出格式正确，否则将无法得分。 每个子任务的分数为其中每个测试点分数的最小值。