A_R_O_N_A @ 2023-09-10 16:17:31
我使用了 FFT 算法,但是无法通过本题(已通过 P1919)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const double PI=acos(-1);
inline int read(){
int x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
static int sta[35];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top)putchar(sta[--top]+'0');
}
struct comp{
double r,i;
comp(){
r=0,i=0;
}
comp(double real,double imag):r(real),i(imag){}
};
comp operator +(comp a,comp b){
return comp(a.r+b.r,a.i+b.i);
}
comp operator -(comp a,comp b){
return comp(a.r-b.r,a.i-b.i);
}
comp operator *(comp a,comp b){
return comp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
}
int rev[3000005],len,lim=1;
comp a[3000005],b[3000005];
string s1,s2;
void FFT(comp *a,int op){
for(int i=0;i<lim;i++){
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(int mid=1; mid<lim; mid<<=1){
comp wn(cos(PI/mid),op*sin(PI/mid));
for(int r=mid<<1,j=0; j<lim; j+=r){
comp w(1,0);
for(int l=0; l<mid; l++,w=w*wn){
comp x=a[j+l],y=w*a[j+mid+l];
a[j+l]=x+y; a[j+mid+l]=x-y;
}
}
}
}
int n1,n2;
signed main(){
cin>>s1;
n1=s1.size()-1;
for(int i=0;i<=n1;i++)a[n1-i].r=s1[i]-'0';
cin>>s2;
n2=s2.size()-1;
for(int i=0;i<=n2;i++)b[n2-i].r=s2[i]-'0';
while(lim<=n1+n2){
lim<<=1;len++;
}
for(int i=0;i<lim;i++){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
}
FFT(a,1);FFT(b,1);
for(int i=0;i<=lim;i++)a[i]=a[i]*b[i];
FFT(a,-1);
memset(rev,0,sizeof(rev));
for(int i=0;i<=n1+n2+1;i++){
rev[i]=a[i].r/lim+0.5;
}
for(int i=0;i<=n1+n2;i++){
rev[i+1]+=rev[i]/10;
rev[i]%=10;
}
lim=n1+n2+1;
while(rev[lim]){
rev[lim+1]+=rev[lim]/10;
rev[lim]%=10;
lim++;
}
for(int i=lim-1;i>=0;i--)cout<<rev[i];
return 0;
}
by cff_0102 @ 2023-09-10 16:38:58
输入
0
114514
试试?
by A_R_O_N_A @ 2023-09-10 16:39:57
@cff_0102 确实是0的问题,但是在不加特判的情况下如何解决
by ZHYaiSYR @ 2023-09-16 14:39:41
@xie_T34
#include<iostream>
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<math.h>
int main(){
char a[2005], b[2005];
int c[5000] = {0};
scanf("%s\n%s", a, b);
int t1, t2;
int h = 0;
t1 = strlen(a), t2 = strlen(b);
int i, j;
for(i = t1 - 1; i != -1; i--)
{
int z = h;
for(j = t2 - 1; j != -1; j--)
{
int l = c[h];
c[h] = (c[h] + (a[i] - '0') * (b[j] - '0')) % 10;
h++;
c[h] += (l + (a[i] - '0') * (b[j] - '0')) / 10;
}
if(i)h = z + 1;
}
while(!c[h] && h)h--;
for(int m = h; m >= 0; m--)
{
printf("%d", c[m]);
}
return 0;
}