P1009 [NOIP 1998 普及组] 阶乘之和

题目描述

用高精度计算出 （）。

其中 ! 表示阶乘，定义为 。例如，。

输入格式

一个正整数 。

输出格式

一个正整数 ，表示计算结果。

输入输出样例 #1

输入 #1

3

输出 #1

9

说明/提示

【数据范围】

对于 的数据，。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 ，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

NOIP1998 普及组 第二题

AC代码（高精乘+高精加）

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
#define lowbit(x) = ((x) & -(x))
#define rep_0(a, b, c) for (int a = b; a < c; a++)
#define rep_1(a, b, c) for (int a = b; a <= c; a++)
#define per(a, b, c) for (int a = b; a >= c; a--)
using namespace std;
string solve_a_add_b(string a, string b)//高精加
{
    vector<int> ans;
    stack<int> ans_a;
    stack<int> ans_b;
    for (int i = 0; a[i]; i++)
    {
        ans_a.push(a[i] - 48);
    }
    for (int i = 0; b[i]; i++)
    {
        ans_b.push(b[i] - 48);
    }
    while (!ans_a.empty() && !ans_b.empty())
    {
        int temp_a, temp_b;
        temp_a = ans_a.top();
        ans_a.pop();
        temp_b = ans_b.top();
        ans_b.pop();
        ans.push_back(temp_a + temp_b);
    }
    if (!ans_a.empty())
    {
        while (!ans_a.empty())
        {
            ans.push_back(ans_a.top());
            ans_a.pop();
        }
    }
    else if (!ans_b.empty())
    {
        while (!ans_b.empty())
        {
            ans.push_back(ans_b.top());
            ans_b.pop();
        }
    }
    for (int p = 0; p < ans.size() - 1; p++)
    {

        if (ans[p] >= 10)
        {
            ans[p + 1] += ans[p] / 10;
            ans[p] = ans[p] % 10;
        }
    }
    while (ans.back() >= 10)
    {
        int num = ans.back();
        ans.push_back(num / 10);
        ans[ans.size() - 2] = num % 10;
    }
    string s = "";

    for (int i = ans.size() - 1; i >= 0; i--)
    {
        s += to_string(ans[i]);
    }
    return s;
}
string solve_a_cul_b(string s_a, string s_b)//高精乘
{
    vector<int> a;
    vector<int> b;

    int lena = s_a.size();
    int lenb = s_b.size();
    rep_0(i, 0, lena)
    {
        a.push_back(s_a[lena - i - 1] - '0');
    }
    rep_0(i, 0, lenb)
    {
        b.push_back(s_b[lenb - i - 1] - '0');
    }
    vector<int> ans(lena + lenb, 0);
    for (int i = 0; i < lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            ans[i + j] += a[i] * b[j];
        }
    }
    rep_0(i, 0, lena + lenb)
    {
        if (ans[i] > 9)
        {
            ans[i + 1] += ans[i] / 10;
            ans[i] = ans[i] % 10;
        }
    }
    int lenans = ans.size() - 1;
    per(i, ans.size() - 1, 0)
    {
        if (ans[i] == 0)
        {
            lenans--;
        }
        else
        {
            break;
        }
    }
    string s = "";
    if (lenans != -1)
    {
        per(p, lenans, 0) { s += to_string(ans[p]); }
    }
    else
    {
        s = "0";
    }
    return s;
}

int main()//相当于字符串之间的运算
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s_z = "0";
    for (int i = n; i >= 1; i--)
    {
        int temp = i;
        string s = "1";
        while (temp > 0)
        {
            string temp_s = to_string(temp);
            s = solve_a_cul_b(s, temp_s);
            temp--;
        }
        s_z = solve_a_add_b(s_z, s);
    }
    cout << s_z;

    return 0;
}