#P3588. fx

    ID: 2789 传统题 2000ms 256MiB 尝试: 100 已通过: 49 难度: 6 上传者: 标签>CF2100提高数位 DP上界限制状态非受限状态记忆化等价类划分可行性剪枝By佚名提供

fx

题目描述

对于一个 nn 位的十进制数 x(An,An−1,⋯ ,A1)x (A_n,A_{n-1},\cdots,A_1),我们定义它的权重为:$F(x)=A_n\times 2n-1+A_{n-1}\times 2n-2+\cdots+A_1\times 20$。

现在,给你两个十进制数 aa 和 bb,请计算出在闭区间 [0,b][0, b] 之中,有多少个数 xx 的权重不大于 aa 的权重,即 F(x)≤F(a)F(x)\le F(a)。由于答案可能很大,你只需要输出答案对 109+710^9+7 取模的结果即可。

输入格式

第一行一个正整数 TT,表示测例的个数。 随后 TT 行,每行描述一个测例,包含两个非负整数 aa、bb ,之间用空格隔开。含义见问题描述。

输出格式

对于每个测例,单独输出一行 Case #t: ans,其中 tt 表示测例编号,从 11 开始递增,ansans 表示该组测例的答案(对 109+710^9+7 取模后的结果)。

3
0 100
1 10
5 100
Case #1: 1
Case #2: 2
Case #3: 13

数据规模与约定

对于 20%20\% 的数据,a,b≤109a,b\le 10^9; 对于 30%30\% 的数据,a,b≤1018a,b\le 10^{18};

对于 100%100\% 的数据,a,b≤10200a,b\le 10^{200},T≤5T\le 5。

样例说明

对于 Case #3,符合条件的数有 0,1,2,3,4,5,10,11,12,13,20,21,1000, 1, 2, 3, 4, 5, 10, 11, 12, 13, 20, 21, 100,共 1313 个。

题目来源

By 佚名提供