题目分析

题意简述

本题通过预先计算并存储一系列数值到二维数组 res 中，然后根据输入的整数 $n$，输出数组 res 中对应 $n$ 的数值。当输入的 $n$ 为 $-1$ 时，程序结束。输出格式为 “N=n: 数值”，其中数值由数组 res 中 $n$ 对应的最高位以及其他位组成，其他位以四位一组的形式输出，不足四位的前面补 $0$。

输入

• 多组测试用例，每组为一个整数 $n$。
• 当输入的整数 $n$ 为 $-1$ 时，程序终止。

输出

对于每组输入（除 $-1$ 外），输出格式为 “N=n: 数值”，数值由数组 res 中 $n$ 对应的最高位以及其他位组成，其他位以四位一组的形式输出，不足四位的前面补 $0$。

解题思路

数组初始化

定义二维数组 res[MAXN][MAXM] 用于存储计算结果，数组 msb[MAXN] 用于记录 res[i][] 中最高位的位置。初始化 res[3][0] = 4 和 msb[3] = 0，表示预先设定的初始状态。

递推计算

通过循环 for (i = 3; i < MAXN - 2; ++i) 进行递推计算：

1. 内层循环 for (j = 0; j <= msb[i]; ++j) 对 res[i][] 中的每一位进行处理，将 res[i][j] 乘以 $i$ 后累加到 res[i + 1][j] 中，同时处理进位，将 res[i + 1][j] 除以 BASE 的结果累加到 res[i + 1][j + 1] 中，res[i + 1][j] 取模 BASE。
2. 根据 res[i + 1][msb[i] + 1] 是否为 $0$ 来更新 msb[i + 1] 的值，如果 res[i + 1][msb[i] + 1] 不为 $0$，则 msb[i + 1] = msb[i] + 1，否则 msb[i + 1] = msb[i]。

输入处理与结果输出

使用 while (scanf("%d", &n) != EOF && n != -1) 循环读取输入的整数 $n$，当 $n$ 为 $-1$ 时结束循环。对于每个输入的 $n$，先输出 “N=n:”，然后输出 res[n][msb[n]] 作为最高位，再通过循环 for (i = msb[n] - 1; i >= 0; --i) 以四位一组的形式输出 res[n][i]，不足四位的前面补 $0$。

代码实现

#include <stdio.h>
#define MAXN 205
#define MAXM 1050
#define BASE 10000
int res[MAXN][MAXM] = {0}, msb[MAXN] = {0}; //2*(i-1)!保存在res[i][]中，msb[i]为2*(i-1)!最高位的位置

int main() {
    int n, i, j;
    res[3][0] = 4;
    msb[3] = 0;
    for (i = 3; i < MAXN - 2; ++i) {
        for (j = 0; j <= msb[i]; ++j) {
            res[i + 1][j] += res[i][j] * i;
            res[i + 1][j + 1] += res[i + 1][j] / BASE;
            res[i + 1][j] %= BASE;
        }
        if (res[i + 1][msb[i] + 1])
            msb[i + 1] = msb[i] + 1;
        else
            msb[i + 1] = msb[i];
    }

    while (scanf("%d", &n) != EOF && n != -1) {
        printf("N=%d:\n%d", n, res[n][msb[n]]);
        for (i = msb[n] - 1; i >= 0; --i)
            printf("%04d", res[n][i]);
        printf("\n");
    }

    return 0;
}

代码说明

1. 宏定义：使用 #define 定义了三个宏 MAXN、MAXM 和 BASE，分别表示数组的大小和进制基数。
2. 数组定义：定义了二维数组 res 和一维数组 msb，并对其进行了注释说明。
3. 初始化：对 res[3][0] 和 msb[3] 进行初始化。
4. 递推计算循环：外层循环控制计算的轮数，内层循环处理每一位的计算和进位。
5. 最高位位置更新：根据 res[i + 1][msb[i] + 1] 的值更新 msb[i + 1]。
6. 输入处理与输出循环：通过 while 循环读取输入的整数 $n$，根据 $n$ 输出相应的结果，输出时按照特定格式进行。