自动搬运

查看原文

来自洛谷，原作者为

	MatrixGroup 删繁就简

搬运于2025-08-24 22:48:57，当前版本为作者最后更新于2023-02-28 13:50:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

非常 Educational 的一道题。

题意

构造一个数字串，正写 $\equiv a\pmod {998,\!244,\!353}$，反写 $\equiv b\pmod {998,\!244,\!353}$。

做法 1（Subtask 0）

显然一位数正读倒读都是它自己，输出 $a$ 即可。

做法 2（Subtask 1,2）

考虑手玩或打表。

做法 3（$a=0,c=1$）

定义 $\operatorname{rev}(x)$ 为数 $x$ 反转之后的结果。

考虑构造 $\operatorname{rev}(998,\!244,\!353k)\equiv b\pmod{998,\!244,\!353}$，但是这样枚举量太大了了。不考虑前导后缀 $0$ 的话，考虑构造 $\operatorname{rev}(998,\!244,\!353k)\times10^u\equiv b\pmod{998,\!244,\!353}$。我们猜测，在 $k$ 和 $u$ 在一定的范围内必定有解。迭代其中一个，预处理另一个即可。

期望得分：$0$。

做法 4（Subtask 5）

考虑两个问题，

• 如何去掉 $a=0$ 这个特殊限制。
• 如何去掉前后缀的 $0$。

对于 $a\neq0$，我们考虑一个性质：$0\cdot 10^k+a=a$。

由此，我们可以想到如下构造：

显然，这样构造出来的数正着读余 $a$，倒着余 $b$。所以它符合条件。

我们考虑如何去掉前后缀的 $0$。我们可以把 $0$ 替换为一些不是 $0$ 的东西，但效果一样。这需要一个东西正读倒读都余 $0$。可以发现$A=649{,}938{,}929{,}839{,}946$ 符合条件。我们把前后缀的 $15$ 个 $0$ 替换成 $A$ 即可。（可以简单地保证至少有 $15$ 个 $0$）

为何数据不随机的情况下这个算法是正确的呢？

借用机器的算力我们可以证明：考虑这么一个事情，我们假如让每一个数取 $10$ 模 $998,\!244,\!353$ 的离散对数。（$10$ 是模 $998,\!244,\!353$ 的原根）打出 $10^6$ 以内的 $\operatorname{rev}(998,\!244,\!353k)$ 表后，发现对数的 gap 在 $2\times10^4$ 的级别。因此我们可以最多迭代 $2\times10^4$ 级别的 $u$ 就可以得到答案。长度不超过 $4\times10^4$ 级别。

实际上，有很多对撞算法也可以以很高概率得到正解，因为没法对着卡，所以本题数据实际上是随机造的。

Bonus

保证数据随机，请你保证答案在 $2^{127}-1$ 以内。

代码：

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i)
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
const ll mod1=998244353;
const ll g=10;
const ll inv_g=299473306;
const string f15="649938929839946";
string s,t;
int rev(ll x)
{
	ll v=0;
	rep(i,18)
	{
		v=v*10+x%10;x/=10;
	}
	return v%mod1;
}
string revv(ll x)
{
	string f="";
	rep(i,18)
	{
		f+=char('0'+x%10);x/=10;
	}
	return f;
}
map<int,int> idx;
string gett(ll a)// mod 0 = a
{
	string v="";
	int c=15;rep(i,c)a=a*inv_g%mod1;
	while(!idx.count(a))
	{
		a=a*inv_g%mod1;
		++c;
	}
	int fst=idx[a];
	v=revv(fst*mod1);
	rep(i,c-15) v+="0";
	v+=f15;
	return v;
}
void init()
{
	rep(i,1000001) idx[rev(i*mod1)]=i;
}
void solve()
{
	int a,b;
	cin>>a>>b;
	s=gett(a);t=gett(b);
	reverse(t.begin(),t.end());cout<<t<<s<<endl;
}
int main()
{
	init();
	ios_base::sync_with_stdio(false);
	int t,c;cin>>t>>c;
	while(t--)
	solve();
	return 0;
}