D - F(x)

时间:2021-10-11 21:37:26

For a decimal number x with n digits (A nA n-1A n-2 ... A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.

For each test case, there are two numbers A and B (0 <= A,B < 10 9)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

3

0 100

1 10

5 100

Sample Output

Case #1: 1

Case #2: 2

Case #3: 13

计算满足fa的个数,数位dp,终于搞懂怎么做数位dp,自己写出来了

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip>
#include<cmath>
#include<float.h>
#include<string.h>
#include<algorithm>
#define sf scanf
#define pf printf
#define sca(x) scanf("%d",&x)
#define mm(x,b) memset((x),(b),sizeof(x))
#include<vector>
#include<queue>
#include<map>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
typedef long long ll;
const ll mod=1e9+7;
const double eps=1e-8;
using namespace std;
const double pi=acos(-1.0);
const int inf=0xfffffff;
const int N=1000005;
int p[25];
int tt[15][11];
int dp[11][4605];
void first()
{
p[1]=1;
rep(i,2,22)
p[i]=p[i-1]*2;
rep(i,1,11)
rep(j,0,10)
tt[i][j]=j*p[i];
mm(dp,-1);
}
int calc(int x)
{
int ans=0,pos=1;
while(x)
{
ans+=(x%10)*p[pos++];
x/=10;
}
return ans;
}
int num1[15],num2[15];
int dfs(int pos,int left,bool lead,bool limit)//left是剩下的,lead这里没有用,可舍去,limit是否上限
{
if(!pos) return 1;
int ans=0;
if(!limit&&dp[pos][left]!=-1) return dp[pos][left];
int up=limit?num2[pos]:9;
rep(i,0,up+1)
{
if(tt[pos][i]>left) break;
ans+=dfs(pos-1,left-tt[pos][i],lead&&i==num1[pos],limit&&(i==num2[pos]));
}
if(!limit) dp[pos][left]=ans;
return ans;
}
int solve(int l,int r)
{
int x=l;
mm(num1,0);
int pos1=0;
while(l)
{
num1[++pos1]=l%10;
l/=10;
}
int pos=0;
while(r)
{
num2[++pos]=r%10;
r/=10;
}
return dfs(pos,calc(x),true,true);
}
int main()
{
int re,l,r,cas=1;
first();
sf("%d",&re);
while(re--)
{
sf("%d%d",&l,&r);
pf("Case #%d: %d\n",cas++,solve(l,r));
}
return 0;
}