阶乘和

题目描述

计算 $S=1!+2!+\dots+n!$ （ $n\le 50$ ），输入正整数 $n$ ，输出精确结果 $S$ 。

输入格式：一个正整数 $n$ 。

输出格式：一个整数 $S$ 。

样例输入：5，样例输出：153。

思路

滚动维护当前阶乘 $f_i=f_{i-1}\times i$ ，再累加到答案中； $n\le 50$ 时结果超过 64 位整数范围，故用数组实现十进制高精度乘与加。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:04
# update_at: 2026-09-29 22:13

import sys
from itertools import accumulate
from operator import mul


def solve() -> None:
    """读入 n，输出 S = 1! + 2! + ... + n! 的精确值。"""
    (n,) = map(int, sys.stdin.buffer.read().split())
    # accumulate(..., mul) 正是 C++ 里的那一步高精乘 a *= i：它依次产出 1!, 2!, ..., n!。
    # Python 的 int 是任意精度、乘法自带进位，所以不必再手写 mul/add 的进位循环。
    print(sum(accumulate(range(1, n + 1), mul)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:18
 * update_at: 2026-10-05 04:18
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int LEN = 200;        // 数组长度，50! 只有 65 位十进制数字，这里留足余量
int fact[LEN], sumv[LEN];   // fact: 当前阶乘；sumv: 当前累加和，均按低位在前存
int lf = 1, ls = 1;         // 两个数的当前有效位数

// 高精度乘单精度：大整数 a（共 len 位）乘以一个小整数 x，结果仍放在 a 中
void mul(int a[], int &len, int x) {
    for (int i = 0; i < len; i++) a[i] *= x;
    int carry = 0;
    for (int i = 0; i < len || carry; i++) {
        if (i >= len) a[len++] = 0;          // 进位产生新位时扩展长度
        a[i] += carry;
        carry = a[i] / 10;
        a[i] %= 10;
    }
}

// 高精度加：把大整数 a 加到 c 上
void add(int c[], int &lc, int a[], int la) {
    if (lc < la) lc = la;    // 结果位数至少取两者较大者
    int carry = 0;
    for (int i = 0; i < lc || carry; i++) {
        if (i >= lc) c[lc++] = 0;            // 进位产生新位
        int t = c[i] + (i < la ? a[i] : 0) + carry;
        c[i] = t % 10;
        carry = t / 10;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    fact[0] = 1;   // 0! = 1，作为滚动起点
    lf = 1;
    sumv[0] = 0;
    ls = 1;

    for (int i = 1; i <= n; i++) {
        mul(fact, lf, i);   // f_i = f_{i-1} * i
        add(sumv, ls, fact, lf); // S_i = S_{i-1} + f_i
    }

    // 从最高位开始输出
    for (int i = ls - 1; i >= 0; i--) cout << sumv[i];
    cout << '\n';

    return 0;
}

目录

题目描述

思路

参考代码