题解

· · 题解

前言

非常 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\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;
}