题解：P9500 「RiOI-2」tnelat

oaheh7990 · 2026-04-25 15:13:33 · 题解

题目大意

给出 0\le a,b<998244353，构造首尾均不为 0、长度不大于 114514 的十进制数 s，使得 s\equiv a\pmod{998244353}，\overline s\equiv b\pmod{998244353}，其中 \overline s 表示将 s 反转得到的数。如果这样的 s 不存在，输出 -1。每个测试点有 T 组测试数据，T\le30。

题目分析

约定 \mathrm{inv}(x) 表示将 x 反转得到的数，\overline{\mathsf{XXX}} 表示十进制数的结构。

这样的 s 可以写作 998244353k+a，其中 k 是非负整数。如果忽略 \overline s\equiv b\pmod{998244353} 的条件，这样的 s 大约有 9\times{10}^{114504} 个。令 f(k)=\overline s\bmod998244353，因为反转 s 的过程和 \mathrm{mod}~998244353 无关，可以感性认为 f(k) 是随机的。基于以上想法，我们猜测这样的 s 存在，且平均枚举 998244353 个就能找到一个。

简单枚举是无用的，因为程序平均需要枚举 998244353T\approx3\times{10}^9 个数，显然超时。我们需要可以一次枚举大量 s 的方式。为了用到 s 的长度不大于 114514 这个条件，可以这样设计 s 的结构：

s=\overline{(998244353k)\,0^g\,a}

其中 0^g 表示 0 重复 g 次，则 \overline s 的结构如下：

\overline s=\overline{\mathrm{inv}(a)\,0^g\,\mathrm{inv}(998244353k)}

为了方便程序计算，将十进制结构转换为表达式：

\overline s=\mathrm{inv}(a)\times{10}^d\times{10}^g+\mathrm{inv}(998244353k)

其中 d 是 998244353k 的十进制位数。由 \overline s\equiv b\pmod{998244353}，我们可以借助逆元计算 {10}^g 的值。如果最小的 g 可以让 s 的长度不大于 114514，那么结束枚举，否则递增 k 继续枚举。关于求 g 的方法，容易想到 BSGS，但是 BSGS 需要一个 \sqrt{998244353}\approx3\times{10}^4 次的循环，并且平均查询次数为 \frac{998244353T}{114514}\approx3\times{10}^5，时间复杂度不能接受。继续想到用哈希表预处理 {10}^g \rightarrow g 的映射，可以实现 \mathcal{O}(1) 的查询，时间复杂度可以接受。

实现中注意一些细节：

如果 a \equiv 0 \pmod{10}，令 a \leftarrow a + 998244353；
如果 \mathrm{inv}(a) \equiv 0 \pmod{998244353}，令 a \leftarrow a + 998244353；

如果 k \equiv 0 \pmod{10}，那么 998244353k 末尾为 0，这次枚举提供的信息极少，可以跳过。

AC 代码

目前是最优解。

#include<bits/stdc++.h>
using namespace std;
const int N=114490,M=998244353;
struct E{//哈希表
int x,i;
};
vector<E> mp[N];
int query(int x){
for(E v:mp[x/(M/N)]){
    if(x==v.x)return v.i;
}
return -1;
}
long long T,a,b;
long long inv(long long x){
long long res=0;
for(;x;x/=10)res=res*10+x%10;
return res;
}
int qpow(int a,int b){
int res=1;
for(;b;a=1ll*a*a%M,b>>=1){
    if(b&1)res=1ll*res*a%M;
}
return res;
}
void solve(){
cin>>a>>b;
while(a%10==0||inv(a)%M==0)a+=M;
for(long long ia=inv(a),c=M;;c+=M){
    if(c%10==0)continue;//剪枝
    long long d=ia,e=c,f=0;
    for(;e;e/=10)d=d*10%M,f=f*10+e%10;
    int g=(b-f)%M*qpow(d,M-2)%M,h=query(g<0?g+M:g);
    if(h>=0){
        cout<<c<<string(h,'0')<<a<<'\n';
        break;
    }
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
for(int i=0,x=1;i<N;x=x*10ll%M)mp[x/(M/N)].push_back({x,i++});//预处理
for(cin>>T>>a;T--;)solve();
}