FFT喜提80分
查看原帖
FFT喜提80分
1040353
zhangshirui楼主2023/12/31 15:34
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#include <bits/stdc++.h>
using namespace std;

namespace FFT{
	const int MAX = 4e6 + 10;const double PI = acos(-1);struct 
	Complex{
			    double x, y;
			    Complex(){x=y=0;}
			    Complex(double x,double y){
			        this->x = x;
			        this->y = y;
			    }
			}a[MAX], b[MAX];
			Complex operator+(Complex a, Complex b) { return Complex(a.x + b.x, a.y + b.y); }
			Complex operator-(Complex a, Complex b) { return Complex(a.x - b.x, a.y - b.y); }
			Complex operator*(Complex a, Complex b) { return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
			
	class FFT_type{	
		
		
		
		void fft(int n,Complex * a){
		    if(n<=1)
		        return ;
		    int mid = n >> 1;
		    Complex a1[mid], a2[mid];
		    for (int i = 0; i < mid;i++){
		        a1[i] = a[i << 1];
		        a2[i] = a[(i << 1) + 1];
		    }
		    fft(mid, a1);
		    fft(mid, a2);
		    Complex w1(cos(PI/mid),sin(PI/mid)),w(1,0),x;
		    for (int i = 0; i < mid;i++){
		        x = w * a2[i];
		        a[i] = a1[i] + x;
		        a[i + mid] = a1[i] - x;
		        w =w* w1;
		    }
		}
		void ifft(int n,Complex * a){
		    if(n<=1)
		        return ;
		    int mid = n >> 1;
		    Complex a1[mid], a2[mid];
		    for (int i = 0; i < mid;i++){
		        a1[i] = a[i << 1];
		        a2[i] = a[(i<<1) + 1];
		    }
		    ifft(mid, a1);
		    ifft(mid, a2);
		    Complex w1(cos(PI/mid),-sin(PI/mid)),w(1,0),x;
		    for (int i = 0; i < mid;i++){
		        x = w * a2[i];
		        a[i] = a1[i] + x;
		        a[i + mid] = a1[i] -x;
		        w =w*w1;
		    }
		    
		}
		public:
			string operator()(string aa,string bb){
				int n, m;
				n=aa.size()-1;
				for (int i = 0; i <=n;i++){
				    a[i].x=aa[i]-'0';
				}
				m=bb.size()-1;
			    for (int i = 0; i <=m;i++){
			        b[i].x=bb[i]-'0';
			    }
			    int k = 1;
			    while(k<=n+m)
			        k <<= 1;
			    fft(k, a);
			    fft(k, b);
			    for (int i = 0; i <= k; i++){
			        a[i] = a[i] * b[i];
			    }
			    ifft(k, a);
			    string re;
			    long long sss=0;
			    vector<long long> re2;
			    for (int i = 0; i <=(n+m);i++){
			        sss=(long long)(a[i].x / k + 0.5);
			        re2.push_back(sss);
			    }
			    int kkk=re2.size();
			    for(int i=0;i<kkk/2;i++){
					swap(re2[i],re2[kkk-i-1]);
				}
				
				
				if(re2.size()==0)re2.push_back(0);
						for(int i=0;i<(int)re2.size()-1;i++){
							if(re2[i]>=10){
								re2[i+1]+=(re2[i]/10);
								re2[i]%=10;
							}
						}
						for(int i=0;i<(int)re2.size()-1;i++){
							while(re2[i]<0){
								re2[i+1]--;
								re2[i]+=10;
							}
						}
						while(re2.back()>=10){
							re2.push_back(re2.back()/10);
							re2[re2.size()-2]%=10;
						}
				kkk=re2.size();
							    for(int i=0;i<kkk/2;i++){
									swap(re2[i],re2[kkk-i-1]);
								}
				for(int i=0;i<kkk;i++){
					re+=(re2[i]+'0');
				}
			    return re;
			}
	};
}
class high_int{
	vector<int> num_s;
	bool is_bad=0;
	void ok_down(){
		
		for(int i=num_s.size()-1;i>=0;i--){
			if(num_s[i]==0)num_s.pop_back();
			else return;
		}
	}
	void ok_up(){
		if(num_s.size()==0)num_s.push_back(0);
		for(int i=0;i<(int)num_s.size()-1;i++){
			if(num_s[i]>=10){
				num_s[i+1]+=(num_s[i]/10);
				num_s[i]%=10;
			}
		}
		for(int i=0;i<(int)num_s.size()-1;i++){
			while(num_s[i]<0){
				num_s[i+1]--;
				num_s[i]+=10;
			}
		}
		while(num_s.back()>=10){
			num_s.push_back(num_s.back()/10);
			num_s[num_s.size()-2]%=10;
		}
	} 
	
	
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	

	
	
	
	
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
	
	
	
	
	
	public:
		high_int(int a=0){
			if(a<0){
				a=-a;
				is_bad=1;
			}
			num_s.push_back(a);
			ok_up();
		}
		high_int(const high_int& a){
			num_s=a.num_s;
			is_bad=a.is_bad;
		}
		high_int(const string a){
			for(int i=a.size()-1;i>=0;i--){
				num_s.push_back(a[i]-'0');
			}
		}
		void write(){
			for(int i=num_s.size()-1;i>=0;i--)putchar(num_s[i]+'0');
			if(num_s.size()==0)putchar('0');
		}
		void read()
		{
			is_bad=0;num_s.clear();
		    char ch=getchar();
		    while(ch<'0'||ch>'9'){if(ch=='-')is_bad=!is_bad;ch=getchar();}
		    while(ch>='0' && ch<='9')num_s.push_back(ch-'0'),ch=getchar();
		    long long len=num_s.size()/2;
		    for(int i=0;i<len;i++){
				swap(num_s[i],num_s[num_s.size()-i-1]);
			}
		    return ;
		}
		high_int operator+(const high_int& a){
			high_int b(a);
			b+=*this;
			return b;
		}
		high_int& operator+=(high_int a){
			num_s.resize(max(num_s.size(),a.num_s.size()));
			a.num_s.resize(num_s.size());
			for(int i=0;i<(int)num_s.size();i++){
				num_s[i]+=a.num_s[i]; 
			}
			ok_up();
			ok_down();
			return *this;
		}
		high_int operator-(){
			high_int b(*this);b.is_bad=!b.is_bad;
			return b;
		}
		high_int operator-(const high_int& a){
			high_int b(*this);
			b-=a;
			return b;
		}
		high_int& operator-=(const high_int& a){
			num_s.resize(max(num_s.size(),a.num_s.size()));
			for(int i=0;i<min((int)num_s.size(),(int)a.num_s.size());i++){
				num_s[i]-=a.num_s[i]; 
			}
			
			ok_up();
			ok_down();
			return *this;
		}
		operator string(){
					string b;
					for(int i=num_s.size()-1;i>=0;i--)b+=char(num_s[i]+'0');
					return b;
				}
		
		
		
		
		
};
high_int fast_mul(high_int a,high_int b){
	return 	high_int(FFT::FFT_type()(a,b));
}
istream& operator>>(istream& in,high_int& b){
	b.read();
	return in;
}
ostream& operator<<(ostream& out,high_int b){
	b.write();
	return out;
}
int main(){
	high_int a,b;
	cin>>a>>b;
	cout<<fast_mul(a,b);
}
2023/12/31 15:34
加载中...