【hdu4734】F(x) 数位dp

题目描述

对于一个非负整数 $x=​​\overline{a_na_{n-1}...a_2a_1}$ ，设 $F(x)=a_n·2^{n-1}+a_{n-1}·2^{n-2}+...+a_2·2^1+a_1·2^0=\sum\limits_{i=1}^na_i·2^{i-1}$ 

多次询问 $[0,B]$ 区间内 $F$ 值小于等于 $F(A)$ 的数的个数。

输入

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⁹)

输出

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.

样例输入

3
0 100
1 10
5 100

样例输出

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

---

题解

数位dp

考虑到最大的 $F(x)=F(999999999)=9207$ ，因此可以设 $f[i][j][k]$ 表示 $i$ 位数，最高位为 $j$ ，$F$函数的值为 $k$ 的数的个数。

首先预处理出 $f$ 数组，考虑当前位的贡献来计算。

然后先计算出$F(a)$，然后要求的就是$[0,b+1)$内 $F$值小于等于 $F(a)$ 的数的个数。

按照常规的数位dp思路，先考虑不足总位数的，然后再从高位向低位枚举，考虑以前位的贡献，得出当前的范围，直接计算即可。

由于有多组询问，需要使用前缀和优化转移过程。

这里为了不开long long把询问区间转化为 $[0,b)$ （实际上是 $[1,b)$），因此需要计算 $b$ 对答案的贡献。

#include <cstdio>
int f[10][10][10010] , b[10];
void init()
{
	int i , j , k , l;
	f[0][0][0] = b[0] = 1;
	for(i = 1 ; i < 10 ; i ++ )
	{
		b[i] = b[i - 1] * 10;
		for(j = 0 ; j < 10 ; j ++ )
			for(k = 0 ; k < 10 ; k ++ )
				for(l = j << (i - 1) ; l <= 10000 ; l ++ )
					f[i][j][l] += f[i - 1][k][l - (j << (i - 1))];
	}
	for(i = 1 ; i < 10 ; i ++ )
		for(j = 0 ; j < 10 ; j ++ )
			for(k = 1 ; k <= 10000 ; k ++ )
				f[i][j][k] += f[i][j][k - 1];
}
int calc(int n)
{
	int t = 1 , ans = 0;
	while(n) ans += n % 10 * t , n /= 10 , t <<= 1;
	return ans;
}
int query(int n , int m)
{
	int i , j , p , di = 1 , ans = 1 + (calc(n) <= m);
	for(i = 1 ; b[i] <= n ; i ++ )
		for(j = 1 ; j < 10 ; j ++ )
			ans += f[i][j][m];
	for( ; i ; i -- )
	{
		p = n / b[i - 1] % 10;
		for(j = di ; j < p ; j ++ ) ans += f[i][j][m];
		m -= p << (i - 1) , di = 0;
		if(m < 0) break;
	}
	return ans;
}
int main()
{
	init();
	int T , i , a , b;
	scanf("%d" , &T);
	for(i = 1 ; i <= T ; i ++ ) scanf("%d%d" , &a , &b) , printf("Case #%d: %d\n" , i , query(b , calc(a)));
	return 0;
}