题解：P9500 「RiOI-2」tnelat
qqqaaazzz_qwq
·
·
题解
来一个长度正好 36 的做法。
令 p=998244353。
构造集合 S，要求所有数字形如：
xxxxxxxxx000000000yyyyyyyyy000000000
并且这个数模 p 等于 a。
随机构造 10^5 个数即可。
构造集合 T，所有数字形如：
000000000xxxxxxxxx000000000yyyyyyyyy
并且这个数模 p 等于 0。
随机构造 10^5 个数即可。
然后，聪明的你发现，随便从 S 里选一个数，再从 T 里面选一个数，加起来就满足 a 这个条件了。
而 x+y 位数相同（允许有前导零），且不产生进位时，f(\overline {x+y})=f(\overline x + \overline y)。
所以像 BSGS 的思想，枚举 S 里面的一个数，看看 T 里面有没有对应的数就行了。
因为是随机生成的，所以根据生日悖论可知正确率很高。
代码里为了平衡复杂度，$S$ 只有 $40000$ 个数，$T$ 有 $400000$ 个数。
代码：
```cpp
#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
/*
by qqqaaazzz
*/
int a,b;
const int p = 998244353;
int fpm(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%p;
a=(a*a)%p;
b>>=1;
}
return res;
}
mt19937 rd(1);
int f(string s){
int res=0;
for(auto i:s)res=(res*10+i-'0')%p;
return res;
}
string rev(string s){
reverse(s.begin(),s.end());
return s;
}
int get(){
int res=0;
for(int i=1;i<=9;i++)res=(res*10+rd()%9+1);
if(res>=p)return get();
return res;
}
string TT(int x){
string res;
for(int i=8;i>=0;i--)res+=((x/(int)pow(10,i))%10+'0');
return res;
}
map<int,int> mp;
void get_by_2(int x,int y){
//cout<<x<<" " <<y<<"\n";
int H=(a-x%p*fpm(10,27)%p+p)%p*fpm(1000000000,p-2)%p;
string G=TT(x)+"000000000"+TT(H)+"000000000";
int H2=(0-y%p+p)%p*fpm(1000000000000000000%p,p-2)%p;
string G2="000000000"+TT(H2)+"000000000"+TT(y);
string final=TT(x)+TT(H2)+TT(H)+TT(y);
cout<<final<<"\n";
}
signed main()
{
int t,c;
cin>>t>>c;
FAST;
for(int i=1;i<=400000;i++){//平衡了一下复杂度
int K=get();
int H=(0-K+p)%p*fpm(1000000000000000000%p,p-2)%p;
string G="000000000"+TT(H)+"000000000"+TT(K);
mp[f(rev(G))]=K;
}
while(t--){
cin>>a>>b;
for(int i=1;i<=40000;i++){
int K=get();
int H=(a-K*fpm(10,27)%p+p)%p*fpm(1000000000,p-2)%p;
string G=TT(K)+"000000000"+TT(H)+"000000000";
int want=(b-f(rev(G))+p)%p;
if(mp.find(want)!=mp.end()){
get_by_2(K,mp[want]);
break;
}
}
}
return 0;
}
```