求助QAQ

回复帖子

@niiick 2019-01-08 18:27 回复

WA3 T9实在找不到错了QAQ, 蒟蒻几乎都照着题解抄了

#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;
typedef double dd;
#define eps 1e-7

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const dd Pi=acos(-1.0);
const int maxn=1200010;
int n,m;
struct complex{
    dd x,y;
    complex(dd _x=0,dd _y=0){ x=_x; y=_y;}
}A[maxn],B[maxn],C[maxn];
int lim=1,L,R[maxn];
char pat[maxn],txt[maxn];
int a[maxn],b[maxn];
int ans[maxn],cnt;

complex operator +(complex a,complex b){ return complex( a.x+b.x, a.y+b.y);}
complex operator -(complex a,complex b){ return complex( a.x-b.x, a.y-b.y);}
complex operator *(complex a,complex b){ return complex( a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}

void FFT(complex* a,int opt)
{
    for(int i=0;i<lim;++i)
    if(i<R[i]) swap(a[i],a[R[i]]);

    for(int i=1;i<lim;i<<=1)
    {
        complex wn(cos(Pi/i),opt*sin(Pi/i));
        for(int j=0;j<lim;j+=(i<<1))
        {
            complex w(1,0);
            for(int k=0;k<i;++k)
            {
                complex nx=a[j+k],ny=w*a[i+j+k];
                a[j+k]=nx+ny;
                a[i+j+k]=nx-ny;
                w=w*wn;
            }
        }
    }

    if(opt==-1)
    for(int i=0;i<=lim;++i) a[i].x/=(dd)lim;
}

void solve1()
{
    for(int i=0;i<lim;++i) 
    A[i]=complex(a[i]*a[i]*a[i],0),B[i]=complex(b[i],0);
    FFT(A,1);FFT(B,1);
    for(int i=0;i<lim;++i) C[i]=C[i]+A[i]*B[i];
}

void solve2()
{
    for(int i=0;i<lim;++i) 
    A[i]=complex(a[i],0),B[i]=complex(b[i]*b[i]*b[i],0);
    FFT(A,1);FFT(B,1);
    for(int i=0;i<lim;++i) C[i]=C[i]+A[i]*B[i];
}

void solve3()
{
    for(int i=0;i<lim;++i) 
    A[i]=complex(a[i]*a[i],0),B[i]=complex(b[i]*b[i],0);
    FFT(A,1);FFT(B,1);
    for(int i=0;i<lim;++i) C[i]=C[i]-A[i]*B[i]*complex(2,0);
}

int main()
{
    n=read();m=read();
    scanf("%s%s",pat,txt);
    reverse(pat,pat+n);

    while(lim<=n+m-2) lim<<=1,L++;
    for(int i=0;i<lim;++i)
    R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

    for(int i=0;i<n;++i) a[i]=(pat[i]!='*')?(pat[i]-'a'+1):0;
    for(int i=0;i<m;++i) b[i]=(txt[i]!='*')?(txt[i]-'a'+1):0;

    solve1(); solve2(); solve3();
    FFT(C,-1);
    for(int i=n-1;i<m;++i) 
    if(fabs(C[i].x)<eps) ans[++cnt]=i-n+2;

    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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