最无敌的（114514版，504行）！！
原题链接：1.A+B problem
2025-08-26 11:34:27
发布于：浙江
11阅读
0回复
0点赞
题解 100% AC
#include<bits/stdc++.h>
using namespace std;
int an[10010],bn[10010],cn[10010];
string s1,s2;
void stoh(string s,int h[]){
h[0]=s.size();
for(int i=1,j=s.size()-1;i<=h[0];i++,j--)h[i]=s[j]-'0';
}
void add(int a[],int b[],int c[]){
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++){
c[i+1]=(a[i]+b[i]+c[i])/10;
c[i]=(a[i]+b[i]+c[i])%10;
}
if(c[c[0]+1]>0)c[0]++;
}
void print(int x[]){
for(int i=x[0];i>=1;i--)cout<<x[i];
}
void solve1(){
cin>>s1>>s2;
stoh(s1,an),stoh(s2,bn),add(an,bn,cn),print(cn);
}
const double PI=4*atan(1);
template<typename T>
void Swap(T &a,T &b){
T c=a;
a=b;
b=c;
return;
}
template<typename T>
T Max(const T &a,const T &b){
return a<b?b:a;
}
typedef long long ll;
struct comp{
double real,imag;
comp operator+(const comp &x)const{
return {real+x.real,imag+x.imag};
}
comp operator-(const comp &x)const{
return {real-x.real,imag-x.imag};
}
comp operator*(const comp &x)const{
return {real*x.real-imag*x.imag,real*x.imag+x.real*imag};
}
comp operator/(const unsigned &x)const{
return {real/(double)x,imag/(double)x};
}
};
void FFT(comp *f,unsigned n,int rev){
for(unsigned i=1,j=n>>1,k;i<n-1;i++){
if(i<j)
Swap(f[i],f[j]);
k=n>>1;
while(j>=k){
j-=k;
k>>=1;
}
j+=k;
}
for(unsigned l=2;l<=n;l<<=1){
double arg=2*PI*rev/l;
comp wn={cos(arg),sin(arg)};
for(unsigned i=0;i<n;i+=l){
comp w={1,0};
for(unsigned j=0;j<(l>>1);j++){
comp f1=f[i+j];
comp f2=f[i+j+(l>>1)];
f[i+j]=f1+w*f2;
f[i+j+(l>>1)]=f1-w*f2;
w=w*wn;
}
}
}
if(!~rev)
for(unsigned i=0;i<n;i++)
f[i]=f[i]/n;
}
#define BASE 100
template<const unsigned Size>
class bigint{
private:
unsigned len;
int num[Size];
void init(){
memset(num,0,sizeof(num));
len=1;
}
bool abs_greater_equal(const bigint &a)const{
if(len!=a.len)
return len>a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]>a.num[i];
return 1;
}
public:
bigint(){
init();
}
void get_num(std::string s){
init();
int f=0;
unsigned slen=s.length();
if(s[0]=='-')
num[0]=f=1;
len=0;
unsigned temp=0,w=1;
for(int i=slen-1;i>=f;i--){
temp+=(s[i]^48)*w;
w=(w<<1)+(w<<3);
if(w==BASE||i==f){
num[++len]=(int)temp;
temp=0;
w=1;
}
}
if(temp||len==0)
num[++len]=temp;
}
bool operator<(const bigint &a)const{
if(num[0]&&!a.num[0])
return 1;
if(!num[0]&&a.num[0])
return 0;
if(num[0]){
if(len!=a.len)
return len>a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]>a.num[i];
}
else{
if(len!=a.len)
return len<a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]<a.num[i];
}
return 0;
}
bigint operator+(const bigint &a)const{
bigint res;
if(len==1&&num[1]==0){
res=a;
return res;
}
if(a.len==1&&a.num[1]==0){
res=*this;
return res;
}
if(num[0]==a.num[0]){
res.num[0]=num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new comp[len_sum]();
comp *fb=new comp[len_sum]();
for(unsigned i=0;i<len;i++)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]+fb[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
res.num[i+1]=(int)(val%BASE);
temp=val/BASE;
}
if(temp)
res.num[++res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
}
else{
if(abs_greater_equal(a)){
res.num[0]=num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new comp[len_sum]();
comp *fb=new comp[len_sum]();
for(unsigned i=0;i<len;i++)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]-fb[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
if(val<0){
val+=BASE;
temp=-1;
}
else
temp=0;
res.num[i+1]=(int)(val%BASE);
}
if(temp)
res.num[++res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
}
else{
res.num[0]=a.num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new comp[len_sum]();
comp *fb=new comp[len_sum]();
for(unsigned i=0;i<len;i++)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fb[i]-fa[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
if(val<0){
val+=BASE;
temp=-1;
}
else
temp=0;
res.num[i+1]=(int)(val%BASE);
}
if(temp)
res.num[++res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
}
if(res.len==1&&res.num[1]==0)
res.num[0]=0;
}
return res;
}
bigint operator*(const bigint &a)const{
bigint res;
if((len==1&&num[1]==0)||(a.len==1&&a.num[1]==0))
return res;
res.num[0]=num[0]^a.num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new comp[len_sum]();
comp *fb=new comp[len_sum]();
for(unsigned i=0;i<len;i++)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]*fb[i];
FFT(fa,len_sum,-1);
res.len=len+a.len;
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)(fa[i].real+0.5)+temp;
res.num[i+1]=(int)(val%BASE);
temp=val/BASE;
}
if(temp)
res.num[++res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
return res;
}
void read(){
init();
std::string s;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
s.push_back('-');
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s.push_back(ch);
ch=getchar();
}
get_num(s);
}
void print(){
if(num[0])
putchar('-');
bool leading_zero=1;
for(int i=len;i;i--){
if(leading_zero)
printf("%d",num[i]);
else
printf("%02d",num[i]);
leading_zero=0;
}
putchar('\n');
return;
}
};
const int N=1<<10,M=100;
int n,m;
bigint<114514> a,b,c;
void solve2(){
a.read();
b.read();
c=a+b;
c.print();
}
#define int long long
#define ull unsigned int
#define N 65536
int memory[N];
ull code[N] = {
0x0000000000000000, 0x0000000000000001, 0x5000000000010002, 0x1000000000000002, 0xf000000000000000
};
void solve3()
{
for(int i=0;;i=(i+1)%N)
{
int op=code[i]>>60;
if(op==0) //Input
{
int p=code[i]&65535;
cin >> memory[ (code[i]>>56)&1 ? memory[p] : p ];
}
else if(op==1) //Output
{
int p=code[i]&65535, val = memory[ (code[i]>>56)&1 ? memory[p] : p ];
if((code[i]>>57)&1)
{
cout<<char(val&127);
}
else
{
cout<<val;
}
}
else if(op==2) //Write
{
int p = (code[i]>>32)&65535, val = code[i]&((1ll<<32)-1);
memory[ (code[i]>>56)&1 ? memory[p] : p ] = val;
}
else if(op==3) //Copy
{
int pf = (code[i]>>16)&65535, pt = code[i]&65535;
int val = memory[ (code[i]>>55)&1 ? memory[pf] : pf ];
memory[ (code[i]>>56)&1 ? memory[pt] : pt ] = val;
}
else if(op==4) //Calculate (& | ~ ^ << >>)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
int op2 = (code[i]>>52)&15;
if(op2==0)
{
val3=val1&val2;
}
else if(op2==1)
{
val3=val1|val2;
}
else if(op2==2)
{
val3=~val2;
}
else if(op2==3)
{
val3=val1^val2;
}
else if(op2==4)
{
val3=((val2>>6)?0:val1<<val2);
}
else
{
val3=((val2>>6)?0:val1>>val2);
}
memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
}
else if(op==5)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
int op2 = (code[i]>>52)&15;
if(op2==0)
{
val3=val1+val2;
}
else if(op2==1)
{
val3=val1-val2;
}
else if(op2==2)
{
val3=val1*val2;
}
else if(op2==3)
{
val3=(val2?val1/val2:0);
}
else
{
val3=(val2?val1%val2:0);
}
memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
}
else if(op==6) //Goto
{
int p=code[i]&65535;
i = (code[i]>>56)&1 ? memory[p] : p;
i = (i+N-1)%N;
}
else if(op==7) //If-goto (> < == >= <= !=)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ];
int op2 = (code[i]>>52)&15;
bool flag;
if(op2==0)
{
flag=(val1>val2);
}
else if(op2==1)
{
flag=(val1<val2);
}
else if(op2==2)
{
flag=(val1==val2);
}
else if(op2==3)
{
flag=(val1>=val2);
}
else if(op2==4)
{
flag=(val1<=val2);
}
else
{
flag=(val1!=val2);
}
if(flag)
{
i = (code[i]>>56)&1 ? memory[p3] : p3;
i = (i+N-1)%N;
}
}
else if(op==8) //x++
{
int p=code[i]&65535;
memory[ (code[i]>>56)&1 ? memory[p] : p ]++;
}
else if(op==9) //x--
{
int p=code[i]&65535;
memory[ (code[i]>>56)&1 ? memory[p] : p ]--;
}
else if(op==15) //Exit
{
break;
}
else
{
cout<<"\n\nError: Invalid code\n\n";
}
}
}
signed main(void){
srand(time(0));
int x=1+rand()%3;
if(x==1)solve1();
else if(x==2)solve2();
else if(x==3)solve3();
return 0;
}
这里空空如也
有帮助，赞一个