#P6823. [2019年广州]函数

    ID: 6655 传统题 2000ms 512MiB 尝试: 9 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-数位 DP自动机 DP状态编码自动机最小化朴素划分细化非受限状态记忆化前缀和优化 DP小块状态查表

[2019年广州]函数

题目描述

对于正整数 nn,设其十进制各位依次为 d1,…,dkd_1,\ldots,d_k。分别在每一位前加上正号或负号,使所得和的绝对值最小。记这个最小值为

$$f(n)=\min_{s_1,\ldots,s_k\in\{-1,1\}}\left|\sum_{j=1}^{k}s_jd_j\right|.$$

f(n)f(n) 的取值在 [0,9][0,9] 内。每次给定闭区间 [L,R][L,R],对每个 v=0,1,…,9v=0,1,\ldots,9,分别求满足 f(n)=vf(n)=v 的整数 nn 的和,答案对 109+710^9+7 取模。

原 PDF 正文中的“个数”与其样例及实际评测不符。以第一组样例为例,f(1)=f(10)=1f(1)=f(10)=1,对应这一类的答案为 1+10=111+10=11。

输入格式

第一行是询问数 qq。接下来 qq 行,每行两个十进制正整数 L,RL,R。

输出格式

每个询问输出一行十个整数。第 ii 个整数是 [L,R][L,R] 内满足 f(n)=i−1f(n)=i-1 的各整数之和模 109+710^9+7 的结果。

数据范围

1≤q≤1041\le q\le10^4,1≤L≤R<101001\le L\le R<10^{100}。

子任务 分值 附加限制
1 20 R<106R<10^6
2 25 R<109R<10^9
3 15 R<1018R<10^{18}
4 R<1050R<10^{50}
5 25 无

样例

7
1 10
11 50
51 100
101 500
501 1000
19260817 19260818
1234567890123456789 1234567890987654321
0 11 2 3 4 5 6 7 8 9
110 210 211 193 166 180 84 47 19 0
385 770 579 497 424 310 306 243 171 90
19080 34666 27312 19047 10615 5490 2594 1097 299 0
43695 81005 67134 55962 46289 35085 23872 13924 6385 1899
19260817 19260818 0 0 0 0 0 0 0 0
230833519 749351908 0 0 0 0 0 0 0 0

原 PDF 题面