前言

​ 在洛谷上刷题时遇见这么一道题 P1009 阶乘之和 ，题面简单好理解，适合和我一样菜的 OIer。二话不说，我抄起手中一把梭。

​ 提交，Judge，一气呵成。

​ 然而50Pts…

找锅

​ 明显的，程序出了锅。

怀疑并不是缺点。总是疑，而并不下断语，这才是缺点。 ——鲁迅

​ 为什么会 Wa 呢，这是因为数据范围 $n \leq50$ 实际验算确认，unsigned long long最大可储存的阶乘是 $20!$

,当计算 $21!$​ 时，就出现了溢出的错误。

修锅

​ 是时候介绍主角——高精度了。高精度适用于无法直接用类型储存的数值计算，计算方式类似于竖式算法。竖式算法是通过同一位的两数加减乘除后进位的算法。

​ 图源自OI wiki

储存方式

​ 既然不能用一种类型储存，很自然让人想到字符串(string)，因为string可以动态扩容。但其实string的本质也就是一个数组，而高精度需要储存的都是数字，为什么不用整形(int)数组呢？如果用了int，却无法估计最终会有多少位数时，不妨动态扩容，也就是使用vector作为基类。一阵分析后，我们开始用vector。

​ 竖式运算中由最低位向最高位逐步计算，但是不能估计最高位是否可能进位，vector的扩容是向后的，即越后的数越后出现，那么较低位的数就理所应当先出现，这就需要逆序储存到vector。

string s;
vector<int> v;
cin>>s;
for(int i=s.size()-1;i>=0;i--)
	v.push_back(s[i]-'0');

计算方式

加法

vector<int> add(vector<int> &A,vector<int> &B)
{
	if(A.size()<B.size())	return add(B,A);
	vector<int>C;
	int t=0,len=A.size();
	for(int i=0;i<=len;i++)
	{
		t+=A[i];
		if(i<B.size())	t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)	C.push_back(t);
	return C;
}

​ 首先需要判断A和B谁位数更大，这里让A的位数始终大于B。因为A的位数更大，保证每一位加法都可以有A的这一位参与其中，但B就不一定了，正如上例中百位数只有A的9参与了计算。同时在计算每一位的和之后将该值对10取模（模拟进位过程），然后将该值除以10，最后判断最后一位是否需要进位，如果需要就将最后一位加入，最终返回一个vector。

乘法 高精度乘以低精度

vector<int> mul(vector<int> &A,int b)
{
	vector<int>C;
	int t=0;
	for(int i=0;i<A.size()||t;i++)
	{
		if(i<A.size())	t+=A[i]*b;
		C.push_back(t%10);
		t/=10;
	}
	return C;
}

（作者并不会高精度乘以高精度，以后再更）

​ 和加法类似，同样是每一位乘以b之后对10取模（进位）。值得一提的是这条语句i<A.size()||t因为乘法运算进位有可能不止一位，要考虑t不断进位的情况。

代码

​ 有了以上步骤，我们可以很快打出本题代码。

#include <bits/stdc++.h>
using namespace std;
vector<int> a, b, ans;
int n;
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size())
            t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}
vector<int> add(vector<int> &A, vector<int> &B) {
    if (A.size() < B.size())
        return add(B, A);
    vector<int> C;
    int t = 0, len = A.size();
    for (int i = 0; i <= len; i++) {
        t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t)
        C.push_back(t);
    return C;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        a.clear();
        a.push_back(1);
        for (int j = 1; j <= i; j++) {
            b = mul(a, j);
            a = b;
        }
        ans = add(ans, a);
    }
    for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
    return 0;
}

​ 题解到这里就结束了，以下是一些作者的题外话。

题外话

​ 本题是 noip 1999 的题目，当时的竞赛不分普及组和提高组，可以使用的语言包括 basic ，方便好用的 stl 也没有解禁，甚至于整个中国也没有现在如此之多的 OIer 为了理想而奋斗。现如今的 OI 风雨交加，会有很多很多的 OIer 们因为现实不得不退役，但我认为在 OI 赛场上奋力拼搏，勤恳训练的日子会为所有参加竞赛、热爱竞赛的人留下永恒难忘的回忆。