<span>Codeforces 914 C 数位DP+暴力打表+思维</span>
题意
给出一个二进制数\(n\),每次操作可以将一个整数\(x\)简化为\(x\)的二进制表示中\(1\)的个数,如果一个数简化为\(1\)所需的最小次数为\(k\),将这个数叫做特殊的数,
问从\(1\)到\(n\)一共有多少个特殊的数,答案对\(1e9+7\)取模。
分析
\(n\)最大为\(2^{1000}\),二进制表示中最多有\(1000\)个\(1\),所以\(n\)以内的数经过一次简化后将变为\(1000\)以内的数,我们可以暴力打表\(1000\)以内的数简化为\(1\)所需的最少次数,将求得的次数加\(1\)即为二进制中\(1\)的个数为\(x\)的数简化为\(1\)所需的最少次数为\(cnt[x]\),\(1\)这个数要特判,没特判wa了3发。。。
然后分情况讨论:
-
\(k=0\),答案为\(1\),只有\(1\)是经过\(0\)次简化到\(1\)的数
-
\(k=1\),答案为\(n\)的位数\(-1\),\(n\)除了第\(1\)位,其余每一位为\(1\)都是特殊的数
-
\(k>1\),直接数位dp,设\(dp[i][j]\)为枚举到第\(i\)位二进制中\(1\)的个数为\(j\),\(cnt[x]==k\)的数为特殊的数
Code
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
char s[1010];
int a[1010],cnt[1010],k;
ll dp[1010][1010];
ll dfs(int pos,int x,int limit){
if(pos==0) return cnt[x]==k;
if(!limit&&~dp[pos][x]) return dp[pos][x];
int up=limit?a[pos]:1;
ll ret=0;
for(int i=0;i<=up;i++){
ret+=dfs(pos-1,x+(i==1),limit&&i==a[pos]);
ret%=mod;
}
if(!limit) dp[pos][x]=ret;
return ret;
}
int solve(int x){
if(x==1) return 0;
int ret=0;
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
ret+=solve(cnt)+1;
return ret;
}
void init(int n){
for(int i=1;i<=n;i++){
cnt[i]=solve(i)+1;
}
}
int main(){
ios::sync_with_stdio(false);
init(1005);
memset(dp,-1,sizeof(dp));
cin>>s+1>>k;
int n=strlen(s+1);
for(int i=1;i<=n;i++){
a[n-i+1]=s[i]-'0';
}
if(k==1){
cout<<n-1;
}else if(k==0) cout<<1;
else cout<<dfs(n,0,1);
return 0;
}