Responsive image

问题 2408 --最大集合（线性dp+位运算）

2408: 最大集合（线性dp+位运算）

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

给你一个由n个不同的正整数组成的 数组 a 。
让我们考虑一个最大集合 S ，它包含了所有符合以下条件的 x
1.x = ai (1<=x<=n)
2.x = y*2+1 (y属于S)
3.x = y*4 (y属于S)
找到满足 S 中的元素在小于2^p 时，集合 S 最多有多少个元素
答案可能过大，所以结果对10^9+7取模；

输入描述

第一行包含两个整数n和p (1≤n,p≤200000).

第二行包含n整数a1,a2,…,an (1≤ai≤10^9).

输出描述

一个整数，表示最大元素数量

样例输入

2 4 
6 1

样例输出

9

提示

题解：

完整题解：https://codeforces.com/blog/entry/100153

来源

codeforces，1635D 

[提交][状态]
ACM算法攻关部