文章目錄

• 題意
• 思路

傳送門

題意

給你一個集合$S$，初始集合內(nèi)含有$n$個數(shù)，讓后按照一下三個規(guī)則無限的向集合中添加數(shù)：

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

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

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

問集合中小于$2^p$的數(shù)有多少個，對$1e9+7$取模。

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

思路

$p$是$2e5$級別的，肯定是要找規(guī)律了，考慮兩中操作對于二進(jìn)制來說都發(fā)生了什么：

對于第二種操作，無非就是在二進(jìn)制序列的最后加上了一個$1$，長度增加$1$。

對于第三種操作，無非就是在二進(jìn)制序列的最后加上了兩個$0$，長度增加$2$。

而小于$2^p$也就是小于等于$p$個$1$，所以就可以轉(zhuǎn)換成將某個數(shù)$x$的二進(jìn)制長度加到$p$的方案數(shù)，也就是個數(shù)了，這個可以由$dp[i]=dp[i?1]+dp[i?2]$的經(jīng)典$dp$來得到，讓后做一個前綴和，算一下$dp[p?len(x)]$就是答案了。

但是這樣直接來會有重復(fù)的情況，但是我們發(fā)現(xiàn)如果找到根的話，讓后就可以根據(jù)根來去重，對于每個數(shù)，能構(gòu)成他的數(shù)最多有$logn$個，所以我們直接找到他的所有父親，拿$map$去重一下即可。

由于用到了$map$，所以復(fù)雜度$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; }

總結(jié)

以上是生活随笔為你收集整理的CF 1635 D. Infinite Set 思维 + 二进制的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。