P1009 [NOIP 1998 普及组] 阶乘之和
题目描述
用高精度计算出
S
=
1
!
+
2
!
+
3
!
+
⋯
+
n
!
S = 1! + 2! + 3! + \\cdots + n!
S=1!+2!+3!+⋯+n!（
n
≤
50
n \\le 50
n≤50）。
其中 ! 表示阶乘，定义为
n
!
=
n
×
(
n
−
1
)
×
(
n
−
2
)
×
⋯
×
1
n!=n\\times (n-1)\\times (n-2)\\times \\cdots \\times 1
n!=n×(n−1)×(n−2)×⋯×1。例如，
5
!
=
5
×
4
×
3
×
2
×
1
=
120
5! = 5 \\times 4 \\times 3 \\times 2 \\times 1=120
5!=5×4×3×2×1=120。
输入格式
一个正整数
n
n
n。
输出格式
一个正整数
S
S
S，表示计算结果。
输入输出样例 #1
输入 #1
3
输出 #1
9
说明/提示
【数据范围】
对于
100
%
100 \\%
100% 的数据，
1
≤
n
≤
50
1 \\le n \\le 50
1≤n≤50。
【其他说明】
注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有
n
≤
20
n \\le 20
n≤20，使用书中的代码无法通过本题。
如果希望通过本题，请继续学习第八章高精度的知识。
NOIP1998 普及组 第二题
解析
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
int n; // 计算S(n)
string s = "0";
unordered_map<string, string> mp;
// 高精度乘法(正整数)
string multiplication(const string &a, const string &b) {
// 首先开辟几个数组存a, b, c中的数据
vector<int> aData, bData, cData(a.size() + b.size());
// 将a, b中的字符数据转化成整型数据装入数组中
for (auto it = a.rbegin(); it != a.rend(); it++)
aData.push_back(*it – '0');
for (auto it = b.rbegin(); it != b.rend(); it++)
bData.push_back(*it – '0');
// 开始做乘法 cData[i + j] = aData[i] * bData[j]
for (int i = 0; i < aData.size(); i++) {
for (int j = 0; j < bData.size(); j++) {
cData[i + j] += aData[i] * bData[j];
}
}
// 处理进位
for (int i = 0; i < cData.size(); i++) {
if (cData[i] >= 10) {
cData[i + 1] += cData[i] / 10;
cData[i] %= 10;
}
}
// 然后将cData中的数据按照适合的顺序装入字符串c中
string c;
int rptr = cData.size() – 1;
while (!cData[rptr] && rptr > 0)
rptr—; // 为0就下一个
for (int i = rptr; i >= 0; i—)
c += cData[i] + '0';
return c;
}
// 高精度加法
string addition(const string &a, const string &b) {
if (a == "0") return b;
if (b == "0") return a;
int len = max(a.size(), b.size());
// 先将字符数据转整形存入数组
vector<int> aData, bData, cData(len + 1);
for (auto it = a.rbegin(); it != a.rend(); it++)
aData.push_back(*it – '0');
for (auto it = b.rbegin(); it != b.rend(); it++)
bData.push_back(*it – '0');
// 给aData或bData扩容, 防止越界访问
if (a.size() < b.size())
aData.resize(len);
else
bData.resize(len);
// 计算 a + b = c
for (int i = 0; i < len; i++) {
cData[i] += aData[i] + bData[i];
if (cData[i] >= 10) {
cData[i + 1] += cData[i] / 10;
cData[i] %= 10;
}
}
// 过滤掉高位0
string c;
int rptr = len;
while (!cData[rptr] && rptr > 0)
rptr—;
for (int i = rptr; i >= 0; i—)
c += cData[i] + '0';
return c;
}
// 高精度减法(正整数)
string subtraction(string a, string b) {
string c;
// 先判断大小
if (a.size() < b.size() || (a.size() == b.size() && a < b)) {
swap(a, b);
c += '-';
}
// 讲字符数据转化为整型数据装入容器
int len = max(a.size(), b.size());
vector<int> aData, bData, cData(len);
for (auto it = a.rbegin(); it != a.rend(); it++)
aData.push_back(*it – '0');
for (auto it = b.rbegin(); it != b.rend(); it++)
bData.push_back(*it – '0');
// 数组扩容
if (a.size() < b.size())
aData.resize(len);
else
bData.resize(len);
// a – b = c
for (int i = 0; i < len; i++) {
cData[i] += aData[i] – bData[i];
if (cData[i] < 0) {
// 借位
cData[i] += 10;
cData[i + 1]—;
}
}
// 然后过滤0
int rptr = len – 1;
while (!cData[rptr] && rptr > 0)
rptr—;
for (int i = rptr; i >= 0; i—)
c += cData[i] + '0';
return c;
}
// 求x!
string factorial(string x) {
if (x.size() <= 1 && x[0] – '0' == 0) {
// 只有一位且为0
return mp[x] = "1";
}
if (mp.find(x) != mp.end())
return mp[x];
return mp[x] = multiplication(x, factorial(subtraction(x, "1")));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
// 计算S(n) = 1! + 2! + … + n!
for (int i = 1; i <= n; i++) {
s = addition(s, factorial(to_string(i)));
}
cout << s;
return 0;
}
