#PQJ2560x14581. QOJ 2560_14581

    ID: 2837 传统题 2500ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2026 互测

QOJ 2560_14581

标题: 少年汹涌 - Problem - QOJ.ac

#14581. 少年汹涌

Statistics

翻涌 至喷涌
谁能懂 少年汹涌

题目描述

希寇给了你长为 n 的序列 a 和数组 w。

对于常数 L,定义 f(x) 为如下操作构成的集合:

  1. 将 x 加入集合。
  2. 将 x←x+wpopcount(x),其中 popcount(x) 表示 x 二进制下 1 的个数,若 x>L 结束操作,否则回到第一步。

希寇想知道 ⋃i=1nf(ai) 的大小,你能帮帮他吗?

输入格式

第一行两个正整数 n,L。

第二行一个长度为 62 的数组 w。

第三行一个长度为 n 的数组 a。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

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 72

输出 #1

42

说明/提示

对于所有数据,n≤6×104,1≤wi≤62,1≤ai≤L。

子任务 分值 n≤ L≤ 特殊性质 1 3 103 104 A 2 5 6×104 230−1 3 10 1 260−1 无 4 12 10 5 15 102 6 24 3×104 A 7 31 6×104 无

  • 特殊性质 A:wi=i,ai 在 [1,L] 中均匀随机。