#1958. 少年汹涌

少年汹涌

少年汹涌

题目描述

标题: 少年汹涌 - 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] 中均匀随机。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
42

样例 2

1000 10000
1 2 3 4 5 6 7 8 9 10 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
2145 5993 8543 3395 9543 5138 8802 3198 9856 1574 8243 8179 667 4869 4772 4947 127 9010 2672 9565 610 698 6642 9889 1413 1584 4153 5931 1306 6311 7358 569 2960 7851 1803 1842 8403 1830 6626 2317 2544 5534 2423 6751 1136 422 7318 3840 6257 4785 6538 1964 9551 1535 9679 7788 4651 6607 8016 557 9697 886 8065 2174 4189 4308 4994 2443 2305 7252 1311 768 8923 3123 6799 2313 4380 8207 9242 2379 8714 7397 5319 6855 8111 7523 4727 7351 9312 9021 8455 4503 9273 9106 9267 5538 9701 7270 8140 9135 5341 2426 2850 2901 2368 7037 9229 9739 6886 8853 248 4169 859 8853 6693 5949 3450 5631 8103 9252 9816 2187 3528 6500 9331 5625 6795 2367 4497 6456 1359 3313 4882 8609 3262 609 2172 4248 2061 4162 3748 5286 3298 6105 3942 3031 1117 1783 6853 5106 6744 2563 4172 2833 4956 3616 9995 7974 1026 8342 2865 4721 6307 4409 1408 9402 150 2799 4103 448 2334 1816 5702 9253 4252 7928 3153 3724 2344 2158 9931 9609 2307 8848 4027 6219 6411 9853 8513 6600 9579 2411 1446 2875 363 8925 6111 4755 4943 4034 1314 946 6627 2785 1396 8769 242 9652 1018 1765 561 476 965 1464 4448 3446 4818 1160 2856 7860 2493 5166 1173 4096 5094 6644 1937 5987 6289 2491 3504 134 9271 4930 8856 6385 8208 8324 7344 6550 8429 6646 5592 9518 5340 3706 2120 2436 1498 880 3335 4203 577 2868 318 5475 7526 5804 2673 1516 6850 2026 7141 115 1767 5173 9124 3065 5485 5764 5443 3363 2378 9423 8637 4349 8715 7684 2753 8735 3151 2664 8059 3662 4721 5560 6252 9880 2246 9967 9974 4074 5568 836 9748 2734 3901 5263 9391 9703 1094 9220 4468 2667 7189 6072 809 5229 972 3570 923 2041 7363 9284 6332 4940 6488 1538 2668 7083 1097 1949 2036 3821 2937 1145 7668 8841 4470 289 6098 854 8146 9724 4859 445 2054 7863 3866 1470 5025 9017 2039 2514 2909 8779 481 6936 3553 4810 3390 4214 434 7106 2490 3092 6263 1810 313 5323 4312 3068 3182 6383 2548 4655 6412 1877 1298 5101 4496 1911 6972 7084 3538 7403 2369 9775 8503 9690 3089 6724 8308 5269 1902 6161 2482 6270 5536 5823 7384 3237 120 2787 1767 1847 9681 3412 134 4472 1038 545 7862 9082 4914 4455 3210 3184 3395 6545 3796 6282 2018 8072 5696 5176 1707 6853 2520 2655 4843 5834 7380 3007 9983 3092 7091 6909 1763 4781 4039 7081 6216 8881 3999 2776 7695 6626 4915 1410 3714 2383 4895 7318 4700 1033 5794 613 8809 3579 3494 212 7911 8393 8049 2749 8267 1453 8096 6171 8912 3600 743 7784 4467 5481 5476 2139 953 1920 9608 7486 160 5437 8967 9123 3393 8944 4927 4741 2002 6254 4313 7456 7546 740 4109 6597 158 9008 6196 777 6377 9429 3066 7190 5240 8185 1656 4622 2629 2517 9557 4918 3662 422 9582 1255 741 9373 2125 945 7863 6134 5329 2748 4130 6860 4894 5737 3608 891 515 3357 2385 3102 8422 18 6053 5032 8592 9168 6313 1933 5944 7410 3349 1342 5884 1307 2019 9023 2081 9297 3983 2360 4048 904 3482 5584 1671 3709 6171 4283 3360 4532 8469 739 1153 4757 1187 1479 7565 4492 656 5008 9974 6571 1150 7324 1961 7809 387 5062 8405 4913 630 5653 9546 1762 1281 7900 9354 6447 6610 1401 8613 4668 4790 2482 3548 9448 924 843 8742 9588 4032 5554 797 9691 8888 4017 3865 5502 9376 6629 4071 6938 5978 3036 9564 9760 7617 2468 3201 2925 9028 1714 611 291 3666 3759 839 4283 3773 1836 2263 2999 5233 7555 3820 5077 2207 6861 7149 251 744 7888 1819 3208 9511 6846 2654 4504 5608 3676 362 605 1497 2577 5735 9425 8837 5102 7123 2585 5863 786 8580 5570 8174 3781 154 8411 5511 8855 1001 9454 6211 7694 8214 6547 8414 2492 2092 6671 4464 5384 7200 3893 6428 2790 3244 1413 7218 2399 8618 3232 6233 4768 8321 5919 1545 1815 7459 8898 3662 2495 2833 1562 1264 5521 7314 7906 1357 7707 2593 9947 7853 9892 9587 7685 421 1382 8766 5585 679 2729 893 7790 1628 7877 9939 2513 8466 9509 5729 9973 8881 6871 7391 2079 3370 5850 7455 5007 5923 9835 2019 925 1458 2914 7823 6873 6726 7845 7097 6126 6993 9947 8437 7647 4094 6809 6204 80 5392 5477 3005 1625 8170 3352 556 7167 7443 6340 8604 2968 4769 2022 8546 654 9739 68 5541 2373 3844 5088 5574 4552 893 6583 3053 5091 5977 6722 3213 3267 7993 3574 5762 9495 830 4442 2255 6841 6728 7276 132 4034 803 2897 5165 9772 2886 5925 1680 2413 7529 4405 769 8619 1815 1163 7373 8541 7404 4279 1615 6910 9516 24 6675 7807 4409 343 8870 794 2859 1286 4352 3216 3259 6488 5257 3003 8846 6764 1071 2882 4208 6900 1597 8239 4772 2284 6650 9728 8127 7124 242 9751 3785 5666 8277 6651 882 8353 8920 1916 6433 6297 934 8906 4670 5740 2640 9623 6402 9666 4322 8403 400 4758 6392 4498 1903 9329 6905 6004 8575 6845 3621 7005 3597 8511 4119 3892 3420 7726 6638 7745 7171 634 2654 1078 1109 5764 1409 3441 9824 1863 9682 8352 9754 6232 7198 6901 5669 4052 1097 9865 4231 8275 9720 228 8363 4407 6914 8291 4323 8412 5932 5578 8000 6790 4568 2428 8515 4050 7564 9065 3695 3911 5241 4010 7955 5923 5844 6457 2426 9151 30 7300 9397 4113 388 9447 7050 4816 2434 5154 497 3363 3043 6578 3649 6890 8222 2131 5791 3569 7158 622 9230 1050 8867 2584 2662 5712 2493 5041 9340 1751 3688 5950 8836 6824 2353 5831 4412 3335 23 912 8132 4528 914 8590 3706 688 6305 2267 7787 3810 627 38 7466 4658 7597 6684
4948