解题思路

n 最大是 10000，而 10000! 有 3 万多位，结果远远超过所有整数类型能存的范围，必须用高精度数组一位一位地存。

如果一位一位存，乘 2 到 n 一共要乘 1 万多次，每次处理 3 万多位，运算量太大，容易超时。这里用一个小技巧加速：每个格子存 4 位数字（0~9999），这样要处理的格子数少了 4 倍，速度快很多。

做法：a[0] 存最低的 4 位，依次乘上 2、3、…、n。每一位算 a[i]×k + 进位，超过 9999 的部分往高一位进。最后输出时，最高的一格直接输出，其余每格不够 4 位的要在前面补 0（例如某格是 7，就要输出 0007）。

用 int 存 4 位数字是安全的：9999 × 10000 ≈ 10^8，加上进位也不会超过 int 的最大值 2.1×10^9。

参考代码

#include <iostream>
using namespace std;

int a[9000];   // 每格存4位数字（0~9999），a[0]是最低的4位

int main() {
    int n;
    cin >> n;
    a[0] = 1;        // 1! = 1
    int len = 1;     // 用了几格

    // 依次乘上 2, 3, ..., n
    for (int k = 2; k <= n; k++) {
        int carry = 0;   // 进位
        for (int i = 0; i < len; i++) {
            a[i] = a[i] * k + carry;
            carry = a[i] / 10000;   // 超过9999的部分往高一位进
            a[i] %= 10000;
        }
        // 最高位还有进位，扩展格子
        while (carry) {
            a[len] = carry % 10000;
            carry /= 10000;
            len++;
        }
    }
    // 输出：最高一格直接输出，其余每格前面要补足0
    cout << a[len - 1];
    for (int i = len - 2; i >= 0; i--) {
        if (a[i] >= 1000) cout << a[i];
        else if (a[i] >= 100) cout << "0" << a[i];
        else if (a[i] >= 10) cout << "00" << a[i];
        else cout << "000" << a[i];
    }
    return 0;
}

复杂度分析

每 4 位存一格后，n! 大约有 n/4 × 位数/4 的量级，设结果格数为 L，总运算量约 O(n×L)。用基数 10000 比一位一位存快约 4 倍，可以稳稳通过 10000! 的时限。额外空间复杂度 O(L)。