题解 P1940 Reversible Number

阿丑 · 2021-05-10 09:42:29 · 题解

传送门

题目大意：

求小于 10^x 并且满足“对其倒序数与其本身求和的结果每位数都是奇数”的数的数量。
3 \le x \le 400

题目中的例子：n=409，其倒序数 reverse(n) 就是 904，求和是1313，每位数都是奇数，满足条件。

而题目中的首位不能是 0，指的不仅是 n 不含前导零，还指不能有 n=10 这样的情况，因为 reverse(10)=01 含前导零。

思路：

通过数学方法推导出公式。
因为位数 x\le 400，暴力高精即可。

下文将 n+reverse(n) 记作 sum(n)。

数学部分

假设 n=\overline{a_{f(n)}a_{f(n)-1}...a_2a_1}，其中 f(n) 表示 n 的位数，且有 0 \le a \le 9，a_1、a_{f(n)} \ne 0。

则 n+reverse(n)=\overline{a_{f(n)}a_{f(n)-1}...a_2a_1}+\overline{a_1a_2...a_{f(n)-1}a_{f(n)}}

=\sum\limits^{f(n)}_{i=1}(a_i+a_{f(n)-i+1})×10^{i-1}

为叙述方便，下列表格表示了 \sum 中的每一项。以 f(n)=7 为例。

[7]	[6]	[5]	[4]	[3]	[2]	[1]
a_7+a_1	a_6+a_2	a_5+a_3	a_4+a_4	a_3+a_5	a_2+a_6	a_1+a_7

显然，第 i 项（a_i+a_{f(n)-i+1}）和第 f(n)-i+1 项（a_{f(n)-i+1}+a_{f(n)-(f(n)-i+1)+1}）完全相同；并且 sum(n) 的第 i 位就等于第 i 项的个位和第 i-1 项的十位之和。接下来会借助这两点性质，将 sum(n) 的可能情况讨论出来。

温馨提示：请注意区分 sum(n) 的第 i 位和 [i]（即第 i 项）之间的区别。

首先，为使第 1 位（从右往左）为奇数，[1] 中必须为奇数。考虑到进位对其他位的影响，分为两种情况：大于 10 的奇数与小于 10 的奇数。

1、[1] 中是大于 10 的奇数

此时，[1]（a_1+a_7）可以取 11、13、15、17，不妨以 15 为例。

[7]	[6]	[5]	[4]	[3]	[2]	[1]
15	？	？	？	？	？	15

这里，[6] 是不能进位的，否则会使 sum(n) 的第 7 位成为偶数。而由第 2 位为奇数知，[2] 内一定是偶数（因为 [1] 进位了）而 [2] 与 [6] 相同，故是不进位的偶数，即 0、2、4、6 或 8。以 8 为例。

[7]	[6]	[5]	[4]	[3]	[2]	[1]
15	8	？	？	？	8	15

同理，[5] 必须进位，而 [3] 必须是奇数，那么就是进位的奇数，可以发现与 [1]、[7] 符合的条件相同，即产生了循环。那么剩下的过程就可以递归求解。

但由于 f(n) 的不同，情况也会不一样；由于四位（左右各两位）一循环，所以有四种情况。

1° f(n)\%4=0

以 f(n)=4 为例。

[4]	[3]	[2]	[1]
15	8	8	15

此时第 3 位是偶数，不满足题设。

2° f(n)\% 4=1

以 f(n)=5 为例。

[5]	[4]	[3]	[2]	[1]
15	8	11	8	15

此时 [3] 是奇数，而 [3]=2a_2 为偶数，两者冲突。

3° f(n)\% 4=2

以 f(n)=6 为例。

[6]	[5]	[4]	[3]	[2]	[1]
15	8	11	11	8	15

此时第 4 位是偶数（11_{[4]}\%10+11_{[3]}/10=2），不满足题设。

4° f(n)\% 4=3

以 f(n)=7 为例。

[7]	[6]	[5]	[4]	[3]	[2]	[1]
15	8	11	6	11	8	15

此时是可以满足题设的。（与上表对应的 sum(n) 为 15917195）

而通过枚举数学方法得知，[1] 与 [7] 对应的 a_1 与 a_7 一共有 20 种情况，[4] 对应的 a_4 有 5 种情况（请自行推导 orz）。而 [6] 与 [2] 有 20 种情况，[5] 与 [3] 有 25 种情况。而在上文推导过，一次“循环”是两位，由乘法原理知一次“循环”是 20×25=500 种情况。

故一共有 20×5×500^{(f(n)-3)/4} 种情况。注意，一定在 f(n)\equiv 3(mod 4) 时才成立。

2、[1] 中是小于 10 的奇数

此时，[1] 可以取 1、3、5、7、9，不妨以 7 为例。

[7]	[6]	[5]	[4]	[3]	[2]	[1]
7	？	？	？	？	？	7

[6] 不能进位，否则会使第 7 位成为偶数。而由第 2 位为奇数知，[2] 内一定是奇数。故是不进位的奇数，与 [1]、[7] 符合条件相同。即再次产生了循环。

当然，f(n) 不同时情况也不一样。当 f(n)\% 2=1 时，最中间一位会是奇数。仍以 f(n)=7 作为例子，即 [4] 为奇数；而 [4]=2a_4 为偶数，矛盾。

当 f(n)\% 2=0 时，以 f(n)=4 为例：

[4]	[3]	[2]	[1]
5	3	3	5

类似地，可以推出 [1] 与 [4] 对应的 a_1、a_4 有 20 种情况，而 [3]、[2] 对应的 a_2、a_3 有 25 种情况，即一“循环”是 25 种情况。一共有 20×25^{(f(n)-2)/2} 种情况。

高精部分

由以上的数学推论，可以知道我们只需要写出高精乘低精、高精加高精（统计答案）即可。具体写法可以参考代码部分。

#include<bits/stdc++.h>
using namespace std;
const int N=400+20;
struct BigInt {
    int a[N], len;
    inline void carry() {   //进位，顺便更新 len 
        for(int i=0; i<len; i++) {
            a[i+1]+=a[i]/10, a[i]%=10;
            if(a[len]) ++len;   //更新 len 
        }
    }
    BigInt operator = (int i2) {    //将低精赋值给高精 
        for(int i=1; i<=N-3; i++) a[i]=0;   //清零 
        len=1, a[0]=i2, carry();
    }
    BigInt operator * (int i2) {    //高精乘低精
        BigInt ret=*this;
        for(int i=0; i<ret.len; i++) ret.a[i]*=i2;
        ret.carry();
        return ret;
    }
    BigInt operator + (BigInt b2) { //高精加高精
        BigInt ret=*this;
        ret.len=max(ret.len, b2.len);
        for(int i=0; i<ret.len; i++) ret.a[i]+=b2.a[i];
        ret.carry();
        return ret;
    }
    inline void output() {  //输出
        for(int i=len-1; i>=0; i--) printf("%d", a[i]);
    }
} ans;

int x;
int main() {
    ans=0;
    scanf("%d", &x);
    for(int i=1; i<=x; i++) {   //从 1 到 x 都要计算
        if(i%2==0) {    //f(n)%2==0
            BigInt dl;
            dl=20;
            for(int t=1; t<=(i-2)/2; t++) dl=dl*30; //(i-2)/2 次幂 
            ans=ans+dl;
        } else if(i%4==3) { //f(n)%4==3
            BigInt dl;
            dl=20*5;
            for(int t=1; t<=(i-3)/4; t++) dl=dl*(20*25);    //(i-3)/4 次幂
            ans=ans+dl;
        } 
    }
    ans.output();
    return 0;
}