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)