BISHI63　计算阶乘¶

简单通过率 35.28%python3样例通过牛客 AC

牛客原题　源码

讲解章节：内置函数速查、高精度与大整数、基础数学与递推

一句话

T 组询问，每组求 n! mod (1e9+7)。

解题思路¶

这题考什么¶

「多组询问 + 同一个上界」的经典套路：预处理阶乘前缀表，O(1) 回答。 n! 的前缀性质天然适合打表 —— fact[i] 只比 fact[i-1] 多乘一个 i，一张表就把 T 组询问的重复计算全部摊掉。

数据规模与复杂度¶

T <= 1e3，n <= 1e6。两条被否决的朴素路线先说清楚：

每组询问都从 1 乘到 n，是 O(T * n) = 1e9 次乘法取模，这条路在 Python 下必然超时；
先算出精确的大整数 1e6!（约 550 万位）再取模，大整数乘法的代价随位数增长，时间和内存都撑不住。

本解法预处理一次 fact[0..maxn] 是 O(maxn) = 1e6 次「乘法 + 取模」，之后每次询问 O(1) 查表，总复杂度 O(maxn + T)， CPython 下即可通过，不需要换 PyPy3。进一步的小优化：先把所有询问读进来取 max，只预处理到实际用得到的最大 n，样例里 n = 1，递推循环一轮都不跑。

坑在哪¶

一定要先读完全部输入再决定表的长度，所以用整块读取 + 游标；边读边答就没法知道最大的 n 是多少，只能按上界 1e6 建满表；
递推 fact[i] = fact[i-1] * i % MOD，每步都要取模。少了这个 % 就退化成上面那条大整数路线，数值一路膨胀到百万位；
表的下标要开到 m 而不是 m-1，fact 的长度是 m+1；递推从 2 起步，fact[0] = fact[1] = 1 由初始化的全 1 直接给出；
输出攒进列表最后一次性写出，T 到 1e3 时逐行 print 的开销已经可见。

样例复核¶

T = 1、n = 1：m = 1，fact = [1, 1]，range(2, 2) 是空循环，直接查 fact[1] = 1，输出 1 ✓。

模运算与阶乘见 85-基础数学与递推，大整数的代价见 22-高精度与大整数。

参考实现¶

solutions/BISHI63.py
import sys

MOD = 1000000007


def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    ns = [int(x) for x in data[1:t + 1]]
    m = max(ns) if ns else 0             # 只建到实际用得到的最大 n，多余的不算

    fact = [1] * (m + 1)                 # 前缀阶乘表，只建一次，随后 O(1) 查表
    for i in range(2, m + 1):            # 从 2 起步：0! = 1! = 1 已由初始值给出
        fact[i] = fact[i - 1] * i % MOD  # 每步取模，把数值钉死在 30 位以内

    # 攒成一整块再写出，避免 T 次系统调用
    sys.stdout.write("\n".join(str(fact[n]) for n in ns) + "\n")


main()

BISHI63 计算阶乘¶