自动搬运

查看原文

来自洛谷，原作者为

	Cure_Wing 我想：希望是本无所谓有，无所谓无的。这正如地上的路；其实地上本没有路，走的人多了，也便成了路。

搬运于2025-08-24 21:27:26，当前版本为作者最后更新于2024-01-10 13:36:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P1643 完美数

思路

一道折磨人的高精度......

可以想象的是，对于一个回文数，我们只需要看前 $\lceil\dfrac{k}{2}\rceil$ 位的状态就可以了，因为左右对称。

那么一种暴力的思路就是对着前 $\lceil\dfrac{k}{2}\rceil$ 位的状态暴力分奇偶回文加数，直到加到 $N$ 次为止。当然可以根据长度为 $k$ 的回文串个数优化一下，但是只能拿到 $80$ 分的高分。

这种做法时间复杂度看起来不是很大，只需要加大约 $N$ 次。但是由于计算到后面数的位数特别多，也就导致了在高精上时间耗费过多而超时。

这个时候我们想，既然已经知道了这个数距离 $X$ 有 $N$ 个回文数，那么能不能求出 $1$ 到 $X$ 有多少个回文数呢？这样的话就可以知道 $1$ 到 $N$ 的回文数个数了。

有什么用呢？考虑我们知道 $Y$ 是第 $a$ 个回文数，我们可以先求出 $Y$ 的位数。因为长度为 $l$ 的回文串一共有 $9\times10^{\lceil\frac{l}{2}\rceil-1}$ 个（首位不为 $0$ 有 $9$ 种，其余位有 $10$ 个数可填），我们可以依次减去 $9\times10^{\lceil\frac{i}{2}\rceil-1}$，如果遇到不能减的数为 $9\times10^{\lceil\frac{k}{2}\rceil-1}$，此时剩下的数为 $p$，说明 $Y$ 是长度为 $k$ 的回文串中第 $p$ 小的数。然后我们只需要对 $p$ 加上 $10^{\lceil\frac{k}{2}\rceil-1}$ 的基础数（保证长度为 $k$），再减去 $1$ 的次序（长度为 $k$ 的串可以从 $10^{\lceil\frac{k}{2}\rceil-1}$ 开始），就得到了答案。

现在的问题就变成了求 $X$ 前面（包括 $X$）一共有多少个回文串。考虑把刚才的过程反过来，如果这个回文串的长度为 $k$，那么它前面一定存在长度为 $1\sim(k-1)$ 的回文串，可以先把它们的个数加起来。对于长度为 $k$ 的回文串，设这个数的前 $\lceil\dfrac{k}{2}\rceil$ 位组成的数为 $w$，那么还剩下 $(w-10^{\lceil\frac{k}{2}\rceil-1}+1)$ 个数可以选择，而这之中以 $(10^{\lceil\frac{k}{2}\rceil-1}\sim w-1)$ 作为前缀（$k$ 分奇偶）都可以作为前缀，此时只需要考虑 $w$ 作为前缀的情况。此时分类讨论一下，如果 $w$ 组成的串大于 $X$ 则不能作为答案，反之可以。

看似到这里就做完了，但是依旧存在和第一个做法一样的问题：由于计算的数过大，直接相加或相乘会浪费大量的时间，于是我们可以直接存储计算结果：比如要算 $\sum\limits_{i=1}^k9\times10^{\lceil\frac{i}{2}\rceil-1}$ 的值，可以手玩发现当 $k$ 为偶数时答案形如 $1999\dots9998$（长度为 $k$）的形式，如果说是奇数的话再补上 $i=k$ 的答案即可。

结果就是跑得飞快，平均不超过 10ms。

最后不要忘记判断一下回文串长度的奇偶性就可以了。

时间复杂度约为 $O(\sum(|X|+|N|))$，其中 $|X|,|N|$ 分别表示数 $X,N$ 的位数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using std::cin;using std::cout;
constexpr int N=20005;
int t;
struct Bigint{//高精度模板部分
    int a[N],len=0;
    inline Bigint(int x=0){
        len=0;memset(a,0,sizeof(a));
        for(int i=x;i;i/=10) a[++len]=i%10;
    }
    inline void scan(){
        std::string s;cin>>s;len=s.size();memset(a,0,sizeof(a));
        for(int i=0;i<len;++i) a[len-i]=s[i]-'0';
    }
    inline int& operator[](int i){return a[i];}
    inline void flatten(int L){
        len=L;
        for(int i=1;i<=len;++i){a[i+1]+=a[i]/10;a[i]%=10;}
        for(;!a[len]&&len>1;--len);
    }
    inline void print(std::string s=""){for(int i=len;i;--i) cout<<a[i];cout<<s;}
    inline void reflectl(){for(int i=1;i<=len/2;++i) a[i]=a[len-i+1];}//翻转数的前半部分，用于还原前缀
    inline Bigint substr(int l,int r){//提取数的部分，用于提取前缀
        Bigint c;c.len=r-l+1;
        for(int i=1;i<=c.len;++i) c[i]=a[l+i-1];
        return c;
    }
}x,n,ans,now1,now2,zero(0);
inline bool operator<(Bigint a,Bigint b){
    if(a.len!=b.len) return a.len<b.len;
    for(int i=a.len;i;--i)
        if(a[i]!=b[i])
            return a[i]<b[i];
    return 0;
}
inline Bigint operator+(Bigint a,Bigint b){
    Bigint c;int len=std::max(a.len,b.len)+1;
    for(int i=1;i<=len;++i) c[i]=a[i]+b[i];
    c.flatten(len);
    return c;
}
inline Bigint operator-(Bigint a,Bigint b){
    Bigint c;
    for(int i=1;i<=a.len;++i){
        if(a[i]<b[i]){a[i]+=10;--a[i+1];}
        c[i]=a[i]-b[i];
    }
    c.flatten(a.len);
    return c;
}
inline Bigint operator*(Bigint a,int b){
    Bigint c;
    for(int i=1;i<=a.len;++i) c[i]=a[i]*b;
    c.flatten(a.len+11);
    return c;
}
inline Bigint operator<<(Bigint a,int b){
    Bigint c;
    for(int i=1;i<=a.len;++i) c[i+b]=a[i];
    c.flatten(a.len+b);
    return c;
}//左移数，用于还原前缀
inline Bigint rank(Bigint k){//计算前面有多少回文数
    Bigint ans(0),tot;
    int q=(k.len-1)/2;//直接计算答案
    if(q==0){ans.len=1;ans[1]=0;}
    else{
        ans.len=q+1;
        ans[1]=8;ans[q+1]=1;
        for(int i=2;i<=q;++i) ans[i]=9;
    }
    if(k.len%2==0){
        if(q){ans[ans.len]=0;ans[++ans.len]=1;}
        else ans[1]=9;
    }
    tot.len=q+1;tot[q+1]=1;
    ans=ans+k.substr(k.len-(k.len+1)/2+1,k.len);
    ans=ans-tot+Bigint(1);//ans 计算应有回文个数
    Bigint w=k;w.reflectl();
    if(k<w) ans=ans-Bigint(1);//判断 w 是否可行
    return ans;
}
inline Bigint get(Bigint x){//计算排名对应的回文数
    Bigint ans(0),tot(0),nxt(0);int b=1;//初始长度为 1，是奇前缀
    int q=x.len,cnt=0;
    tot.len=ans.len=std::max(q-1,1);//直接计算所得数
    if(q-1>1){ans[q-1]=1;ans[1]=8;for(int i=2;i<q-1;++i) ans[i]=9;}
    if(q-1>0){tot[q-1]=9;}
    if(ans+tot<x){ans=ans+tot;++cnt;b^=1;}
    if(ans+tot<x){ans=ans+tot;++cnt;b^=1;}//根据加和次数判断此时前缀的奇偶性
    q+=cnt/2-1;
    tot[tot.len]=0;tot[tot.len=q]=1;
    Bigint sum=x-ans;sum=sum+tot-Bigint(1);//根据上面的式子计算
    if(b&1) sum=(sum<<(sum.len-1));//将前缀还原，分奇偶性讨论
    else sum=(sum<<sum.len);
    sum.reflectl();
    return sum;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
    for(cin>>t;t--;){
        x.scan();n.scan();
        get(n+rank(x)).print("\n");//当前排名 = 前面的回文数 + 中间的回文数
    }
    return 0;
}