2 条题解
-
0
#include<bits/stdc++.h>//快速数论变换(递归版) #define LL long long const int M=4e5+10; const LL P=(7ll<<26)+1; LL qpow(LL a,LL b){LL res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;} LL A[M],B[M],C[M]; void NTT(LL A[],LL n,LL x) { if(n==1)return; LL A1[n/2],A2[n/2]; for(LL i=0;i<n/2;++i)A1[i]=A[2*i],A2[i]=A[2*i+1]; NTT(A1,n/2,x*x%P); NTT(A2,n/2,x*x%P); for(LL i=0,xi=1;i<n/2;++i,xi=xi*x%P) { A[i] = (A1[i] + A2[i]*xi) % P; A[i+n/2] = ((A1[i] - A2[i]*xi) % P + P) % P; } } char s1[M/4],s2[M/4]; int main() { scanf("%s%s",s1,s2); int n=strlen(s1),m=strlen(s2); for(int i=0;i<n;++i)A[i]=s1[n-i-1]-'0'; for(int i=0;i<m;++i)B[i]=s2[m-i-1]-'0'; LL N=1;while(N<n+m-1)N<<=1;LL inv_N=qpow(N,P-2); LL x=qpow(3ll,(P-1)/N); NTT(A,N,x); NTT(B,N,x); for(int i=0;i<N;++i)C[i]=A[i]*B[i]%P; LL inv_x=qpow(x,P-2); NTT(C,N,inv_x); for(int i=0;i<N;++i)C[i]=C[i]*inv_N%P; for(int i=0;i<n+m-1;++i)C[i+1]+=C[i]/10,C[i]%=10; int len=N;while(C[len]==0 && len>0)len--; for(int i=len;i>=0;--i) printf("%lld",C[i]); return 0; }非递归版：
#include <bits/stdc++.h>//快速数论变换(非递归版) #define LL long long using namespace std; const int M=4e5+10; const LL P=(7ll<<26)+1; LL qpow(LL a,LL b){LL res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;} LL A[M],B[M],C[M],r[M]; void NTT(LL A[],LL n,LL x) { for(int i=0;i<n;++i)if(i<r[i])swap(A[i],A[r[i]]); for(LL m=2;m<=n;m<<=1) { LL xm=qpow(x,n/m); for(LL i=0;i<n;i+=m) { for(LL j=0,xj=1;j<m/2;++j,xj=xj*xm%P) { LL t1=A[i+j],t2=A[i+j+m/2]*xj%P; A[i+j] =(t1+t2)%P; A[i+j+m/2]=(t1-t2+P)%P; } } } } char s1[M/4],s2[M/4]; int main() { scanf("%s%s",s1,s2); int n=strlen(s1),m=strlen(s2); for(int i=0;i<n;++i)A[i]=s1[n-i-1]-'0'; for(int i=0;i<m;++i)B[i]=s2[m-i-1]-'0'; LL N=1;while(N<n+m-1)N<<=1;LL inv_N=qpow(N,P-2); for(int i=0;i<N;i++)r[i]=r[i/2]/2+(i&1)*N/2; LL x=qpow(3ll,(P-1)/N); NTT(A,N,x); NTT(B,N,x); for(int i=0;i<N;++i)C[i]=A[i]*B[i]%P; LL inv_x=qpow(x,P-2); NTT(C,N,inv_x); for(int i=0;i<N;++i)C[i]=C[i]*inv_N%P; for(int i=0;i<n+m-1;++i)C[i+1]+=C[i]/10,C[i]%=10; int len=N;while(C[len]==0 && len>0)len--; for(int i=len;i>=0;--i) printf("%lld",C[i]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:05:31
#include<bits/stdc++.h>//快速数论变换(递归版) #define LL long long const int M=4e5+10; const LL P=(7ll<<26)+1; LL qpow(LL a,LL b){LL res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;} LL A[M],B[M],C[M]; void NTT(LL A[],LL n,LL x) { if(n==1)return; LL A1[n/2],A2[n/2]; for(LL i=0;i<n/2;++i)A1[i]=A[2*i],A2[i]=A[2*i+1]; NTT(A1,n/2,x*x%P); NTT(A2,n/2,x*x%P); for(LL i=0,xi=1;i<n/2;++i,xi=xi*x%P) { A[i] = (A1[i] + A2[i]*xi) % P; A[i+n/2] = ((A1[i] - A2[i]*xi) % P + P) % P; } } char s1[M/4],s2[M/4]; int main() { scanf("%s%s",s1,s2); int n=strlen(s1),m=strlen(s2); for(int i=0;i<n;++i)A[i]=s1[n-i-1]-'0'; for(int i=0;i<m;++i)B[i]=s2[m-i-1]-'0'; LL N=1;while(N<n+m-1)N<<=1;LL inv_N=qpow(N,P-2); LL x=qpow(3ll,(P-1)/N); NTT(A,N,x); NTT(B,N,x); for(int i=0;i<N;++i)C[i]=A[i]*B[i]%P; LL inv_x=qpow(x,P-2); NTT(C,N,inv_x); for(int i=0;i<N;++i)C[i]=C[i]*inv_N%P; for(int i=0;i<n+m-1;++i)C[i+1]+=C[i]/10,C[i]%=10; int len=N;while(C[len]==0 && len>0)len--; for(int i=len;i>=0;--i) printf("%lld",C[i]); return 0; }
非递归版：#include <bits/stdc++.h>//快速数论变换(非递归版) #define LL long long using namespace std; const int M=4e5+10; const LL P=(7ll<<26)+1; LL qpow(LL a,LL b){LL res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;} LL A[M],B[M],C[M],r[M]; void NTT(LL A[],LL n,LL x) { for(int i=0;i<n;++i)if(i<r[i])swap(A[i],A[r[i]]); for(LL m=2;m<=n;m<<=1) { LL xm=qpow(x,n/m); for(LL i=0;i<n;i+=m) { for(LL j=0,xj=1;j<m/2;++j,xj=xj*xm%P) { LL t1=A[i+j],t2=A[i+j+m/2]*xj%P; A[i+j] =(t1+t2)%P; A[i+j+m/2]=(t1-t2+P)%P; } } } } char s1[M/4],s2[M/4]; int main() { scanf("%s%s",s1,s2); int n=strlen(s1),m=strlen(s2); for(int i=0;i<n;++i)A[i]=s1[n-i-1]-'0'; for(int i=0;i<m;++i)B[i]=s2[m-i-1]-'0'; LL N=1;while(N<n+m-1)N<<=1;LL inv_N=qpow(N,P-2); for(int i=0;i<N;i++)r[i]=r[i/2]/2+(i&1)*N/2; LL x=qpow(3ll,(P-1)/N); NTT(A,N,x); NTT(B,N,x); for(int i=0;i<N;++i)C[i]=A[i]*B[i]%P; LL inv_x=qpow(x,P-2); NTT(C,N,inv_x); for(int i=0;i<n+m-1;++i)C[i]=C[i]*inv_N%P; for(int i=0;i<n+m-1;++i)C[i+1]+=C[i]/10,C[i]%=10; int len=N;while(C[len]==0 && len>0)len--; for(int i=len;i>=0;--i) printf("%lld",C[i]); return 0; }
- 1
