【Codeforces】1635D Infinite Set题解

题目大意

给定初始有$n$个正整数$a_i(1\le n\le 2?10^5,1\le a_i\le 10^9)$集合$S$。
而满足下列条件的数$y$,也会被添加进这个集合:

• $y=2?x+1且x=a_i$
• $y=4?x,且x=a_i$

问，这个集合最终不超过$2^p(1\le p\le 2?10^5)$的数的个数是多少。

题目链接

思路

我们先假设初始集合中只有$1$。那么$3,4$也会被添加进来，紧接着$12,16,7,9$也会被添加进来。多试几个数我们会发现，不同的操作产生的数不会产生重合。

直接设$d{p}_i$表示$i$以内的数有多少个,那么我们可以轻松得出状态转移方程，但是，显然是开不下的。

我们注意到题目要求不超过$2^p$,所以我们不妨用二进制来表示状态。

$f_i$表示有$i$位二进制位数，其以内的数有多少个。比如$f_4$就表示集合中小于等于$(1111{)}_2$ 且大于 $(1000{)}_2$的数个数有多少(这么做可以防止重复计算)。

题目中的两种操作在二进制下就是这种操作:

• $x=x<<1|1$
• $x=x<<2$

我们来写一下状态转移方程$f_i$:

• 通过$x=x<<1|1$操作,所有$f_{i?1}$中的数都可以转移过来
• 通过$x=x<<2$操作，所有$f_{i?2}$中的数都可以转移过来

故，$f_i=f_{i?1}+f_{i?2}$

只有一个的情况我们已经表示出来了，那么假如初始的时候有多个数呢？
假如一个数$x$可以被另一个数$y$产生出来，那么我们就不再需要$x$了。

那么具体怎么做呢？

• 我们先判断$x$是否包含在$set$中
• 如果二进制下$x$的末尾是$1$,那么它可能由$$x=x<<1|1$$操作产生,所以我们令$x>>=1$
• 如果二进制下$x$的末尾是$00$,那么它可能由$x=x<<2$操作产生,所以我们令$x>>=2$
• 如果$x$的后两位为$11$,那么就无法继续下去了，结束这种操作。
• 结束循环后，如果$x$无法被$set$中的数表示,那就把$x$加入$set$中。

代码

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;const int maxN = 2e5 + 7;
const long long Mod = 1e9 + 7;
int n, p, a[maxN], cnt[35];
long long f[maxN];inline int calc(int x)
{
    int cnt = 0;while(x) {
    cnt++;x >>= 1;}return cnt;
}int main()
{
    scanf("%d%d", &n, &p);for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);set<int> num;sort(a + 1, a + 1 + n);for(int i = 1; i <= n; ++i) {
    if(calc(a[i]) > p)continue;bool hav = false;int x = a[i];while(x) {
    if(num.count(x)) {
    hav = true;break;}if(x & 1)x >>= 1;else if(x & 3)break;elsex >>= 2;}if(!hav)num.insert(a[i]);}for(auto i : num) cnt[calc(i)]++;long long ans = 0;for(int i = 1; i <= 33; ++i)f[i] = cnt[i];f[2] += f[1];ans = (ans + f[2] + f[1]) % Mod;for(int i = 3; i <= p; ++i) {
    f[i] = (f[i] + f[i - 1] + f[i - 2]) % Mod;ans = (ans + f[i]) % Mod;}printf("%lld\n", ans);return 0;
}