F(x)

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 382 Accepted Submission(s): 137

Problem Description

For a decimal number x with n digits (A

_nA

_n-1A

_n-2 ... A

₂A

₁), we define its weight as F(x) = A

_n * 2

^n-1 + A

_n-1 * 2

^n-2 + ... + A

₂ * 2 + A

₁ * 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

⁹)

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

题意

定义F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1。给A，B，求0到B的F(x)的小于等于F(A)的个数。

分析

数位DP。dp[i][j]为位数i的值小于等于j的个数。利用记忆化搜索

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  using namespace std;typedef pair
                  
                    pii;#define X first#define Y second#define pb push_back#define mp make_pairtypedef long long ll;#define ms(a,b) memset(a,b,sizeof(a))const int inf = 0x3f3f3f3f;const int maxn = 2e5;const int mod = 1e9+7;#define lson l,m,2*rt#define rson m+1,r,2*rt+1int dp[15][maxn];int bit[15];int F(int A){ int len=0; int res=0; while(A){ res += (A%10)*(1<
                   
                    =0; if(num<0) return 0; if(!limit && dp[pos][num]!=-1) return dp[pos][num]; int ed=limit?bit[pos]:9; int ans=0; for(int i=0;i<=ed;i++){ ans+=dfs(pos-1,num-i*(1<