题目链接

计算阶乘

题目描述

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

解题思路

本题要求在多组查询中计算阶乘对一个大质数取模的结果。

  1. 分析问题

    • 多组查询：题目包含 组查询，其中 的最大值为 。
    • 数据范围：每次查询的 最大可达 。
    • 取模运算：由于阶乘结果非常大，题目要求对 取模。

  2. 朴素解法及其问题

    最直观的想法是，对于每次查询 ，都写一个循环从 累乘到 ，并在每一步都进行取模操作。这种方法单次查询的时间复杂度为 。

    然而，在最坏情况下（），总的计算量将达到 级别，这会远远超出常规的运行时间限制（通常是 级别），导致超时。

  3. 预处理优化

    考虑到所有查询的 都在一个固定的范围内（），我们可以采用预处理（打表）的方法来优化。

    具体思路如下：

    • 在程序开始时，我们创建一个数组（例如 factorials），大小为 。
    • 我们用一次循环，计算出从 到 的所有阶乘模 的值，并存入这个数组中。
      • 递推关系为：
    • 这个预处理过程的时间复杂度为 ，其中 。
    • 预处理完成后，对于接下来的 组查询，无论查询哪个 ，我们都可以通过访问数组 factorials[n] 在 的时间内直接得到答案。

    通过这种方式，总的时间复杂度从 优化到了 ，可以轻松通过本题。

代码

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;
const int MAX_N = 1000001;
vector<long long> factorials(MAX_N);

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

int main() {
    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 = 1000001;
    static long[] factorials = new long[MAX_N];

    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 = 1000001
factorials = [0] * MAX_N

def precompute_factorials():
    factorials[0] = 1
    for i in range(1, MAX_N):
        factorials[i] = (factorials[i - 1] * i) % MOD

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

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：预处理 / 动态规划

  • 时间复杂度：。其中 是 的最大可能值（），用于预处理。 是查询的次数。

  • 空间复杂度：。我们需要一个数组来存储所有预计算出的阶乘值。