F(x)(数位DP)

F(x)

http://acm.hdu.edu.cn/showproblem.php?pid=4734

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9614 Accepted Submission(s): 3802

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

0 100

1 10

5 100

Sample Output

Case #1: 1

Case #2: 2

Case #3: 13

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<char,int> pci;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 
23 int dp[25][10005];
24 int a[25];
25 int num;
26 
27 int fun(int x){
28     if(!x) return 0;
29     int ans=fun(x/10);
30     return ans*2+(x%10);
31 }
32 
33 int dfs(int pos,int sum,int limit){
34     if(pos==-1) return sum<=num;
35     if(sum>num) return 0;
36     if(!limit&&dp[pos][num-sum]!=-1) return dp[pos][num-sum];
37     int up = limit ? a[pos] : 9;
38     int ans=0;
39     for(int i=0;i<=up;i++){
40         ans+=dfs(pos-1,sum+i*(1<<pos),limit&&i==a[pos]);
41     }
42     if(!limit) dp[pos][num-sum]=ans;
43     return ans;
44 }
45 int solve(int x){
46     int pos=0;
47     while(x){
48         a[pos++]=x%10;
49         x/=10;
50     }
51     return dfs(pos-1,0,true);
52 }
53 
54 int main(){
55     #ifndef ONLINE_JUDGE
56      //   freopen("1.txt","r",stdin);
57     #endif
58     std::ios::sync_with_stdio(false);
59     int n,m;
60     int t;
61     cin>>t;
62     memset(dp,-1,sizeof(dp));
63     for(int i=1;i<=t;i++){
64         cin>>n>>m;
65         num=fun(n);
66         int ans=solve(m);
67         cout<<"Case #"<<i<<": "<<ans<<endl;
68     }
69 }

View Code