学步园

数位dp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn ((1<<9)*9)
int dp[15][15][maxn+10];
void init()
{
	memset(dp,0,sizeof(dp));
	for(int i=0;i<10;i++)
		for(int j=i;j<maxn;j++)
			dp[1][i][j]=1;
	for(int i=2;i<=9;i++)
		for(int j=0;j<10;j++)
			for(int k=0;k<maxn;k++)
				for(int l=0;l<10&&(k-j*(1<<(i-1)))>=0;l++)
					dp[i][j][k]+=dp[i-1][l][k-j*(1<<(i-1))];					
}
int cal(int x)
{
	int pow=1;
	int ans=0;
	while(x)
	{
		ans+=(x%10)*pow;
		x/=10;
		pow<<=1;
	}
	return ans;
}
int get(int sum,int x)
{
	int ans=0;
	int num[12];
	int k=0;
	if(cal(x)<=sum)
		ans++;	
	while(x)
	{
		num[++k]=x%10;
		x/=10;
	}	
	for(int i=k;i>=1;i--)
	{
		for(int j=0;j<num[i];j++)
			ans+=dp[i][j][sum];
		sum-=(num[i]*(1<<(i-1)));
		if(sum<0)
			break;
	}
	return ans;
}
void solve(int i)
{
	int a,b;
	scanf("%d%d",&a,&b);
	printf("Case #%d: ",i);
	printf("%d\n",get(cal(a),b));
}
int main()
{
	int t;
	cin>>t;
	init();
	for(int i=1;i<=t;i++)
		solve(i);
	return 0;
}