B3883

· · 题解

加强 By @沉石鱼惊旋

upd 2023.11.13 20:59 修改一处表达错误。

upd 2023.11.22 21:06 修改 std。

upd 2023.12.30 15:22 添加 ShanireZ 按题解实现的做法。

简要题意

求 [1,n] 中有多少回文数,对 20091119 取模。

模数是我的生日。

题目思路

考虑分成 len=\left\vert n\right\vert 和 len<\left\vert n\right\vert 两部分。

我们会发现答案一定是 $[10\dots000000\dots01,999999\dots99999]$ 的形式,所以这一部分答案就是 $\sum 9\times 10^{\left\lceil\frac{len}{2}\right\rceil-1}$。 然后考虑 $len=\left\vert n\right\vert$ 怎么做,我们可以先把他搞成**最大的比 $n$ 小的回文串**。那么答案就在 $10\dots000000\dots01$ 到刚才这个回文串之间。统计个数是简单的,类似高精度减法即可,而且这里没有退位操作。 ```cpp void pre_ans() { for (int len = 1; len < n; len++) { int m = (len + 1) >> 1; (ans += qpow(10, m - 1) * 9) %= p; } } ``` # 完整代码 感谢 @[Aaplloo](https://www.luogu.com.cn/user/137426) 指出的错误。 ~~题解中提到的实现等我什么时候调完代码什么时候放。~~ [Code by @irris](https://www.luogu.com.cn/paste/wvlxskaj) [Code by @ShanireZ](https://www.luogu.com.cn/paste/4ic34ae8)