题解：P13929 [蓝桥杯 2022 省 Java B] 山

关于这种直接提交答案的题，如果大家在考试中，不会的话，那么就可以先打表把所有的可能（这题是大概 $10^9$）模拟一遍。因为咱们可以等呀，考试几个小时几千秒，足够运行完 $10^{10}$（保守估计）的次数了。这题就可以大模拟运行他几分钟，算出答案 $3138$ 就可以提交了，提交的时候，那个程序就是 $O(1)$ 的，不用担心超时。

废话不多说。

分析一下要求：

既然要求回文，令数位为 $k$，那么我们只需要考虑前一半就行了（如果 $k$ 是奇数，那么最中间的一位也需要考虑）。

那么第一位不能是 $0$。

因为第 $1$ 为非零，而且后面的都不能比 $1$ 小，所以我们永远用不到 $0$ 这个数字，只需要考虑其他的九个数字就行了。

强调一下，我们这里说的只是在上面说到需要考虑的，后面回文的部分就不考虑了。

要求不递减而且可以重复数字，那么根据一个公式：

如果说一共有 $n$ 个可选项，而且可以重复选，一共选 $k$ 个，那么总排列组合数量就是 $C^{n+k-1}_{k}$。

将 $k$ 个待选的用圆点表示，然后用 $n-1$ 个线把这些圆点分成 $n$ 组。第 $i$ 组中圆点的个数表示了第 $i$ 个待选项的选择次数。

那么先不区分圆点和线，那么排列方式就是一共有 $(n+k-1)!$

然后去掉重复的功能，就是有 $\frac{(n+k-1)!}{k!\times (n-1)!}$ 种。

我们这里只需要对于十位数和四位数特殊讨论即可。（因为这俩是不满的，有一部分在区间外）

四位数：因为下限是 $2022$，所以第一位数不小于 $2$，可选项就是从 $2$ 到 $9$ 了。因为后面不可能选到 $0$，所以只考虑第一位就涵括了所有区间外的可能。带入上面公式 $n=8,k=2$ 算得 $36$。

十位数：从 $2000000000$ 到区间末尾 $2022222022$，可以证明不存在。因为怎么找都会有 $0$ 了。

从 $1000000000$ 到 $1999999999$ 这些，排除第一位为 $1$ 后，中间四位就带入 $n=9,k=4$ 即可。得到 $495$

其他的数位的话，求一下 $\sum^{9}_{i=5} \frac {(8+i)!}{i!\times 8!}$ 即可。求得 $2607$（这个问题可以抛给 c++）。

最后把答案加起来：$36+495+2607=3138$。

$3138$。