P8764 [蓝桥杯 2021 国 BC] 二进制问题

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=250,mod=998244353;
LL f[106][106];//长度为i时，前pos-1项的和为j的合法数
int s[106],cnt,k;

//pos位置，sum==mark，limit限制，isnum是否存在数字
LL dfs(int pos,LL sum,bool limit,bool isnum){
  int up=limit?s[pos]-0:1;//如果有限制那么最多只能枚举到该位置，否则会超出n的范围
  if(pos==0){//到达终点
    return sum==k;
  }
  if(isnum&&!limit&&f[pos][sum]!=-1) return f[pos][sum];//记忆化
  LL res=0;
  //只有前面都为前导0才可以
  if(!isnum) res=dfs(pos-1,0,false,false);//跳过，注意边界
  for(int i=1-isnum;i<=up;i++){//范围，以及起始边界
     res+=dfs(pos-1,sum+i,i==up&&limit,true);//每一个位置的合法数都要枚举
  }
  if(isnum&&!limit) f[pos][sum]=res;//如果存在数，且在合法范围内，记忆化
  return res;

}


LL work(LL n){
  memset(f,-1,sizeof f);
  cnt=0;
  while(n){
    s[++cnt]=n%2;
    n/=2;
  }
  //不知道为什么反转数组会出错
  LL ans=dfs(cnt,0,true,false);
  return  ans;
}

int main()
{
  LL n;
  cin>>n>>k;
  cout<<work(n);

  return 0;
}