翻涌 至喷涌
谁能懂 少年汹涌
题目描述
希寇给了你一个长度为 $n$ 的序列 $a$ 和一个长度为 $62$ 的序列 $w$。
对于常数 $L$，定义集合 $f(x)$。集合 $f(x)$ 由以下过程产生：
- 将当前的 $x$ 加入集合。
- 令 $x \leftarrow x + w_{\operatorname{popcount}(x)}$，其中 $\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示中 $1$ 的数量。
- 如果 $x > L$，则结束操作；否则回到步骤 $1$。
请计算 $\bigcup_{i = 1}^{n} f(a_i)$ 的大小。
输入格式
第一行包含两个正整数 $n,L$。
第二行包含 $62$ 个正整数 $w_0,w_1,\dots,w_{61}$。
第三行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$。
输出格式
输出一行一个整数，表示 $\bigcup_{i = 1}^{n} f(a_i)$ 的大小。
样例一
input
3 246
7 2 1 10 3 9 4 8 5 6 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
97 112 72output
42数据范围
对于所有测试数据，均有：
- $n \le 6 \times 10^4$；
- $1 \le L \le 2^{60} - 1$；
- 对于所有 $0 \le i < 62$，均有 $1 \le w_i \le 62$；
- 对于所有 $1 \le i \le n$，均有 $1 \le a_i \le L$。
| 子任务编号 | 分值 | $n \le$ | $L \le$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $3$ | $10^3$ | $10^4$ | A |
| $2$ | $5$ | $6 \times 10^4$ | $2^{30} - 1$ | A |
| $3$ | $10$ | $1$ | $2^{60} - 1$ | 无 |
| $4$ | $12$ | $10$ | 无 | |
| $5$ | $15$ | $10^2$ | 无 | |
| $6$ | $24$ | $3 \times 10^4$ | A | |
| $7$ | $31$ | $6 \times 10^4$ | 无 |
特殊性质 A：对于所有 $0 \le i < 62$，均有 $w_i = i$，且每个 $a_i$ 均在 $[1,L]$ 中独立均匀随机生成。
时间限制：$\texttt{2.5s}$
空间限制：$\texttt{512MB}$
鄂公网安备 42010202000505 号