题解文字教学

本题要求统计 $n!$ 的十进制表示中某个特定数码 $a$ 出现的次数。$n$ 最大为 $1000$，$n!$ 的位数大约在 $2568$ 位左右，无法用标准整型存储，需要用高精度乘法模拟阶乘计算。

核心思路

1. 用一个足够大的整型数组（如 a[3000]）来存储阶乘结果的每一位，a[0] 表示个位，a[1] 表示十位，依此类推，并维护一个变量 len 表示当前有效位数。
2. 初始时设置 a[0] = 1，len = 1。
3. 遍历乘数 i 从 $2$ 到 $n$，每次将当前数组的每一位乘以 i，并处理进位。具体操作：
   • 从低位到高位，将 a[j] * i 加上之前的进位 car，结果存为 tmp；
   • a[j] = tmp % 10，car = tmp / 10；
   • 循环直至所有位均处理，最后若 car 仍有值，则将其逐位存入数组并更新 len。
4. 得到完整的 $n!$ 后，遍历数组前 len 位，统计数码 $a$ 出现的次数。

复杂度
每组数据需要 $O(n \times \text{位数})$ 的时间，$t \le 10$，$n \le 1000$，完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, d;
        cin >> n >> d;
        int a[3000] = {0};
        a[0] = 1;
        int len = 1;
        for (int i = 2; i <= n; ++i) {
            int car = 0;
            for (int j = 0; j < len; ++j) {
                int tmp = a[j] * i + car;
                a[j] = tmp % 10;
                car = tmp / 10;
            }
            while (car) {
                a[len++] = car % 10;
                car /= 10;
            }
        }
        int ans = 0;
        for (int i = 0; i < len; ++i)
            if (a[i] == d) ++ans;
        cout << ans << endl;
    }
    return 0;
}