AcWing 4641. F(x)
原题链接
简单
作者:
天后
,
2023-01-10 09:24:33
,
所有人可见
,
阅读 170
维护一下A的权值,然后dp的时候一位一位减掉B的权值,看最后是否大于等于零
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int l,r,val;
int f[N][N*N*N],num[N],two[N];
int dp(int pos,int val,int lim)
{
if(val<0) return 0;
if(!pos) return 1;
int ans=f[pos][val];
if(!lim&&ans!=-1) return ans;
ans=0;
int up=lim?num[pos]:9;
for(int i=0;i<=up;i++) ans+=dp(pos-1,val-i*two[pos-1],lim&&up==i);
if(!lim) f[pos][val]=ans;
return ans;
}
int calc(int x)
{
int len=0;
while(x) num[++len]=x%10,x/=10;
return dp(len,val,1);
}
void solve()
{
val=0;
cin>>l>>r;
for(int i=1;l;i++)
val+=(l%10)*two[i-1],l/=10;
cout<<calc(r)<<endl;
}
int main()
{
memset(f,-1,sizeof f);
two[0]=1;
for(int i=1;i<20;i++) two[i]=two[i-1]*2;
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
printf("Case #%d: ",i);
solve();
}
return 0;
}