P1643 完美数

· · 题解

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;
}