#P6106. 「2021 集训队互测」圆滚滚的算术占卜

    ID: 5396 传统题 3000ms 2048MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS数位 DP模意义不变量状态维度消除预计算转移

「2021 集训队互测」圆滚滚的算术占卜

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

数据范围与提示

Subtask 1(5pts): T≤500,R≤105T\le 500,R\le 10^5 。

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

Subtask 3(20pts): T≤500,L=R≤1012T\le 500,L=R\le 10^{12} 。

Subtask 4(30pts): L=RL=R 。

Subtask 5(10pts): T≤500,R≤1012T\le 500,R\le 10^{12} 。

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

对于所有测试数据,满足 1≤T≤5×104,1≤L≤R≤10181\le T\le 5\times 10^4,1\le L\le R\le 10^{18} 。