第一个点WA求助

P1303 A*B Problem

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;
}

|