题解 | #n的阶乘#

//递归关系很简单
//主要考虑了大数乘法，将数据存储为字符串并模拟了乘法的进位
//实现了较大数的乘法
//但n>1000时算法执行时间仍会有明显增加
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
using namespace std;

string multi(string str1,string str2)
{
    vector<int>output(str1.length()+str2.length());
    int a,b,c;            //a-十进位 b-百进位 c-千进位
    reverse(str1.begin(),str1.end());
    reverse(str2.begin(),str2.end());
    for(int i=0;i<str1.length();i++)
    {
        for(int j=0;j<str2.length();j++)
        {
            output[i+j] += (str1[i]-'0')*(str2[j]-'0');
        }
    }
    for(int i=0;i<str1.length()+str2.length();i++)
    {
        c=output[i]/1000;
        b=(output[i]/100)%10;
        a=(output[i]/10)%10;
        output[i]%=10;
        if(a != 0)
        {
            output[i+1] += a;
        }
        if(b != 0)
        {
            output[i+2] += b;
        }
        if(c != 0)
        {
            output[i+3] += c;
        }
    }
    stringstream ss;
    string s,outcome;
    copy(output.rbegin(),output.rend(),ostream_iterator<int>(ss,"")); //vector<int>-->string
    s=ss.str();
    int m=0;
    while(s[m]=='0')
    {
        m++;
    }
    outcome=s.substr(m,s.length()); //除去前面多余的0
    return outcome;
}

int main() {
   int n;
   cin>>n;
   vector<string>outcome(n+1);
   outcome[0]="1";
   outcome[1]="1";
   for(int i =2 ;i <= n;i++)
   {
        outcome[i]=multi(to_string(i),outcome[i-1]);
   }
   cout<<outcome[n];
   return 0;
}