CF1635D Infinite Set

题目链接

分析

• 计数题。

• 三种操作的本质：

  1. 将 a[1...n] 全放入 S 中
  2. 从 S 中取出一个元素, 左移 1 位然后加 1, 放回 S
  3. 从 S 中取出一个元素, 左移 2 位, 放回 S

  最终，S中所有的元素均是由 a[1..n]经过后2种操作扩展出来的。易知，操作2会使数字的二进制表示长度加1，操作3会使长度加2。由于S中的数字必须小于$2^p$，所以若一个数字的二进制表示长度为 blen，则可供其扩展的长度为 p - blen。另外，我们可以用DP计算$f(x)$，表示若可供扩展的长度为$x$，最多可以生成$f(x)$个不同的数字。

• DP的计算方法：

  void init(){
      dp[0]=1;
      dp[1]=1;
      dp[2]=2;
      for(int i=3;i<MAXN;i++){
          dp[i]=(dp[i-1]+dp[i-2])%MOD;
      }
      for(int i=1;i<MAXN;i++){
          dp[i]=(dp[i]+dp[i-1])%MOD;
      }
  }

• 去重。在 a[1...n] 中，有些数字本身就可以由其他数字通过操作2、3生成出来，这种数字就不能再拿去生成新的数字了，否则会造成重复。这里有一个显然的性质，即一个数字肯定是由比它小的数字生成出来的，所以我们可以先把数组 a[1...n] 排个序，用一个set保存已经用过的数字，从小到大考虑，将这个数字按照操作2、3的逆操作不断还原，然后去set中检查是否用过，如果用过就不再用它去生成新的数字。具体做法如下：

  set<LL> vis;
  bool check(LL num){
      while(num){
          if(vis.count(num)!=0)  return 1;
          if(num&1)
              num>>=1;
          else{
              if((num&3)==0){
                  num>>=2;
              }
              else
                  return 0;
          }
      }
      return 0;
  }

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5+5;
const LL MOD = 1e9+7;

LL dp[MAXN];
LL a[MAXN],ra[MAXN];

void init(){
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<MAXN;i++){
        dp[i]=(dp[i-1]+dp[i-2])%MOD;
    }
    for(int i=1;i<MAXN;i++){
        dp[i]=(dp[i]+dp[i-1])%MOD;
    }
}
int calen(LL num){
    int ret=0;
    while(num){
        num>>=1;
        ret++;
    }
    return ret;
}

set<LL> vis;
bool check(LL num){
    while(num){
        if(vis.count(num)!=0)  return 1;
        if(num&1)
            num>>=1;
        else{
            if((num&3)==0){
                num>>=2;
            }
            else
                return 0;
        }
    }
    return 0;
}

int main(){
    // freopen("in.txt", "r", stdin);
    init();

    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    sort(a,a+n);
    int m=0;
    for(int i=0;i<n;i++){
        if(!check(a[i])){
            ra[m]=a[i];
            m++;
            vis.insert(a[i]);
        }
    }

    LL ans=0;
    for(int i=0;i<m;i++){
        int tlen=calen(ra[i]);
        if(tlen>p)
            continue;
        ans=(ans+dp[p-tlen])%MOD;
    }
  
    printf("%lld\n",ans);

    return 0;
}