当前位置 博文首页 > ApocalypseTq的博客：P1009 [NOIP1998 普及组] 阶乘之和 题解
其实这道题用二维数组做高精会更好理解（也好打一些），奇怪为啥没这么打的（当然啦，有一点点浪费空间（也就2M？））
首先我们发现，求的是1到n所有阶乘的和，而阶乘又有递归写法（n!=(!n*n）)
那么直接用递推一直推到！n，然后再把所有的都相加就可以了（当然是倒序存储）
关于进位：单个数组位置只存一个（其实可以多个）数位，乘了之后做操作的时候只需要判断当前位置是否是该行最后一位，如果是就++，那么它会一直循环到刚好合适为止。
代码如下（拒绝复制，共创和谐CSDN）
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<map>
#include<queue>
using namespace std;
int bor[52][10000];
int n;
int main()
{
bor[0][0]=1;//每行0位是该行长度
bor[0][1]=1;
bor[1][0]=1;
bor[1][1]=1;
cin>>n;
for(int i=2;i<=n;i++)
{
for(int r=1;r<=bor[i-1][0];r++)
bor[i][r]=bor[i-1][r]*i;//求阶乘
bor[i][0]=bor[i-1][0];
for(int k=1;k<=bor[i][0];k++)
{
if(bor[i][k]>9){
if(k==bor[i][0])bor[i][0]++;//用这种方法消除进位的问题
bor[i][k+1]+=bor[i][k]/10;
bor[i][k]%=10;
}
}
}
for(int i=1;i<=n;i++)
for(int r=1;r<=bor[n][0];r++)
bor[n+1][r]+=bor[i][r];//所有的相加
bor[n+1][0]=bor[n][0];
for(int k=1;k<=bor[n+1][0];k++)
{
if(bor[n+1][k]>9){
if(k==bor[n+1][0])bor[n+1][0]++;//同上
bor[n+1][k+1]+=bor[n+1][k]/10;
bor[n+1][k]%=10;
}
}
for(int i=bor[n+1][0];i>0;i--)
cout<<bor[n+1][i];//倒序输出，完成
return ;
}
