#2028. 圆滚滚的算术占卜

    ID: 2028 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest758来源:qoj.ac数据:公开样例模拟前缀和

圆滚滚的算术占卜

圆滚滚的算术占卜

题目描述

标题: 圆滚滚的算术占卜 - Problem - QOJ.ac

#4904. 圆滚滚的算术占卜

Statistics

The problem was used in the following contests:

在具有高度智慧的、拥有“史莱姆的导师”之称的红头史莱姆的引导下,史莱姆们理解了十进制数,并能够利用数字进行占卜。

史莱姆每天会进行占卜活动,第 k 天的流程如下:

  1. 将 n 的值设为 k 。
  2. 将 n 的不含前导0的十进制表示写下来。如果现在已经写下来了一些数,就将 n 写在它们的后面。
  3. 令 n:=n−S(n) ,其中 S(n) 表示 n 的十进制表示的各位数字之和,例如 S(233)=2+3+3=8 ,S(114514)=1+1+4+5+1+4=16 。
  4. 如果 n=0,结束占卜,否则回到第2步。

最终的占卜结果是一个十进制数字串。显然,它也表示了一个十进制数。史莱姆想让你帮它们求出,第 L 天到第 R 天的占卜结果之和是多少。由于答案可能很大,你只需要求出对 998244353 取模后的结果。史莱姆们总共问了 T 个这样的问题,你需要对每个问题求出答案。

输入格式

第一行包含一个正整数 T ,表示史莱姆的问题个数。

接下来 T 行,每行两个正整数 L 和 R ,表示你需要求出第 L 天到第 R 天的占卜结果之和。

输出格式

对于每组询问,输出答案对 998244353 取模后的结果。

样例

input

7
1 9
10 11
32 32
16058 258258
1 998244353
31415926 271828182
757427636498525616 1000000000000000000

output

45
228
3227189
64050837
32261615
188342047
329553393

explanation

对于 1≤k≤9,第 k 天的占卜一次就会结束,因此占卜结果就是 k ,第一组询问的答案为 1+2+3+⋯+9=45 。

第 10 天的占卜中会依次写下 10 和 10−S(10)=9 ,第 11 天会依次写下 11 和 9 ,从而第二组询问的答案为 109+119=228 。

第 32 天会依次写下 32 ,32−S(32)=27 ,27−S(27)=18 和 18−S(18)=9 ,因此第三组询问的答案是 3227189 。

限制与约定

Subtask 1(5pts): T≤500,R≤105 。

Subtask 2(10pts): T≤5,L=R≤109 。

Subtask 3(20pts): T≤500,L=R≤1012 。

Subtask 4(30pts): L=R 。

Subtask 5(10pts): T≤500,R≤1012 。

Subtask 6(25pts): 无特殊限制。

对于所有测试数据,满足 1≤T≤5×104,1≤L≤R≤1018 。

**时间限制:**4s

**空间限制:**2GB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

7
1 9
10 11
32 32
16058 258258
1 998244353
31415926 271828182
757427636498525616 1000000000000000000
45
228
3227189
64050837
32261615
188342047
329553393