高精度
因为c++没有大数类，最大的类型是 UNSIGNED LONG LONG 数值范围只有 \([0,2^{64}-1]\)，没法满足需要，int128似乎不是正统语言中的内容，略。
所以高精度就是解决大数运算的技巧，把数组按位存储，一般从低位到高位。进制无所谓，但是常用10，为了节约复杂度有时会使用压位，即设 \(10^k\) 进制，可以在复杂度优化一个 \((压的位数)\)，但是会遇到运算溢出的问题。
接下来讨论运算：
\(n,m\) 为两个高精数字位数，n为运算符左边的数，m为运算符右边的数
\(p\) 为低精数字，在运算符右边
加: \(O(n+m)\)
减：\(O(n+m)\)
朴素乘: \(O(nm)\) NTT乘：\(O((n+m)\log(n+m))\)
低精乘: \(O(n)\)
低精除：\(O(n)\)
低精取模：\(O(n)\)
模板如下：
const int Base=10;
typedef long long ll;
int r[1<<19];
int G=3,Gi=332748118;
void ntt(vector<ll> &a,int s,int INTT){for(int i=0;i<s;++i)if(i<r[i])swap(a[i],a[r[i]]);for(int len=2;len<=s;len<<=1){ll gn=qpow(INTT==-1?Gi:G,(mod-1)/len,mod);int k=len/2;for(int i=0;i<s;i+=len){ll g=1;for(int j=0;j<k;++j,g=g*gn%mod){ll tmp=a[i+j+k]*g%mod;a[i+j+k]=(a[i+j]-tmp+mod)%mod;a[i+j]=(a[i+j]+tmp)%mod;}}}if(INTT==-1){ll inv=qpow(s,mod-2,mod);for(int i=0;i<s;++i)a[i]=a[i]*inv%mod;}
}
struct Number{vector<ll> a;Number(){a.clear();}Number(int n){while(n){a.emplace_back(n%Base);n/=Base;}}void read(){string s;cin>>s;reverse(s.begin(),s.end());for(int i=0;i<(int)s.size();i+=1){int t=0;for(int j=min((int)s.size(),i+1)-1;j>=i;--j)t=t*10+s[j]-'0';a.emplace_back(t);}}Number operator + (int b){Number C;C.a=a;C.a[0]+=b;for(int i=0;i<(int)a.size();++i){if(C.a[i]>=Base){if(i+1<(int)a.size())C.a[i+1]+=C.a[i]/Base;else C.a.emplace_back(C.a[i]/Base);C.a[i]%=Base;}else break;}return C;}Number operator * (Number b){int n=a.size()-1+b.a.size()-1+1;int s=1;while(s<n)s<<=1;for(int i=0;i<s;++i)r[i]=(r[i>>1]>>1)|((i&1)*(s>>1));vector<ll> A=a,B=b.a;A.resize(s);B.resize(s);ntt(A,s,1);ntt(B,s,1);for(int i=0;i<s;++i)A[i]=A[i]*B[i]%mod;ntt(A,s,-1);Number C;C.a=A;for(int i=0;i<C.a.size()-1;++i){if(C.a[i]>=Base){C.a[i+1]+=C.a[i]/Base;C.a[i]%=Base;}}while(C.a.back()==0)C.a.pop_back();return C;}Number operator / (int b){Number C;C.a.resize(a.size(),0);ll t=0;for(int i=a.size()-1;i>=0;--i){t=t*Base+a[i];C.a[i]=t/b;t%=b;}while(C.a.back()==0)C.a.pop_back();return C;}void print(){if(a.size()==0){puts("0");return;}printf("%lld",a.back());for(int i=a.size()-2;i>=0;--i)printf("%lld",a[i]);puts("");}
};
