P1009 阶乘之和

前言

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

​ 提交,Judge,一气呵成。

​ 然而50Pts…

找锅

​ 明显的,程序出了锅。

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

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

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

修锅

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

​ 图源自OI wiki

储存方式

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

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

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

计算方式

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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。

乘法 高精度乘以低精度

1
2
3
4
5
6
7
8
9
10
11
12
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不断进位的情况。

代码

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

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
#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 赛场上奋力拼搏,勤恳训练的日子会为所有参加竞赛、热爱竞赛的人留下永恒难忘的回忆。

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/02/21/lg1009/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog