高精度

对于大数，unsigned long long int可能也无法表示

需要用数组，字符串等才能表示

例题：

洛谷：阶乘之和

思路：

用unsigned long long int，只能过50%用例

所以必须用高精度解决

我这里采用vector表示大数，从左到右，是低位到高位（也即与正常的数，反转了一下）

对于加法：注意进位，模拟即可

对于乘法：

也可以模拟，将每一位相乘的结果加起来即可，时间复杂度

还可以用数学的方法：可以证明两个数相乘，长度分别为m，n（均大于0），他们

通过找规律可以发现：

**比如123*456，对于索引i，j（第i、j位）**

如果索引从高位开始，num1[i] * num2[j]的本位在i+j+1，进位在i+j处，算出的结果为56088

如果从低位开始，num1[i] * num2[j]的本位在i+j，进位在i+j+1处，算出来就是反转的，结果为88065

由于我这里是反着存储大数，索引从低位开始，得到的结果是反转的，刚好也符合反转存储，也就是不需要改变结果顺序

如果是正向存储的字符串，索引是从高位开始，结果正向，也不需要改变结果顺序

也就是，该乘法对于索引的不同起始，

因为正常进位，高位在左边，所以索引要-1，反向存储的话，高位在右边，进位索引+1

注意：别忘了去掉前导0

优化的乘法时间复杂度为：

代码：

//万能头文件
#include<bits/stdc++.h>
using namespace std;

class BigInt{

    public:
        vector<int> num;

        BigInt(){}

        BigInt(int n){
            if(n<0){
                cout << "错误！" << endl;
            }
            while(n){
                this->num.push_back(n % 10);
                n /= 10;
            }
        }

    void plus_int(unsigned long long int t){
        vector<int> &arr = this->num;
        int pos = 0;
        while(t){
            int num = t % 10;
            t /= 10;
            if(pos >= arr.size()){
                arr.push_back(0);
            }
            arr[pos] += num;
            if(arr[pos] >= 10){
                arr[pos] -= 10;
                if(pos+1 >= arr.size()){
                    arr.push_back(1);
                }else arr[pos + 1] += 1;
            }
            pos++;
        }
    }

    void plus_BigInt(BigInt b){
        int pos = 0;
        while(pos < b.num.size()){
            vector<int> & arr = this->num;
            if(pos >= arr.size()){
                arr.push_back(0);
            }
            arr[pos] += b.num[pos];
            if(arr[pos] >= 10){
                arr[pos] -= 10;
                if(pos+1 >= arr.size()){
                    arr.push_back(1);
                }else arr[pos + 1] += 1;
            }
            pos++;
        }
    }
    //把b当一个整体（只适合b位数较小）
    void mul_int(int b){
        vector<int> & arr= this->num;
        int carry = 0;
        for (int i = 0; i < arr.size();i++) {
            arr[i] *= b;
            arr[i] += carry;
            carry = arr[i] / 10;
            arr[i] %= 10;
        }
        int pos = arr.size();
        while(carry != 0){
            arr.push_back(carry);
            carry = arr[pos] / 10;
            arr[pos] %= 10;
            pos++;
        }
    }
    //竖式乘法优化版（推荐）
    void mul_BigInt(BigInt& b){
        vector<int> & arr= b.num;
        //最大长度
        int N = num.size() + arr.size();
        vector<int> tmp(N, 0);
        // i*j本位为第i+j位，进位在i+j+1位
        for (int i = 0; i < num.size(); i++) {
            for (int j = 0; j < arr.size(); j++) {
                tmp[i + j] += num[i] * arr[j];
                tmp[i + j + 1] += tmp[i + j] / 10;
                tmp[i + j] %= 10;
            }
        }
        if(tmp[N-1] == 0){
            tmp.pop_back();
        }
        this->num = tmp;
    }



    void disp(){
        for (int i = num.size()-1; i >= 0; i--) {
            cout << num[i];
        }
        cout << endl;
    }
    

};



int main(){
    int n;
    cin >> n;

    BigInt res(1),tmp(1);

    for (int i = 2; i <= n;i++){
        //方法1
        //tmp.mul_int(i);
        //方法2
        BigInt t(i);
        tmp.mul_BigInt(t);
        res.plus_BigInt(tmp);
    }

    res.disp();

    return 0;
}

这里没有写模拟的竖式乘法，详细的模拟可以参考下面的官方题解

类似的题：leetcode：字符串相乘

里面还提到可以采用fft的方法