FFT怎么一分都水不到?

P4245 【模板】任意模数多项式乘法

AffineRing @ 2020-11-17 21:21:12

RT三角形。

//38 lines of WA_code
#include<bits/stdc++.h>
using namespace std;
const long double Pi=acos(-1);
long long n,m,pp,tr[2700000];
struct CP{
    CP (long double xx=0,long double yy=0){x=xx,y=yy;}long double x,y;
    CP operator + (CP const &B) const {return CP(x+B.x,y+B.y);}
    CP operator - (CP const &B) const {return CP(x-B.x,y-B.y);}
    CP operator * (CP const &B) const {return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[2700000],g[2700000];
void fft(CP *f,bool flag){
    for(long long i=0;i<n;i++)
        if(i<tr[i])swap(f[i],f[tr[i]]);
    for(long long p=2;p<=n;p<<=1){
        long long len=p>>1;
        CP tG(cos(2*Pi/p),sin(2*Pi/p));
        if(!flag)tG.y*=-1;
        for(long long k=0;k<n;k+=p){
            CP buf(1,0);
            for(long long l=k;l<k+len;l++){
                CP tt=buf*f[len+l];
                f[len+l]=f[l]-tt,f[l]=f[l]+tt,buf=buf*tG;
            }
        }
    }
}
int main(){
    cin>>n>>m>>pp;
    for(long long i=0;i<=n;i++)cin>>f[i].x;
    for(long long i=0;i<=m;i++)cin>>g[i].x;
    for(m+=n,n=1;n<=m;n<<=1);
    for(long long i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    fft(f,1);fft(g,1);
    for(long long i=0;i<n;i++)f[i]=f[i]*g[i];
    fft(f,0);
    for(long long i=0;i<=m;++i)cout<<((long long)(f[i].x/n+0.5))%pp<<" ";
    return 0;
}

为何全WA,我认为这没有问题(至少部分分),然后一分也没有……什么原因啊


by Rui_R @ 2020-11-17 21:23:15

@KDL_56iNv02 我寻思它也没说给你部分分啊?


by AffineRing @ 2020-11-17 21:24:08

@Rui_R 我寻思我的输出应该是没有问题的


by Remake_ @ 2020-11-17 21:24:43

@KDL_56iNv02

FFT不适用任意模数的啊


by AffineRing @ 2020-11-17 21:26:32

@Miracle_Creator 在没模的时候输出不是对的吗……为啥按照题意模了之后就全错啦


by Rui_R @ 2020-11-17 21:27:27

@KDL_56iNv02 我寻思它系数是1e9,你中途运算位数不得上天,这肯定会掉精度掉的很严重的啊,要把系数拆开来做


by qwqqwq_qwqqwq @ 2020-11-17 21:28:37

运算过程中系数爆精度了


by Rui_R @ 2020-11-17 21:29:01

@KDL_56iNv02 FFT 中途那么多 double 和三角函数,带有误差,系数到1e9了误差过大肯定会出事的。


by AffineRing @ 2020-11-17 21:29:10

@Rui_R 谢谢


|