#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的压位上线这么低?