luogu#P9500. 「RiOI-2」tnelat

    ID: 13471 远端评测题 1500ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷月赛

「RiOI-2」tnelat

题目背景

小 E 是一名一年级的小学生。她正在学习如何阅读。

如果在纸上写上 998, ⁣244, ⁣353998,\!244,\!353,那么她就会读「三——五三四四——二八九九。」是的,她是从右往左读的。然后,她会把这个数理解为 353, ⁣442, ⁣899353,\!442,\!899

不过这并不影响她交流——她只是不会读纸上的文字罢了。唯一的问题是,她现在要学习带余除法了,而老师说不定会在纸上画一些红色的叉叉。不过,那又如何?

题目描述

对于一个长度为 nn由数字组成的字符串 s=s1s2s3sns=s_1s_2s_3\cdots s_n,定义它的权值为 f(s)=i=1n10nisif(s)=\sum\limits_{i=1}^n 10^{n-i}s_i。(也就是它代表的十进制数)定义它的反串为 s=snsn1sn2s1\overline s=s_ns_{n-1}s_{n-2}\cdots s_1。例如,s=0321s=\texttt{0321} 的权值为 f(s)=321f(s)=321,反串为 s=1230\overline s=\texttt{1230}

试构造一个字符串 ss,使得 s114514|s|\le 114514,且 f(s)a(mod998, ⁣244, ⁣353)f(s)\equiv a\pmod {998,\!244,\!353}f(s)b(mod998, ⁣244, ⁣353)f(\overline s)\equiv b\pmod{998,\!244,\!353}。如果 c=0c=0,你还要保证 s10s_1\neq \texttt0sn0s_n\neq \texttt 0。 如果无解,仅输出整数 1-1 即可。

输入格式

本题有多组数据。

第一行一个正整数 TT 表示数据组数。

第二行一个整数 cc,意义如题目所述。

接下来 TT 行,每行两个以空格隔开的自然数 a,ba, b 描述一组数据。

输出格式

输出 TT 行,每行一个正整数表示你构造的数。

本题开启 Special Judge,只要你的输出符合要求即可得到该测试点的分数。

4
0
1755648 1755648
0 353442899
35281 18253
99728538 70320626
1000000001
998244353
35281
66330831785160880538172878128228067748679057340064161580956433229228884846388176250309226257600174873157935217529307119972759542770571505108922703815887608877795159689067116959276902444827654683066165
1
1
30 30
030
5
0
114514191 214748364
414414414 515515515
302813344 124821394
123456789 987654321
307210721 127012703
4509169566936302030543528193
6765800751328156020889260421
6754420765703935546785979321
4408846009459835952892074437
3108033793065515131695113495

提示

样例解释

对于第一组样例的第一组数据,s=s=1000000001s=\overline{s}=\texttt{1000000001},$f(s)=f(\overline s)=1{,}000{,}000{,}001\equiv 1{,}755{,}648\pmod{998,\!244,\!353}$,所以它是一个可行解。

数据规模与约定

本题开启捆绑测试。

Subtask\text{Subtask} 分值 a,ba,b 特殊性质
00 55 [1,9] \in [1, 9] a=ba = b
11 1010 [0,9] \in [0, 9] /
22 1515 [0,99] \in [0, 99]
33 2525 / a=0a = 0
44 c=1c = 1
55 2020 /

上表中的斜杠表示无特殊限制。

对于 100%100\% 的数据,1T301\leq T\leq 30c{0,1}c\in\{0,1\}0a,b<998,244,3530 \leq a, b \lt 998{,}244{,}353