3641: 偶数(第四轮04)
题目描述
牛牛喜欢偶数，他定义一种新的“偶数”为： (在十进制下，去掉前导零)数字的位 数为偶数，且数字前一半和后一半完全一致。比如 121121 、12341234 是“偶 数”，而 111 、121212 不是“偶数”。
对于一个“偶数”，牛牛可以在这个“偶数”后继续添加数字，使得它成为新的“偶 数”。比如， 121121 可以在后面添加数字，使之变成 1211212112 成为新的 “偶数”。牛牛总是想添加最少的数字获得新的“偶数”。可以证明添加的方式是唯 一的。
对于任何一个“偶数”， 牛牛都可以通过上述的方式产生新的“偶数”， 这个新的 “偶数”继续产生下一个新的“偶数”，直到这个“偶数”的位数超过任意给定的正整 数 n 为止。之后，牛牛会多次询问你，这个最终的“偶数”的第 l 位到第 r 位
(1 ≤ l ≤ r ≤ n)组成的整数 模 998244353 后是多少。
输入
第一行 T，表示测试样例数。
对于每个测试样例， 一行一个“偶数”u 。(“偶数”的定义见题目描述)
接下来一行，两个正整数 n, q，其中n表示牛牛产生的最终的“偶数”的位数至少为 n ， q 代表询问个数。
接下来q行，每行两个正整数l，r，代表一个询问。
输出
对于每个询问输出答案，模 998244353。
样例输入 复制
2
121121
15 2
4 10
1 15
1111
10 2
1 5
1 10样例输出 复制
1212112
230884310
11111
112866758提示
样例 1 说明】
第 1 组 ：“ 偶 数 ”产 生 直 到 超 过 15 位 ： 121121 −> 1211212112 −>1211212112112121。
询问 1 、4 到 10 位是 1212112。
询问 2 、1 到 15 位是 121121211211212，取模后为 230884310。
【数据范围】
对于 10%的数据，满足 1 ≤ u ≤ 101000， 1≤n,q≤1000
对于 40%的数据，满足 1 ≤ n ≤ 10^5
对于 100%的数据，满足 T = 10, 1 ≤ u ≤ 10^10^5 , 1 ≤ n ≤ 10^18 , 1 ≤ ∑q ≤ 10^5, 1 ≤ l ≤ r ≤ n。
保证 u 每一位只有 1-9。