#P16043. [Oni2023国家队选拔赛]Trim

[Oni2023国家队选拔赛]Trim

题目描述

对于一个用恰好 NN 位二进制表示的正整数 xx,定义操作 trim⁡(x)\operatorname{trim}(x):删除其二进制表示左侧和右侧连续的 00,但保留中间的 00。

例如,当 N=6N=6 时:

  • x=4=0001002x=4=000100_2,则 trim⁡(4)=12\operatorname{trim}(4)=1_2;
  • x=10=0010102x=10=001010_2,则 trim⁡(10)=1012=5\operatorname{trim}(10)=101_2=5。

现在考虑所有整数 1,2,…,2N−11,2,\ldots,2^N-1,它们均用恰好 NN 位二进制表示。对每个数执行 trim⁡\operatorname{trim} 操作后,将得到的数按如下规则排序:

  1. 先按二进制表示中 11 的个数从小到大排序;
  2. 若 11 的个数相同,则按 trim⁡\operatorname{trim} 后的数值从小到大排序。

最后,将排序后的所有数的二进制表示依次拼接成一个长二进制串,位置从左到右编号为 11。

给定 NN 以及 TT 个询问位置 p1,p2,…,pTp_1,p_2,\ldots,p_T,请回答拼接串中这些位置上的比特值。

输入格式

第一行包含两个整数 N,TN,T。

第二行包含 TT 个整数:

p1,p2,…,pT.p_1,p_2,\ldots,p_T.

输出格式

输出一个长度为 TT 的 01 串,不含空格。第 ii 个字符表示位置 pip_i 上的比特。

数据范围

  • 1≤N≤1001\le N\le 100;
  • 2≤T≤1000002\le T\le 100000;
  • 1≤pi≤10181\le p_i\le 10^{18};
  • 保证所有 pip_i 不超过最终拼接串的长度。

子任务

子任务 分值 限制
1 7 N=5N=5 且 pi≤109p_i\le 10^9
2 N≤20N\le 20 且 pi≤109p_i\le 10^9
3 26 N≤60N\le 60 且 pi≤109p_i\le 10^9
4 17 pi≤105p_i\le 10^5
5 26 pi≤5×1010p_i\le 5\times 10^{10}
6 17 无额外限制

样例

样例 1

3 10
7 1 2 3 4 5 6 8 9 10
1111111101

当 N=3N=3 时,初始数为 11 到 77。执行 trim 并排序后得到:

1_2, 1_2, 1_2, 11_2, 11_2, 101_2, 111_2

拼接串为 1111111101111。

样例 2

5 10
1 2 3 4 15 23 19 45 66 99
1111011111