题解：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。

答案