题意
定义 \(\operatorname{popcount}(x)\) 为 \(x\) 二进制下 \(1\) 的个数。
定义对 \(x\) 的一次操作:\(x\gets\operatorname{popcount}(x)\),显然任意正整数经过若干次操作后会变为 \(1\)。
给定 \(n\) 和 \(k\),其中 \(n\) 是在二进制下被给出,求出所有不大于 \(n\) 且将其变为 \(1\) 的最小操作次数为 \(k\) 的数的个数对 \(10^9+7\) 取模的结果。
分析
因为 \(n<2^{1000}\),所以数 \(x(x<n)\) 经过 \(1\) 次操作后得到的 \(x'\leq1000\)。
所以我们可以预处理 \([2,1000]\) 中的数变成 \(1\) 的最少操作次数。
考虑在二进制下使用数位 dp 解决。
定义 \(dp_{n,i,v}\) 为目前搜索至第 \(n\) 位,该位之前有 \(i\) 个 \(1\),上一位填的是 \(v\) 的满足题意的数的个数。
记忆化搜索即可,时间复杂度 \(O(\log^2n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 1003
#define popc __builtin_popcount
#define mod 1000000007
int ks[maxn];
void init()
{
for(int i=2;i<=1000;i++)
ks[i]=ks[popc(i)]+1;
}
string s;
bitset<maxn> bs;
int dp[maxn][maxn][2], k;
int dfs(int n, int cnt=0, bool la=0, bool lim=1)
{
if(!lim&&~dp[n][cnt][la]) return dp[n][cnt][la];
if(!n) return cnt==1&&la?0:cnt&&ks[cnt]==k-1;
int ret=0, up=lim?bs[n]:1;
for(int i=0;i<=up;i++)
ret=(ret+dfs(n-1, cnt+i, i, lim&&i==up))%mod;
if(!lim) dp[n][cnt][la]=ret;
return ret;
}
int main()
{
init();
memset(dp, -1, sizeof dp);
cin>>s>>k;
if(k==0) return cout<<1, 0;
for(int i=0;i<s.size();i++)
bs[s.size()-i]=s[i]^48;
cout<<dfs(s.size());
}
标签:cnt,return,la,int,题解,maxn,Numbers,Salesman,dp
From: https://www.cnblogs.com/redacted-area/p/18389465