题目链接

HIGH15 计算阶乘

题目描述

给定 个正整数 ，请你计算 的值并输出。

输入描述: 第一行输入一个整数 () 表示测试数据数量。 接下来 行，每行输入一个整数 ()。

输出描述: 输出共 行，其中第 行输出 的结果。

解题思路

这道题虽然是计算阶乘，但由于 的范围可以达到 ，且有多组测试数据，因此不能对每个 都进行一次 的循环计算，否则总时间复杂度会达到 (即 )，会严重超时。

正确的解法是 预处理 + 查表。

  1. 预处理： 我们可以创建一个大小为 的数组（例如 factorials），用来存储从 到 的所有阶乘结果对 取模的值。 这个数组可以通过递推来填充：

    这个预处理过程的时间复杂度是 ，其中 是 的最大值 。

  2. 查表： 在预处理完成后，我们得到了所有可能需要的阶乘值。对于接下来的 组查询，每当输入一个 ，我们不再需要计算，而是直接从 factorials 数组中返回 factorials[n] 的值即可。每次查询的时间复杂度是 。

整体复杂度：

  • 时间复杂度：，即预处理的时间加上 次查询的时间。这远远优于 。
  • 空间复杂度：，用于存储预处理的阶乘数组。

代码

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;
const int MAX_N = 1000000;
long long factorials[MAX_N + 1];

void precompute_factorials() {
    factorials[0] = 1;
    for (int i = 1; i <= MAX_N; ++i) {
        factorials[i] = (factorials[i - 1] * i) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute_factorials();
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << factorials[n] << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;
    static final int MAX_N = 1000000;
    static long[] factorials = new long[MAX_N + 1];

    static {
        factorials[0] = 1;
        for (int i = 1; i <= MAX_N; i++) {
            factorials[i] = (factorials[i - 1] * i) % MOD;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            System.out.println(factorials[n]);
        }
    }
}

MOD = 1000000007
MAX_N = 1000000

# Pre-calculation
factorials = [1] * (MAX_N + 1)
for i in range(2, MAX_N + 1):
    factorials[i] = (factorials[i-1] * i) % MOD

T = int(input())
for _ in range(T):
    n = int(input())
    print(factorials[n])

算法及复杂度

  • 算法：预处理 / 打表
  • 时间复杂度：，其中 是 的最大值 ()， 是测试用例数。
  • 空间复杂度：，用于存储预计算的阶乘表。