[NOIP 1998 普及组] 阶乘之和

知识点

高精度、阶乘、加法、乘法

解题思路

用逆序十进制数组保存当前阶乘fact和阶乘和sum。第k步将fact乘k并处理进位，再将fact加进sum。最后从最高位向最低位输出sum。

正确性说明

初始fact=1、sum=0。第k步乘法得到k!，加法使sum从前k-1个阶乘的和变为前k个阶乘的和；逐位运算与十进制进位规则相同，因此迭代至n时结果正确。

易错点

n可到50，普通long long会溢出；乘法和加法都要处理最终进位；每个新阶乘必须加入总和。

复杂度

设D为n!的十进制位数，时间O(nD)，空间O(D)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;vector<int> fact(1,1),sum(1,0);
    for(int k=1;k<=n;++k){
        int carry=0;
        for(int &v:fact){int x=v*k+carry;v=x%10;carry=x/10;}
        while(carry){fact.push_back(carry%10);carry/=10;}
        sum.resize(max(sum.size(),fact.size()),0);carry=0;
        for(size_t i=0;i<sum.size();++i){int x=sum[i]+(i<fact.size()?fact[i]:0)+carry;sum[i]=x%10;carry=x/10;}
        if(carry) sum.push_back(carry);
    }
    for(auto it=sum.rbegin();it!=sum.rend();++it) cout<<*it;
    cout<<'\n';
}