关于压位FFT
查看原帖
关于压位FFT
484719
XSJProgrammer楼主2023/10/30 18:21
#ifndef _BIGINT
#define _BIGINT
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cmath>
#include<complex>
#define BASETYPE long long
#define BASE (long long)100
#define WIDTH 2
using namespace std;

namespace InOrdered{
	inline long long abs(long long a){
			if(a>=0)return a;
			else return -a;
		}
		inline vector<BASETYPE> Str_Vec(string a_){
			vector<BASETYPE>a;
			string a1=a_;
			reverse(a1.begin(),a1.end());
			while(a1.length()%WIDTH!=0)a1+='0';
			reverse(a1.begin(),a1.end());
			for(register long long i=0;i<a1.length();i+=WIDTH){
				long long temp=0;
				for(register int j=0;j<WIDTH;j++){
					temp*=10;
					temp+=a1[i+j]-'0';
				}
				a.push_back(temp);
			}
			return a;
		}
		
		inline bool is_bigger(vector<BASETYPE>a,vector<BASETYPE>b){
			if(a.size()>b.size())return 1;
			else if(a.size()<b.size() || a==b)return 0;
			else{
				for(register long long i=0;i<a.size();i++){
					if(a[i]>b[i])return 1;
					if(a[i]<b[i])return 0;
				}
			}
			return 0;
		}
		
		
		inline vector<BASETYPE> add(vector<BASETYPE> a_,vector<BASETYPE> b_){
			vector<BASETYPE>a=a_,b=b_;
			long long i;
			if(a.size()<b.size()){
				while(a.size()<b.size())a.insert(a.begin(),0);
			}
			if(b.size()<a.size()){
				while(b.size()<a.size())b.insert(b.begin(),0);
			}
			for(i=a.size()-1;i>=0;i--){
				a[i]+=b[i];
				if(i==0 && a[0]>=BASE){
					a.insert(a.begin(),0);
					a[0]=a[1]/BASE;
					a[1]%=BASE;
				}
				else{
					a[i-1]+=a[i]/BASE;
					a[i]%=BASE;
				}
			}
			return a;
		}
		
		inline vector<BASETYPE> subtract(vector<BASETYPE> a_,vector<BASETYPE> b_){
			vector<BASETYPE>a=a_,b=b_;
			if(a==b){
				vector<BASETYPE>s;
				s.push_back(0);
				return s;
			}
			if(is_bigger(b,a)){
				vector<BASETYPE>c=a;
				a=b;
				b=c;
			}
			if(b.size()<a.size()){
				while(b.size()<a.size())b.insert(b.begin(),0);
			}
			for(register long long i=1;i<=b.size();i++){
				a[a.size()-i]=a[a.size()-i]-b[b.size()-i];
				if(a[a.size()-i]<0){
					a[a.size()-i]+=BASE;
					a[a.size()-i-1]-=1;
				}
			}
			reverse(a.begin(),a.end());
			for(register long long i=0;*(a.end()-1)==0 && a.size()>1;i++)a.pop_back();
			reverse(a.begin(),a.end());
			return a;
		}
		
		inline vector<BASETYPE> vertical(vector<BASETYPE> a_,vector<BASETYPE> b_){
			vector<BASETYPE> a=a_,b=b_;
			vector<BASETYPE>c;
			for(register long long i=0;i<a.size()+b.size();i++)c.push_back(0);
			for(register long long i=a.size()-1;i>=0;i--){
				for(register long long j=b.size()-1;j>=0;j--){
					c[i+j+1]+=a[i]*b[j];
				}
			}
			
			for(register long long i=c.size()-1;i>0;i--){
				c[i-1]+=c[i]/BASE;
				c[i]%=BASE;
			}
			if(c[0]>=BASE){
				c.insert(c.begin(),c[0]/BASE);
				c[0]%=BASE;
			}
			reverse(c.begin(),c.end());
			for(register long long i=0;*(c.end()-1)==0 && c.size()>1;i++)c.pop_back();
			reverse(c.begin(),c.end());
			return c;
		}
		inline long long binary_search(vector<BASETYPE>a,vector<BASETYPE>b){
			long long l=1,r=BASE;
			while(r-l>1){
				int mid=(l+r)/2;
				vector<BASETYPE>m;
				m.push_back(mid);
				vector<BASETYPE>m_;
				m_.push_back(mid+1);
				vector<BASETYPE>nowl=vertical(m,b);
				vector<BASETYPE>nowr=vertical(m_,b);
				if(is_bigger(nowl,a))r=mid;
				else if(is_bigger(a,nowr))l=mid;
				else if(nowr==a)return mid+1;
				else return mid;
			}
			return l;
		}
		inline vector<BASETYPE> divide(vector<BASETYPE> a_,vector<BASETYPE> b_){
			vector<BASETYPE> a=a_,b=b_;
			vector<BASETYPE>n0,n1;
			n0.push_back(0);
			n1.push_back(1);
			if(!is_bigger(a_,b_) and a_!=b_)return n0;
			if(a_==b_)return n1;
			long long p=a.size();
			vector<BASETYPE>now,ans;
			for(register long long i=0;i<a.size();i++){
				now.push_back(a[i]);
				while(now.size()>1 and now[0]==0)now.erase(now.begin());
				if(is_bigger(now,b)){
					long long temp=binary_search(now,b);
					ans.push_back(temp);
					vector<BASETYPE>s;
					s.push_back(temp);
					now=subtract(now,vertical(s,b));
				}
			}
			for(register long long i=ans.size()-1;i>0;i--){
				ans[i-1]+=ans[i]/BASE;
				ans[i]%=BASE;
			}
			if(ans[0]>=BASE){
				ans.insert(ans.begin(),ans[0]/BASE);
				ans[1]%=BASE;
			}
			vector<BASETYPE>mod=subtract(a_,vertical(ans,b_));
			if(is_bigger(mod,b_))ans=add(ans,divide(mod,b_));
			return ans;
		}
}
inline string Vec_Str(vector<BASETYPE>A){
	string c;
	for(register long long i=A.size()-1;i>=0;i--){
		long long k=BASE;
		for(register int j=0;j<WIDTH;j++){
			k/=10;
			c+=(A[i]/k)%10+'0';
		}
	}
	reverse(c.begin(),c.end());
	while(*(c.end()-1)=='0' and c.length()>1)c.erase(c.end()-1);
	reverse(c.begin(),c.end());
	return c;
}
class DivByZero{};
struct BigInt{
	private:
		inline long long abs(long long a){
			if(a>=0)return a;
			else return -a;
		}
		inline vector<BASETYPE> Str_Vec(string a_){
			vector<BASETYPE>a;
			string a1=a_;
			reverse(a1.begin(),a1.end());
			while(a1.length()%WIDTH!=0)a1+='0';
			reverse(a1.begin(),a1.end());
			for(register long long i=0;i<a1.length();i+=WIDTH){
				long long temp=0;
				for(register int j=0;j<WIDTH;j++){
					temp*=10;
					temp+=a1[i+j]-'0';
				}
				a.push_back(temp);
			}
			reverse(a.begin(),a.end());
			return a;
		}
		
		inline bool is_bigger(vector<BASETYPE>a,vector<BASETYPE>b){
			if(a.size()>b.size())return 1;
			else if(a.size()<b.size() || a==b)return 0;
			else{
				for(register long long i=a.size()-1;i>=0;i--){
					if(a[i]>b[i])return 1;
					if(a[i]<b[i])return 0;
				}
			}
			return 0;
		}
		
		
		inline vector<BASETYPE> add(vector<BASETYPE> a,vector<BASETYPE> b){
			while(a.size()<b.size())a.push_back(0);
			while(b.size()<a.size())b.push_back(0);
			for(int i=0;i<a.size();i++)a[i]+=b[i];
			for(int i=0;i<a.size()-1;i++){
				a[i+1]+=a[i]/BASE;
				a[i]%=BASE;
			}
			while(a[a.size()-1]>BASE){
				a.push_back(a[a.size()-1]/BASE);
				a[a.size()-2]%=BASE;
			}
			while(a[a.size()-1]==0)a.pop_back();
			return a;
		}
		
		inline vector<BASETYPE> subtract(vector<BASETYPE> a,vector<BASETYPE> b){
			if(a==b){
				vector<BASETYPE>s;
				s.push_back(0);
				return s;
			}
			if(is_bigger(b,a))swap(a,b);
			while(b.size()<a.size())b.push_back(0);
			for(int i=0;i<a.size();i++)a[i]-=b[i];
			for(int i=0;i<a.size()-1;i++){
				while(a[i]<0){
					a[i]+=BASE;
					a[i+1]--;
				}
			}
			while(a[a.size()-1]==0)a.pop_back();
			return a;
		}
		
		inline vector<BASETYPE> vertical(vector<BASETYPE> a,vector<BASETYPE> b){
			vector<BASETYPE>c;
			for(long long i=0;i<a.size()+b.size();i++)c.push_back(0);
			for(int i=0;i<a.size();i++){
				for(int j=0;j<b.size();j++)c[i+j]+=a[i]*b[j];
			}
			for(int i=0;i<c.size()-1;i++){
				c[i+1]+=c[i]/BASE;
				c[i]%=BASE;
			}
			while(c[c.size()-1]>BASE){
				c.push_back(c[c.size()-1]/BASE);
				c[c.size()-2]%=BASE;
			}
			while(c[c.size()-1]==0)c.pop_back();
			return c;
		}
		int rev(int x,int mxn){
			int ans=0;
			for(int i=0;i<__lg(mxn);i++){
				ans<<=1;
				ans+=x&1;
				x>>=1;
			}
			return ans;
		}
		auto fft(vector<complex<double> >a,char flag){
			vector<complex<double> >ans=a;
			for(int i=0;i<ans.size();i++){
				int p=rev(i,ans.size());
				if(p<i)swap(ans[p],ans[i]);
			}
			const double pi=3.1415926535897932385;
			for(int len=1;len<a.size();len<<=1){
				complex<double>omega={cos(pi/len),flag*sin(pi/len)};
				for(int now=0;now<a.size();now+=2*len){
					complex<double>k=1;
					for(int i=now;i<now+len;i++){
						auto x=ans[i];
						auto y=ans[i+len];
						ans[i]=x+k*y;
						ans[i+len]=x-k*y;
						k*=omega;
					}
				}
			}
			if(!~flag){
				for(int i=0;i<ans.size();i++)ans[i]/=ans.size();
			}
			return ans;
		}
		auto fft(vector<BASETYPE>a){
			vector<complex<double> >a_;
			for(int i:a)a_.push_back({i,0});
			return fft(a_,1);
		}
		auto ifft(vector<complex<double> >a){
			auto k=fft(a,-1);
			vector<BASETYPE>a_;
			for(auto i:k)a_.push_back(i.real()+0.2);
			return a_;
		}
		vector<BASETYPE>multiply(vector<BASETYPE>a,vector<BASETYPE>b){
			a.resize(max(a.size(),b.size()));
			b.resize(max(a.size(),b.size()));
			a.resize(1<<__lg(a.size())+2);
			b.resize(1<<__lg(b.size())+2);
			auto x=fft(a);
			auto y=fft(b);
			for(int i=0;i<x.size();i++)x[i]*=y[i];
			vector<BASETYPE>c=ifft(x);
			for(int i=0;i<c.size()-1;i++){
				c[i+1]+=c[i]/BASE;
				c[i]%=BASE;
			}
			while(c[c.size()-1]>BASE){
				c.push_back(c[c.size()-1]/BASE);
				c[c.size()-2]%=BASE;
			}
			while(c[c.size()-1]==0)c.pop_back();
			return c;
		}
		vector<BASETYPE>divide(vector<BASETYPE>a_,vector<BASETYPE>b_){
			auto a=a_,b=b_;
			reverse(a.begin(),a.end());
			reverse(b.begin(),b.end());
			auto k=InOrdered::divide(a,b);
			reverse(k.begin(),k.end());
			return k;
		}
	public:
		vector<BASETYPE> str={0};
		signed sign=1;
		inline BigInt operator=(BigInt a){
			this->str=a.str;
			this->sign=a.sign;
			return *this;
		}
		inline BigInt operator=(string a){
			if(a[0]=='-')this->sign=-1;
			else this->sign=1;
			if(a[0]=='-')a.erase(a.begin());
			if(a[0]=='+')a.erase(a.begin());
			this->str=Str_Vec(a);
			return *this;
		}
		inline BigInt operator=(long long a){
			long long b=abs(a);
			vector<BASETYPE>t;
			if(a==0)t.push_back(0);
			else{
				while(b>0){
					t.push_back(b%BASE);
					b/=BASE;
				}
				//reverse(t.begin(),t.end());
			}
			this->str=t;
			if(a>=0)this->sign=1;
			else{
				this->sign=-1;
			}
			return *this;
		}
		inline BigInt operator+(BigInt a){
			BigInt b;
			if(a.sign==this->sign){
				b.str=add(this->str,a.str);
				b.sign=this->sign;
			}else{
				if(is_bigger(this->str,a.str)){
					b.str=subtract(this->str,a.str);
					b.sign=this->sign;
				}else if(this->str==a.str){
					vector<BASETYPE>zero;
					zero.push_back(0);
					b.str=zero;
					b.sign=1;
				}else{
					b.str=subtract(a.str,this->str);
					b.sign=a.sign;
				}
			}
			return b;
		}
		inline BigInt operator-(BigInt a){
			BigInt b;
			if(this->sign==1 and a.sign==1){
				if(is_bigger(this->str,a.str) or this->str==a.str){
					b.sign=1;
					b.str=subtract(this->str,a.str);
				}else{
					b.sign=-1;
					b.str=subtract(a.str,this->str);
				}
			}
			if(this->sign==1 and a.sign==-1){
				b.sign=1;
				b.str=add(a.str,this->str);
			}
			if(this->sign==-1 and a.sign==1){
				b.sign=-1;
				b.str=add(a.str,this->str);
			}
			if(this->sign==-1 and a.sign==-1){
				if(is_bigger(this->str,a.str)){
					b.sign=-1;
					b.str=subtract(this->str,a.str);
				}else{
					b.sign=1;
					b.str=subtract(a.str,this->str);
				}
			}
			return b;
		}
		inline BigInt operator*(BigInt a){
			BigInt b;
			b.str=multiply(this->str,a.str);
			b.sign=a.sign*(this->sign);
			if(a.str[0]==0)b.sign=1;
			return b;
		}
		inline BigInt operator/(BigInt a){
			if(a==0){
				throw DivByZero();
			}
			BigInt b;
			vector<BASETYPE>x=this->str;
			vector<BASETYPE>y=a.str;
			b.str=divide(x,y);
			b.sign=a.sign*(this->sign);
			if(b.str[b.str.size()-1]==0)b.sign=1;
			return b;
		}
		inline BigInt operator%(BigInt a){
			if(a==0)throw DivByZero();
			BigInt b;
			b=*this-a*(*this/a);
			return b;
		}
		
		inline BigInt operator+(long long a){
			BigInt b,A;
			A=a;
			b=A+*this;
			return b;
		}
		inline BigInt operator-(long long a){
			BigInt b,A;
			A=a;
			b=*this-A;
			return b;
		}
		inline BigInt operator*(long long a){
			BigInt b,A;
			A=a;
			b=*this*A;
			return b;
		}
		inline BigInt operator/(long long a){
			if(a==0)throw DivByZero();
			BigInt b,A;
			A=a;
			b=*this/A;
			return b;
		}
		inline BigInt operator%(long long a){
			if(a==0)throw DivByZero();
			BigInt b,A;
			A=a;
			b=*this%A;
			return b;
		}
		
		
		inline bool operator==(BigInt a){
			return ((this->str==a.str)&&(this->sign==a.sign))||(this->str[this->str.size()-1]==0 && a.str[a.str.size()-1]==0);
		}
		inline bool operator>(BigInt a){
			if(this->sign==1 and a.sign==1 and (this->str[0]!=0 or a.str[0]!=0))return is_bigger(this->str,a.str);
			if(this->sign==1 and a.sign==-1 and (this->str[0]!=0 or a.str[0]!=0))return 1;
			if(this->sign==-1 and a.sign==1)return 0;
			if(this->sign==-1 and a.sign==-1 and (this->str[0]!=0 or a.str[0]!=0))return !is_bigger(this->str,a.str);
			return 0;
		}
		inline bool operator>=(BigInt a){
			return *this>a || *this==a;
		}
		inline bool operator<(BigInt a){
			return !(*this>=a);
		}
		inline bool operator<=(BigInt a){
			return !(*this>a);
		}
		inline bool operator!=(BigInt a){
			return !(*this==a);
		}
		
		inline bool operator==(long long a){
			BigInt x;
			x=a;
			return *this==x;
		}
		inline bool operator>(long long a){
			BigInt x;
			x=a;
			return *this>x;
		}
		inline bool operator>=(long long a){
			BigInt x;
			x=a;
			return *this>=x;
		}
		inline bool operator<(long long a){
			BigInt x;
			x=a;
			return *this<x;
		}
		inline bool operator<=(long long a){
			BigInt x;
			x=a;
			return *this<=x;
		}
		inline bool operator!=(long long a){
			BigInt x;
			x=a;
			return !(*this==x);
		}
		
		
		inline BigInt operator+=(BigInt a){
			*this=*this+a;
			return *this;
		}
		inline BigInt operator+=(long long a){
			*this=*this+a;
			return *this;
		}
		inline BigInt operator-=(BigInt a){
			*this=*this-a;
			return *this;
		}
		inline BigInt operator-=(long long a){
			*this=*this-a;
			return *this;
		}
		inline BigInt operator*=(BigInt a){
			*this=*this*a;
			return *this;
		}
		inline BigInt operator*=(long long a){
			*this=*this*a;
			return *this;
		}
		inline BigInt operator/=(BigInt a){
			*this=*this/a;
			return *this;
		}
		inline BigInt operator/=(long long a){
			*this=*this/a;
			return *this;
		}
		inline BigInt operator%=(BigInt a){
			*this=*this%a;
			return *this;
		}
		inline BigInt operator%=(long long a){
			*this=*this%a;
			return *this;
		}
		inline BigInt operator++(){
			*this+=1;
			return *this;
		}
		inline BigInt operator--(){
			*this-=1;
			return *this;
		}
		inline BigInt operator++(int){
			BigInt a=*this;
			*this+=1;
			return a;
		}
		inline BigInt operator--(int){
			BigInt a=*this;
			*this-=1;
			return a;
		}
};
inline BigInt abs(BigInt a){
	BigInt ret;
	ret.str=a.str;
	ret.sign=1;
	return ret;
}
inline string to_string(BigInt a){
	string ret;
	if(a.sign==-1)ret+='-';
	ret+=Vec_Str(a.str);
	return ret;
}
inline BigInt operator+(long long a,BigInt b){
	return b+a;
}
inline BigInt operator-(long long a,BigInt b){
	BigInt k;
	k=a;
	return k-b;
}
inline BigInt operator*(long long a,BigInt b){
	return b*a;
}
inline BigInt operator/(long long a,BigInt b){
	BigInt k;
	k=a;
	return k/b; 
}
inline BigInt operator%(long long a,BigInt b){
	BigInt k;
	k=a;
	return k%b;
}
inline bool operator==(long long a,BigInt b){
	BigInt p;
	p=a;
	return p==a;
} 
inline bool operator>(long long a,BigInt b){
	BigInt p;
	p=a;
	return p>a;
} 
inline bool operator<(long long a,BigInt b){
	BigInt p;
	p=a;
	return p<a;
} 
inline bool operator>=(long long a,BigInt b){
	BigInt p;
	p=a;
	return p>=a;
} 
inline bool operator<=(long long a,BigInt b){
	BigInt p;
	p=a;
	return p<=a;
} 
inline bool operator!=(long long a,BigInt b){
	BigInt p;
	p=a;
	return p!=a;
}
inline ostream & operator<<(ostream &out,const BigInt a){
	if(a.sign==-1)out<<'-';
	out <<Vec_Str(a.str);
	return out;
}

inline istream & operator>>(istream &in,BigInt& a)
{
	string str;
	in>>str;
	a=str;
	return in;
}
#undef BASE
#undef WIDTH
#endif

int main(){
    BigInt a,b;
    cin>>a>>b;
    cout<<a*b;
}

如上的代码压了2位,并且可以AC本题,但是P1932会T; 因此扩大压位位数:将

#define BASETYPE long long
#define BASE (long long)1e2
#define WIDTH 2

中的2改为3

全WA;

改为如下的__int128形式,依然WA:

#define BASETYPE __int128
#define BASE (__int128)1e3
#define WIDTH 3

但是FFT的压位上线这么低?

2023/10/30 18:21
加载中...