(ARC_075_D) 镜像

题解

题意

形式化题意

对于正整数 n，定义 rev(n) 为将 n 的十进制表示（不含前导零）左右反转后得到的整数。

给定正整数 D，求满足以下条件的正整数 N 的个数：

rev(N) = N + D

数据范围

• 1 ≤ D < 10⁹

解法

非常恶心的搜索题。

首先根据题意，我们可以很容易想到去分析一个数跟他的反转数的差值是怎么样的。

那么我们就来分析吧。

首先对于一个数$abcdef$,其中每一个字母表示这个数的数位上的数字。

那么$rev(abcdef)=fedcba$

那么根据条件，这个数满足当且仅当$fedcba-abcdef=D$

拆一下每一位的贡献，那么

$$\begin{aligned} D &= (f-a) \cdot 10^5+(e-b) \cdot 10^4+(d-c) \cdot 10^3+(c-d) \cdot 10^2+(b-e) \cdot 10+(a-f) \cdot 1 \\ &= (f-a) \cdot (10^5-1) +(e-b) \cdot (10^4-10) +(d-c) \cdot (10^3-10^2) \end{aligned}$$

既然转成这样了，这样相当于我们只需要枚举每一对数字之间的差值就行了,同一差值可能存在的数字组合是固定的（注意首位特殊处理，不能有前导零）。这样的话我们的枚举范围就大大减小了。

除此之外，我们注意到靠近中间的位$(d-c)$随着长度的增长，这个系数$(10^3-10^2)$会变大，最多如果变大到比$D$大的话，那么无论其他数怎么填都无法满足条件。

由此我们可以粗略估计这个数不会超过$10^{18}$这个级别。

那么通过这个转化，我们的枚举也降到了$10^9$这个级别。 但显然还是过不了。

但我们发现如果暴力枚举每对数的差值，那么这个数很多情况都是不等于$D$的。

于是我们由此考虑剪枝，在我们填数时什么情况下最终一定凑不出$D$呢？

根据我们举的例子，假设此时我们要填$(f-a)$的差值，假设我们已经填好了这个值，那么接下来就要使剩下的数填完后$=(D-(f-a) \cdot (10^5-1))$而观察式子，在移项后，等式右边的数无论后面的差值怎么填都一定满足是$10$的倍数！

继续推下去，我们发现，想要满足条件，假设当前填的差值的系数是$(10^r-10^l)$后剩下的数一定要满足能被$10^{l+1}$整除。

而满足这个条件的差值最多只有$2$个，所以时间直接被剪枝到了$2^9$这个极小的级别，然后就能过了。

但这个细节挺多的，特别注意如果长度是奇数，那么中间数是可以任意填的，所以方案数要$*10$

代码

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll ten[20];
ll d;
ll anss=0;
inline void dfs(int len,int i,ll now,ll sum,int r,int l)
{
    if(i==(len/2))
    {
        if(!now)
        {
            ll ans=1;
            if(len%2==1) ans*=10;
            for(int j=1;j<=len/2;j++)
            {
                ll k=sum%19ll;
                sum/=19ll;
                if((k+1)>=10)
                {
                    k=(k+1)%10;
                    if((j==len/2)&&k==0) ans*=9ll;
                    else ans*=(10ll-k);
                }
                else
                {
                    if((j==len/2)) ans*=(9ll-(k+1ll));
                    else ans*=(10ll-(k+1ll));
                }
            }
            anss+=ans;
        }
        else return ;
    }
    else
    {
        for(ll j=0;j<=18;j++)
        {
            if(((now-(((j+1)>=10)?(-1ll*((j+1)%10)):(j+1))*(ten[r]-ten[l]))%ten[l+1])==0)
            dfs(len,i+1,(now-(((j+1)>=10)?(-1*((j+1)%10)):(j+1))*(ten[r]-ten[l])),sum*19+j,r-1,l+1);   
        }
    }
}
int main()
{
    // freopen("4.in","r",stdin);
    // freopen("4.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>d;
    ten[0]=1;
    for(int i=1;i<=17;i++) ten[i]=ten[i-1]*10ll;
    for(int len=1;len<=18;len++)
    {
        dfs(len,0,d,0,len-1,0);
    }
    cout<<anss;
    return 0;
}