题目链接：nyoj 28

这是一个关于高精度计算的问题，解决大数阶乘的挑战。最初我尝试使用预计算表的方法，但内存超出了题目限制（5w+kb）。通过多种优化技巧，成功将内存消耗降低到要求范围内，以下是我的实现代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int MAX_N = 5002;
 8 const int MOD = 1e6;
 9 
10 int result[MAX_N + 3][2800], digit_count[MAX_N + 3];
11 
12 inline void initialize(int limit = MAX_N) {
13     result[1][0] = 1;    digit_count[1] = 1;
14     for(int i = 2; i <= limit; ++i) {
15         int current_length = digit_count[i - 1];
16         int carry = 0;
17         LL temp;
18         for(int j = 0; j < current_length; ++j) {
19             temp = carry + (LL)result[i - 1][j] * i;
20             result[i][j] = temp % MOD;
21             carry = temp / MOD;
22         }
23         while(carry) {
24             result[i][current_length++] = carry % MOD;
25             carry /= MOD;
26         }
27         digit_count[i] = current_length;
28     }
29 }
30 
31 inline void display_digits(int num) {
32     putchar(num / 100000 % 10 + '0');
33     putchar(num / 10000 % 10 + '0');
34     putchar(num / 1000 % 10 + '0');
35     putchar(num / 100 % 10 + '0');
36     putchar(num / 10 % 10 + '0');
37     putchar(num % 10 + '0');
38 }
39 
40 inline void print_result(int n) {
41     int index = digit_count[n] - 1;
42     const int &first_num = result[n][index];
43     printf("%d",first_num);
44 
45     for(--index; index >= 0; --index)
46         display_digits(result[n][index]);
47     puts("");
48 }
49 
50 int main() {
51     int test_case;
52     initialize();
53     while(~scanf("%d",&test_case))
54         print_result(test_case);
55     return 0;
56 }

出题者的本意可能是希望我们每次读入一个数后实时计算阶乘，而不是预计算所有结果：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cctype>
 5 const int MAX_SIZE = 5002;
 6 
 7 int storage[2][18000];
 8 
 9 inline void compute_factorial(int n) {
10     storage[1][0] = 1;
11     int length = 1;
12     for(int i = 2; i <= n; ++i) {
13         int carry = 0, temp;
14         for(int j = 0; j < length; ++j) {
15             temp = carry + storage[!(i & 1)][j] * i;
16             storage[i & 1][j] = temp % 10;
17             carry = temp / 10;
18         }
19         while(carry) {
20             storage[i & 1][length++] = carry % 10;
21             carry /= 10;
22         }
23     }
24     for(int j = length - 1; j >= 0; --j)
25         putchar(storage[n & 1][j] + '0');
26     puts("");
27 }
28 
29 template <typename T>
30 inline bool read_input(T &x) {
31     x = 0;
32     char ch = getchar();
33     while(!isdigit(ch) && ch != EOF)    ch = getchar();
34     if(ch == EOF)   return 0;
35     while(isdigit(ch)) {
36         x = x * 10 + (ch - '0');
37         ch = getchar();
38     }
39     return 1;
40 }
41 
42 int main() {
43     int input_value;
44     while(read_input(input_value))
45         compute_factorial(input_value);
46     return 0;
47 }