【AtCoder Regular Contest 075 F】Mirrored

mrsrz 3月 08, 2020

思维题。

题目大意：

给定 $D$，定义 $\mathrm{rev}(N)$ 为将 $N$ 翻转后去掉前导 $0$ 后得到的数。

求有多少个 $N$ 满足 $\mathrm{rev}(N)=N+D$。

题解：

以四位数为例。

我们设 $N=1000a+100b+10c+d$，则 $\mathrm{rev}(N)=1000d+100c+10b+a$。

也就是说，$D=1000(d-a)+100(c-b)+10(b-c)+(a-d)=999(d-a)+90(c-b)$。

显然 $D$ 必须是 $9$ 的倍数。那么：

$\frac D 9=111(d-a)+10(c-b)$

由于 $a,b,c,d\in[0,9]$ 且是整数，所以 $d-a,c-b\in[0,9]$。

那么唯一能影响到个位的只有 $111(d-a)$，所以 $d-a$ 的值是确定的，这两个位能选的方案数也是确定的。

接下来能影响到十位的只有 $10(c-b)$，同理也是唯一确定的。

其他位数的也以此类推，一位一位确定即可，最后判一下是否为 $0$ 即可。

如果位数是奇数，则中间的那位是可以任意钦定的，其方案数要乘 $10$。

Code：

#include<cstdio>
#include<cmath>
typedef long long LL;
int D;
LL ans=0;
LL solve(int len){
    LL now=0,ans=1;
    for(int l=0,r=len-1;l<r;++l,--r){
        LL dw=(LL)pow(10,l),qaq=((LL)pow(10,r)-dw)/9;
        if(now<D){
            int wg=(D-now)/dw%10;
            now+=qaq*wg;
            ans=ans*(10-wg-(l==0));
        }else{
            int wg=(now-D)/dw%10;
            now-=qaq*wg;
            ans=ans*(10-wg-(l==0));
        }
    }
    if(len&1)ans*=10;
    if(now==D)return ans;
    return 0;
}
int main(){
    scanf("%d",&D);
    if(D%9)return puts("0"),0;
    D/=9;
    for(int i=1;i<=18;++i)
    if(pow(10,i)>D)ans+=solve(i);
    printf("%lld\n",ans);
    return 0;
}