为什么窝的精度损失这么大啊qwq

回复帖子

@kkxhh 2019-03-10 11:54 回复

在吧eps从1e-8改到0.1的过程中分数呈递增趋势,然后在0.1的时候A了qwq

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

typedef struct complex{
    double a,b;
    complex() {}
    complex(double _a,double _b):a(_a),b(_b) {}
    complex operator + (complex x) {return complex(a+x.a,b+x.b);}
    complex operator - (complex x) {return complex(a-x.a,b-x.b);}
    complex operator * (complex x) {return complex(a*x.a-b*x.b,a*x.b+b*x.a);}
}complex;

const double Pi=acos(-1.0),eps=1e-5;
complex a[1050000],a2[1050000],a3[1050000],b[1050000],b2[1050000],b3[1050000];
int m,n,limit=1,l,r[1050000],ans[300010],siz;
char s[300010];

inline int read(){
    int num=0,k=1; char c=getchar();
    while(c>'9' || c<'0') k=(c=='-')?0:k,c=getchar();
    while(c>='0' && c<='9') num=num*10+c-'0',c=getchar();
    return k?num:-num;
}

void FFT(complex *a,int type){
    for(int i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
    for(int len=1;len<limit;len<<=1){
        complex w(cos(Pi/len),type*sin(Pi/len));
        for(int i=0;i<limit;i+=(len<<1)){
            complex k(1.0,0);
            for(int j=0;j<len;j++,k=k*w){
                complex x=a[i+j],y=k*a[i+j+len];
                a[i+j]=x+y; a[i+j+len]=x-y;
            }
        }
    }
    if(type==-1) for(int i=0;i<limit;i++) a[i].a/=limit;
}

int main(){
    m=read(); n=read();
    while(limit<=n+m) limit<<=1,l++;
    for(int i=0;i<limit;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(l-1)));
    scanf("%s",s);
    for(int i=m-1;i>=0;i--) a[i].a=((s[m-1-i]!='*')?(s[m-1-i]-'a'+1):0),a2[i].a=a[i].a*a[i].a,a3[i].a=a2[i].a*a[i].a;
    scanf("%s",s);
    for(int i=0;i<n;i++) b[i].a=((s[i]!='*')?(s[i]-'a'+1):0),b2[i].a=b[i].a*b[i].a,b3[i].a=b2[i].a*b[i].a;
    FFT(a,1); FFT(b,1); FFT(a2,1); FFT(b2,1); FFT(a3,1); FFT(b3,1);
    for(int i=0;i<limit;i++) a[i]=(a3[i]*b[i])+(a[i]*b3[i])-(complex(2.0,0)*b2[i]*a2[i]);
    FFT(a,-1);
    for(int i=m-1;i<=n-1;i++) if(fabs(a[i].a)<=eps) ans[++siz]=i-m+2;
    printf("%d\n",siz);
    for(int i=1;i<=siz;i++) printf("%d ",ans[i]);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。