九度 OJ 1491 清华机试：大数计数 1 和 2 的个数模 20123

题目大意

给定大整数 N（≤10^100），求 1~N 中数字 1 和 2 出现的总次数，对 20123 取模。

逐位递推公式

设已处理前缀 num，当前位 t，结果 res，前缀中 1/2 个数 cnt。
新前缀 num' = num*10 + t，新结果：

res = (res - cnt) * 10 + cnt * (t + 1) + num * 2 + min(t, 2);
cnt += (t==1 || t==2);
num = num' % 20123;
res %= 20123;

公式推导

1. (res - cnt) * 10：原前缀（除最后一位）的 1/2 计数扩展 10 倍
2. cnt * (t + 1)：最后一位固定为 0..t，贡献 cnt 次
3. num * 2：新位为 1/2 的情况，每个前缀贡献 2 次
4. min(t, 2)：最后一位本身为 1/2 的额外贡献

C++ 实现

#include 
#include 
#include 
using namespace std;

int main() {
    char N[110];
    while (cin >> N) {
        int len = strlen(N);
        int res = 0, num = 0, cnt = 0;
        for (int i = 0; i < len; ++i) {
            int t = N[i] - '0';
            res = ((res - cnt) * 10 + cnt * (t + 1) + num * 2 + min(t, 2)) % 20123;
            num = (num * 10 + t) % 20123;
            if (t == 1 || t == 2) ++cnt;
        }
        printf("%d\n", (res + 20123) % 20123);
    }
    return 0;
}

复杂度

• 时间：O(len) ≤ 100
• 空间：O(1)

关键技巧

1. 大数逐位处理：无需大整数库
2. 模算术贯穿：中间结果均模 20123 防溢出
3. 状态压缩：仅需 res, num, cnt 三变量