FFT求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const double PI=acos(-1);
int n;
struct comp{
	double r,i;
	comp(){
		r=0,i=0;
	}
	comp(double real,double imag):r(real),i(imag){}
};
comp operator +(comp a,comp b){
	return comp(a.r+b.r,a.i+b.i);
}
comp operator -(comp a,comp b){
	return comp(a.r-b.r,a.i-b.i);
}
comp operator *(comp a,comp b){
	return comp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
}
int rev[3000005],len,lim=1;
comp a[3000005],b[3000005];
string s1,s2;
void FFT(comp *a,int op){
    for(int i=0;i<lim;i++){
        if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int mid=1; mid<lim; mid<<=1){
        comp wn(cos(PI/mid),op*sin(PI/mid));
        for(int r=mid<<1,j=0; j<lim; j+=r){
            comp w(1,0);
            for(int l=0; l<mid; l++,w=w*wn){
                comp x=a[j+l],y=w*a[j+mid+l];
                a[j+l]=x+y; a[j+mid+l]=x-y;
            }
        }
    }
}
void work(string s1,string s2,string &ans){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(rev,0,sizeof(rev));
	ans="";
	int n1=s1.size()-1;
	for(int i=0;i<=n1;i++)a[n1-i].r=s1[i]-'0';
	int n2=s2.size()-1;
	for(int i=0;i<=n2;i++)b[n2-i].r=s2[i]-'0';
	while(lim<=n1+n2){
		lim<<=1;len++;
	}
	for(int i=0;i<lim;i++){
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
	}
	FFT(a,1);FFT(b,1);
	for(int i=0;i<=lim;i++)a[i]=a[i]*b[i];
	FFT(a,-1);
	memset(rev,0,sizeof(rev));
	for(int i=0;i<=n1+n2+1;i++){
		rev[i]=a[i].r/lim+0.5;
	}
	for(int i=0;i<=n1+n2;i++){
		rev[i+1]+=rev[i]/10;
		rev[i]%=10;
	}
	lim=n1+n2+1;
	while(rev[lim]){
		rev[lim+1]+=rev[lim]/10;
		rev[lim]%=10;
		lim++;
	}
	for(int i=lim-1;i>=0;i--)ans+='0'+rev[i];
}
string x,y,ans;
signed main(){
	cin>>n;
	if(n==1){
		puts("1");
		return 0;
	}
	if(n==2){
		puts("2");
		return 0;
	}
	while(1){
		if(n==0)break;
		if(n%3==0){
			x+="3";n-=3;
		}else if(n%3==2){
			x+="2";n-=2;
		}else{
			x+="4";n-=4;
		}
	}
	ans="1";
	for(int i=0;i<x.size();i++){
		string z=ans;
		y=x[i];
		work(z,y,ans);
	}
	int len=ans.size();
	cout<<len<<endl;
	for(int i=0;i<min(99ll,len);i++)cout<<ans[i];
	return 0;
}