跳到主要内容

BiodoSC-2025 II 模拟

比赛：2025深圳南宁夏令营模拟赛 NOIP模拟赛2
类型：NOIP 模拟赛
日期：2025-07-28
链接：https://yundouxueyuan.com/d/sznn202507/contest/68874f765f28a9443c912809

100+50+20+1=171pts.100+50+20+1=171pts.

T2 求解​

纯数学题，唉。这里只写一下关键的步骤。一看这个 n≤109n\le10^9，肯定是 O(1)O(1) 没跑了。

题目中要求的 ans\text{ans} 可以转化为：

ans=[∑k=1m(2k−1)×10k−1×9] mod M=9[∑k=1m(2k−1)×10k−1] mod M.\text{ans}=[\sum_{k=1}^m{(2k-1)\times10^{k-1}\times9}]\bmod M=9[\sum_{k=1}^m{(2k-1)\times10^{k-1}]\bmod M.}

其中 M=233,333M=233,333，m=12(n+1)m=\frac{1}{2}(n+1)。注意，2,3332,333 是素数，23,33323,333 也是素数，但是 233,333233,333 不是素数。。

我们盯住 ∑\sum 开头的那串，首先变形成等比数列：

记：x=∑k=1m(2k−1)×10k−1.x=\sum_{k=1}^{m}(2k-1)\times10^{k-1}.

10x=∑k=1m(2k−1)×10k=(2m−1)×10m+∑k=1m−1(2k−1)×10k.10x=\sum_{k=1}^{m}(2k-1)\times10^k=(2m-1)\times10^m+\sum_{k=1}^{m-1}(2k-1)\times10^{k}.

而 ∑k=1m−1(2k−1)×10k=∑k=2m(2k−3)×10k−1.\sum_{k=1}^{m-1}(2k-1)\times10^{k}=\sum_{k=2}^{m}(2k-3)\times10^{k-1}.（换元，把 kk 换成 k−1k-1）

9x=10x−x=(2m−1)×10m+[∑k=2m(2k−3)×10k−1−∑k=1m(2k−1)×10k−1].9x=10x-x=(2m-1)\times10^m+[\sum_{k=2}^m(2k-3)\times10^{k-1}-\sum_{k=1}^m(2k-1)\times10^{k-1}].

我们再关注后面中括号的式子，变形：=1+∑k=2m[(2k−3)−(2k−1)]×10k−1=1−2∑k=2m10k−1=1−2∑k=1m−110k.=1+\sum_{k=2}^m[(2k-3)-(2k-1)]\times10^{k-1}=1-2\sum_{k=2}^m10^{k-1}=1-2\sum_{k=1}^{m-1}10^k.

所以：9x=(2m−1)×10m−2∑k=1m−110k−1.9x=(2m-1)\times10^m-2\sum_{k=1}^{m-1}10^k-1.

然后用裂项相消法来计算 ∑10k\sum10^k：

记 y=∑k=1m−110k.y=\sum_{k=1}^{m-1}10^k.

10y=∑k=2m10k.10y=\sum_{k=2}^{m}10^k.

9y=10y−9y=∑k=2m10k−∑k=1m−110k=10m−10.9y=10y-9y=\sum_{k=2}^m10^k-\sum_{k=1}^{m-1}10^k=10^m-10.

把这个式子除以 9 就得到 yy。

让我们把所有东西撮一块儿：

ans=(2m−1)×10m−29(10m−10) mod M\text{ans}=(2m-1)\times10^m-\frac{2}{9}(10^m-10)\bmod M

我去，还要除以 9，那么我们求逆元吧。（注意 M=233,333M=233,333 不是素数，不能用费马小定理。）