HDU 5763 Another Meaning（FFT）

时间：2023-12-04 14:51:50

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5763

【题目大意】

　　给出两个串S和T，可以将S串中出现的T替换为*，问S串有几种表达方式。

【题解】

　　我们定义数组f为S串中T出现的最后一个字母所在的位置，那么ans[i]=ans[i-1]+f[i-1]?ans[i-lenT]:0，一遍递推即可，所以关键就在于求出f数组了，f数组可以用kmp求，由于最近练FFT，用FFT求距离卷积匹配为0的位置，就是f数组了。

【代码】

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=524300;

int n,pos[N];

namespace FFT{

    struct comp{

        double r,i;

        comp(double _r=0,double _i=0):r(_r),i(_i){}

        comp operator +(const comp&x){return comp(r+x.r,i+x.i);}

        comp operator -(const comp&x){return comp(r-x.r,i-x.i);}

        comp operator *(const comp&x){return comp(r*x.r-i*x.i,i*x.r+r*x.i);}

        comp conj(){return comp(r,-i);}

    }A[N],B[N];

    const double pi=acos(-1.0);

    void FFT(comp a[],int n,int t){

        for(int i=1;i<n;i++)if(pos[i]>i)swap(a[i],a[pos[i]]);

        for(int d=0;(1<<d)<n;d++){

            int m=1<<d,m2=m<<1;

            double o=pi*2/m2*t;

            comp _w(cos(o),sin(o));

            for(int i=0;i<n;i+=m2){

                comp w(1,0);

                for(int j=0;j<m;j++){

                    comp& A=a[i+j+m],&B=a[i+j],t=w*A;

                    A=B-t;B=B+t;w=w*_w;

                }

            }

        }if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;

    }

}

const int mod=1e9+7;

int T,Cas=1,l1,l2,ans[N],cnt=0,a[N],b[N],f[N];

FFT::comp A[N],B[N],C[N];

char s1[N],s2[N];

int main(){

    scanf("%d",&T);

    while(T--){

        scanf(" %s %s",&s1,&s2);

        memset(f,0,sizeof(f));

        memset(ans,0,sizeof(ans));

        memset(a,0,sizeof(a));

        memset(b,0,sizeof(b));

        l1=strlen(s1); l2=strlen(s2);

        for(int i=0;i<l1;i++)a[i]=s1[i]-'a'+1;

        for(int i=0;i<l2;i++)b[l2-1-i]=s2[i]-'a'+1;

        int N=1; while(N<l1+l2)N<<=1;

        int j=__builtin_ctz(N)-1;

        for(int i=0;i<N;i++)C[i]=FFT::comp(0,0);

        for(int i=0;i<N;i++){pos[i]=pos[i>>1]>>1|((i&1)<<j);}

        for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i]*a[i],0),B[i]=FFT::comp(b[i],0);

        FFT::FFT(A,N,1);FFT::FFT(B,N,1);

        for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];

        for(int i=0;i<N;i++)A[i]=FFT::comp(a[i],0),B[i]=FFT::comp(b[i]*b[i]*b[i],0);

        FFT::FFT(A,N,1);FFT::FFT(B,N,1);

        for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];

        for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i],0),B[i]=FFT::comp(b[i]*b[i],0);

        FFT::FFT(A,N,1);FFT::FFT(B,N,1);

        for(int i=0;i<N;i++)C[i]=C[i]-A[i]*B[i]*FFT::comp(2,0);

        FFT::FFT(C,N,-1);

        for(int i=l2-1;i<l1;i++){

            if(C[i].r<0.5)f[i]=1;

        }ans[0]=1;

        for(int i=1;i<=l1;i++){

            ans[i]=ans[i-1];

            if(f[i-1])ans[i]+=ans[i-l2];

            if(ans[i]>mod)ans[i]-=mod;

        }printf("Case #%d: %d\n",Cas++,ans[l1]);

    }return 0;

}

　　

相关文章