Sum of factorials of Luogu p1009 [noip1998 popularization group]

Title Description

Calculate with high precision  S = 1! + 2! + 3! + ⋯+n!（n≤50）.

among  !  It means factorial , Defined as n!=n×(n−1)×(n−2)×2×⋯×1. for example ,5! =5×4×3×2×1=120.

Input format

A positive integer  n.

Output format

A positive integer  S, It means the result of calculation .

I/o sample

Input

3

Output  

9

explain / Tips

【 Data range 】

about 100%  The data of ,1≤n≤50.

【 Other instructions 】

notes ,《 Basic chapter in simple terms 》 Use this question as an example , But its data range is only n≤20, Using the code in the book can't pass this question .

If you want to pass this question , Please continue to learn the knowledge of high precision in Chapter 8 .

Thinking is high precision multiplication + High precision additive , It is to cover the high-precision multiplication template, and then set the high-precision processing template ,b=c=i The factorial .

Don't talk much , Go straight up C++ Code ：

#include<iostream>
#include<cstring>
using namespace std;
int n,a[90],b[90],c[90],f[90],d=0,len_a,len_b=1,len_c=1,len_ans,m=1;
string s;
int main(){
    cin>>n;
    b[0]=1; // initialization 
    for(int i=1;i<=n;i++){ // Calculation i The factorial , It has been calculated i-1 The factorial 
        len_a=0; //i The length of 
        int p=i;
        while(p>0){ // hold i Put in a Array 
            a[len_a++]=p%10;
            p/=10;
        }
        for(int j=0;j<len_a;j++) // Calculation a*b（i*（i-1） The factorial ）, namely i The factorial , If you don't understand, check online , I don't know why? 
            for(int k=0;k<=len_b;k++)
                c[j+k]+=a[j]*b[k];
        for(int j=0;j<len_c;j++) // If you need to carry, carry 
            if(c[j]>9) c[j+1]+=c[j]/10,c[j]%=10;
        if(c[len_c]) len_c++; // See if the highest position should be carried 
        len_ans=len_b,len_b=len_c,m=max(m,len_c); // hold len_b Assign a value to len_ans, modify len_b Value ,m by i The length of the factorial , See if there is a carry 
        for(int k=len_c-1;k>=0;k--) b[k]=c[k]; // hold c Put in b Array , That is, deposit i The factorial , Next cycle b by i-1 The factorial 
        len_c=len_a+len_ans;
        memset(c,0,sizeof(c)); // Zero clearing c Array , Ready to calculate the next factorial 
        for(int j=0;j<m;j++){ // High precision additive , Set the template directly 
            f[j]+=b[j];
            if(f[j]>9) f[j+1]+=f[j]/10,f[j]%=10; // carry , Be careful not to write f[j+1]++,f[j]-=10; Because here wa I got a point 
        }
    }
    while(!f[m]&&m>0) m--; // Remove the first leading zero 
    for(int i=m;i>=0;i--) cout<<f[i]; // Output in reverse order 
    return 0; // A successful conclusion 
}

Last …… Let's go with a compliment ！