最无敌的（114514版，662行）！！
2025-12-24 19:34:22
发布于：江苏
65阅读
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";
}
}
}
string qf (string a)
{
if (a[0] == '-') return a.substr (1 , a.size () - 1);
return "-" + a;
}
string operator - (string a) {return qf (a);}
string gjc (string a , string b)
{
if (a[0] == '-' && b[0] == '-') return gjc (- a , - b);
else if (a[0] == '-') return - gjc (- a , b);
else if (b[0] == '-') return - gjc (a , - b);
int ans[a.size () + b.size ()] = {};
reverse (a.begin () , a.end ());
reverse (b.begin () , b.end ());
for (int i = 0;i < a.size ();i ++)
for (int j = 0;j < b.size ();j ++) ans[i + j] += (a[i] - '0') * (b[j] - '0');
for (int i = 0;i < a.size () + b.size ();i ++)
if (ans[i] > 9)
{
int x = ans[i] % 10 , y = ans[i] / 10;
ans[i] = x;
ans[i + 1] += y;
}
string ans2 = "";
for (int i = 1;i <= a.size () + b.size ();i ++) ans2 += (char) (ans[i - 1] + '0');
if (ans2[ans2.size () - 1] == '0') ans2 = ans2.substr (0 , ans2.size () - 1);
reverse (ans2.begin () , ans2.end ());
return ans2;
}
string max (string a , string b)
{
if (a[0] == '-' && b[0] == '-')
{
if (- max (- a , - b) == a) return b;
return a;
}
else if (a[0] == '-') return b;
else if (b[0] == '-') return a;
else if (a.size () > b.size ()) return a;
else if (a.size () < b.size ()) return b;
else
{
for (int i = 0;i < a.size ();i ++)
if (a[i] > b[i]) return a;
else if (a[i] < b[i]) return b;
return a;
}
}
string min (string a , string b)
{
if (max (a , b) == a) return b;
return a;
}
string gjj (string a , string b);
string cut (string a , string b)
{
if (a[0] == '-' && b[0] == '-') return cut (- b , - a);
else if (a[0] == '-') return - gjj (- a , b);
else if (b[0] == '-') return gjj (b , - a);
else if (max (a , b) != a) return - cut (b , a);
reverse (a.begin () , a.end ());
reverse (b.begin () , b.end ());
string ans = "";
for (int i = 1;i <= a.size () + 1;i ++) ans += "0";
for (int i = 0;i < b.size ();i ++) ans[i] += a[i] - b[i];
for (int i = b.size ();i < a.size ();i ++) ans[i] = a[i];
for (int i = 0;i < ans.size ();i ++)
if (ans[i] < '0')
{
ans[i] += 10;
ans[i + 1] -= 1;
}
while (ans.size () > 1 && ans[ans.size () - 1] == '0') ans = ans.substr (0 , ans.size () - 1);
reverse (ans.begin () , ans.end ());
return ans;
}
string gjj (string a , string b)
{
if (a[0] == '-' && b[0] == '-') return - gjc (- a , - b);
else if (a[0] == '-') return cut (b , - a);
else if (b[0] == '-') return cut (a , - b);
if (a.size () < b.size ()) swap (a , b);
reverse (a.begin () , a.end ());
reverse (b.begin () , b.end ());
string ans = "";
for (int i = 1;i <= a.size () + 1;i ++) ans += "0";
for (int i = 0;i < b.size ();i ++) ans[i] += a[i] - '0' + b[i] - '0';
for (int i = b.size ();i < a.size ();i ++) ans[i] = a[i];
for (int i = 0;i < ans.size ();i ++)
if (ans[i] > '9')
{
ans[i] -= 10;
ans[i + 1] += 1;
}
if (ans[ans.size () - 1] == '0') ans = ans.substr (0 , ans.size () - 1);
reverse (ans.begin () , ans.end ());
return ans;
}
string dev (string b , int a)
{
if (a < 0 && b[0] == '-') return dev (- b , - a);
else if (a < 0) return - dev (b , - a);
else if (b[0] == '-') return - dev (- b , a);
while (a % 10 == 0 && b[b.size () - 1] == '0')
{
a /= 10;
b = b.substr (0 , b.size () - 1);
}
string ans = "";
int yu = 0;
for (int i = 0;i < b.size ();i ++)
{
yu = yu * 10 + b[i] - '0';
ans += yu / a + '0';
yu %= a;
}
while (ans.size () > 1 && ans[0] == '0') ans = ans.substr (1);
return ans;
}
string operator / (string a , int b) {return dev (a , b);}
string operator * (string a , string b) {return gjc (a , b);}
string operator + (string a , string b) {return gjj (a , b);}
string operator - (string a , string b) {return cut (a , b);}
string sqrt (string s)
{
if (s == "0") return "0";
if (s == "1") return "1";
string l = "1" , r = "1" , ans , dan = "1";
for (int i = 1;i < s.size () / 2;i ++) l += "0";
for (int i = 1;i <= s.size () / 2 + 1;i ++) r += "0";
while (max (l , r) == r)
{
string mid = (l + r) / 2;
if (max (mid * mid , s) == s)
{
ans = mid;
l = gjj (mid , dan);
}
else r = mid - dan;
}
return ans;
}
void solve4 (){
string a , b , c = "2";
cin >> a >> b;
if (a[0] == '-' && b[0] == '-') cout << - sqrt (a * a + b * b + c * a * b);
else if (a[0] == '-')
{
if (max (- a , b) == b) cout << sqrt (a * a + b * b + c * a * b);
else cout << - sqrt (a * a + b * b + c * a * b);
}
else if (b[0] == '-')
{
if (max (- b , a) == a) cout << sqrt (a * a + b * b + c * a * b);
else cout << - sqrt (a * a + b * b + c * a * b);
}
else cout << sqrt (a * a + b * b + c * a * b);
}
signed main(void){
srand(time(0));
int x=rand()%4+1;
if(x==1)solve1();
else if(x==2)solve2();
else if(x==3)solve3();
else if(x==4)solve4();
return 0;
}
有帮助，赞一个