文章目录

• 题意
• 思路

传送门

题意

给你一个集合$S$，初始集合内含有$n$个数，让后按照一下三个规则无限的向集合中添加数：

对于所有的$1\le i\le n,x=a_i$都在集合中。

对于所有的$x=2y+1,y\in S$，都可以将$x$加入集合。

对于所有的$x=4y,y\in S$都可以将x加入集合。

问集合中小于$2^p$的数有多少个，对$1e9+7$取模。

$1\le n,p\le 2e5,1\le a_i\le 1e9$

思路

$p$是$2e5$级别的，肯定是要找规律了，考虑两中操作对于二进制来说都发生了什么：

对于第二种操作，无非就是在二进制序列的最后加上了一个$1$，长度增加$1$。

对于第三种操作，无非就是在二进制序列的最后加上了两个$0$，长度增加$2$。

而小于$2^p$也就是小于等于$p$个$1$，所以就可以转换成将某个数$x$的二进制长度加到$p$的方案数，也就是个数了，这个可以由$dp[i]=dp[i-1]+dp[i-2]$的经典$dp$来得到，让后做一个前缀和，算一下$dp[p-len(x)]$就是答案了。

但是这样直接来会有重复的情况，但是我们发现如果找到根的话，让后就可以根据根来去重，对于每个数，能构成他的数最多有$logn$个，所以我们直接找到他的所有父亲，拿$map$去重一下即可。

由于用到了$map$，所以复杂度$O(nlo{g}^{2}n)$。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;int n,p; int f[N],a[N];void solve() {f[1]=1; f[2]=2;for(int i=3;i<N;i++) f[i]=(f[i-1]+f[i-2])%mod;for(int i=2;i<N;i++) (f[i]+=f[i-1])%=mod;map<int,int>mp;scanf("%d%d",&n,&p);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}sort(a+1,a+1+n);LL ans=0;for(int i=1;i<=n;i++) {int val=a[i];bool flag=true;while(val) {if(mp.count(val)) flag=false;if(val&1) val>>=1;else if(val&3) break;else val>>=2;}if(!flag) continue;ans++;int cnt=(int)log2(a[i])+1;ans+=f[max(0,p-cnt)];if(p<cnt) ans--;ans+=mod;ans%=mod;mp[a[i]]=1;}printf("%lld\n",ans); }int main() {int _=1;while(_--) {solve();}return 0; }

总结

以上是生活随笔为你收集整理的CF 1635 D. Infinite Set 思维 + 二进制的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。