HDU - 4734 -- F(x)

题目如下：

For a decimal number x with n digits ( A n A n − 1 A n − 2 . . . A 2 A 1 ) (A_nA_{n-1}A_{n-2} ... A_2A_1) (An​An−1​An−2​...A2​A1​), we define its weight as F ( x ) = A n ∗ 2 n − 1 + A n − 1 ∗ 2 n − 2 + . . . + A 2 ∗ 2 + A 1 ∗ 1. F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2} + ... + A_2 * 2 + A_1 * 1. F(x)=An​∗2n−1+An−1​∗2n−2+...+A2​∗2+A1​∗1. Now you are given two numbers A A A and B B B, please calculate how many numbers are there between 0 0 0 and B B B, inclusive, whose weight is no more than F ( A ) F(A) F(A).
Input
The first line has a number T ( T ≤ 10000 ) T (T \le 10000) T(T≤10000) , indicating the number of test cases.
For each test case, there are two numbers A A A and B B B ( 0 ≤ A , B < 1 0 9 ) (0 \le A,B < 10^9) (0≤A,B<109)
Output
For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1 1 1. Then output the answer.

Sample

Input

3
0 100
1 10
5 100

Output

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

思路 or 题解：

数位DP
dfs(数位， F(x) - 该位数的贡献，是否有限制)
具体请参考下面代码

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int f[30][N], dig[30], idx;
int calc(int x)
{
	int ans = 0, t = 1;
	while (x)
		ans += x % 10 * t, t <<= 1, x /= 10;
	return ans;
}
int dfs(int pos, int s, bool lim)
{
	if (pos == -1)	return s >= 0;
	if (s < 0)
		return 0;
	if (!lim && f[pos][s] != -1)	return f[pos][s];

	int len = lim ? dig[pos] : 9;
	int ans = 0;
	for (int i = 0; i <= len; i++)
		ans += dfs(pos - 1, s - i * (1 << pos), lim && i == len);

	if (!lim)	f[pos][s] = ans;
	return ans;
}
void solve()
{
	int x, n;	cin >> x >> n;
	idx = 0;
	while (n)
		dig[idx++] = n % 10, n /= 10;
	cout << dfs(idx - 1, calc(x), 1) << '\n';
}
int main()
{
	buff;
	memset(f, -1, sizeof f);
	int _ = 1;
	cin >> _;
	for (int i = 1; i <= _; i++)
	{
		cout << "Case #" << i << ": ";
	    solve();
	}
}