F(x)

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

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

Sample Output

Case #1: 1
Case #2: 2
Case #3: 13

Source 2013 ACM/ICPC Asia Regional Chengdu Online

题意：看懂f(x)函数之后，求[0,B]内的f(x)的值小于f(a)的有多少个。
思路：数位dp，由于f(x)的值不大，可以考虑把f(x)放入状态中。 dp[i][j][k] - i 位 j 开头f(x)值为k的数的个数。那么有dp[i][j][k]=dp[i-1][p][k-j*2^(i-1)] 。然后算一个区间内的个数时，一位一位往下算就够了。考虑到时间的原因，采用了一个sum数组纪录前缀和。
代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 10005 #define MAXN 100005 #define mod 100000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans,cnt,tot,flag; int a,b,fac[10]; int dp[10][10][5500],sum[10][10][5500]; void solve() { int i,j,t=0,u,v; for(i=9;i>=1;i--) { t+=((a/fac[i-1])%10)*(1<
             
              =1;i--) { u=(b/fac[i-1])%10; for(j=0;j
              
               =0) t+=dp[i-1][p][k-(1<
               
                0) sum[i][j][k]=sum[i][j][k-1]+t; else sum[i][j][k]=t; } } } scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); solve(); printf("Case #%d: %d\n",++test,ans); } return 0; } /* 3 0 100 1 10 5 100 Case #1: 1 Case #2: 2 Case #3: 13 */

hdu 4734 F(x) （数位dp）

F(x)