RT,压不来位，求救（应该是vector<unsigned long long>压9位，就不考虑负数了，顺便帮忙求一下常数使得$|s|$在什么样的情况下$O(\frac{n^2}{81})$的逐位相乘更快，直接优化到极致）

const double PI=acos(-1.0);
void FFT(vector<complex<double>>&a,bool inv){
    int n=a.size();
    if(n==1)return;
    vector<complex<double>>a0(n/2),a1(n/2);
    for(int i=0,j=0;i<n;i+=2,j++){
        a0[j]=a[i];
        a1[j]=a[i+1];
    }
    FFT(a0,inv);FFT(a1,inv);
    double angle=2*PI/n*(inv?-1:1);
    complex<double>w(1),wn(cos(angle),sin(angle));
    for(int i=0;i<n/2;i++){
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        w*=wn;
    }
}
vector<int>to_vec(string s){
	vector<int>res;
	for(int i=s.size()-1;i>=0;i--)
		res.push_back(s[i]-'0');
	return res;
}
string to_str(vector<int>a){
	string res;
	for(int i=a.size()-1;i>=0;i--)
		res+=to_string(a[i]);
	return res;
}
string _mul(string s1,string s2){
	vector<int>a=to_vec(s1),b=to_vec(s2);
    int n=1;
    while(n<a.size()+b.size())n*=2;
    a.resize(n),b.resize(n);
    vector<complex<double>>c(n),d(n);
    for(int i=0;i<n;i++){
        c[i]=complex<double>(a[i],0);
        d[i]=complex<double>(b[i],0);
    }
    FFT(c,false);FFT(d,false);
    for(int i=0;i<n;i++)c[i]*=d[i];FFT(c,true);
    vector<int>res(n);
    for(int i=0;i<n;i++)
        res[i]=(int)(c[i].real()/n+0.5);
    int carry=0;
    for(int i=0;i<n;i++){
    	res[i]+=carry;
    	carry=res[i]/10;
    	res[i]%=10;
	}
	while(res.size()>1&&res.back()==0)
    	res.pop_back();
	return to_str(res);
}