自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 21:32:08，当前版本为作者最后更新于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$ 含前导零。

思路：

1. 通过数学方法推导出公式。

2. 因为位数 $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		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		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		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;
}

update 21.6.8：将代码尽量改成了初学者能够接受的写法，并更正了笔误。