WA70求助
查看原帖
WA70求助
98490
houzhiyuan楼主2022/1/21 18:26

一直WA 70分,WA 了1,3,4,5,6,9。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353,G=3,Gi=332748118;
int S,l,cnt[N];
int kuai(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*a*ans%mod;
    return ans;
}
void NTT(int *A,int T){
    for(int i=0;i<S;i++)if(i>cnt[i])swap(A[i],A[cnt[i]]);
    for(int mid=1;mid<S;mid<<=1){
        int W=kuai(T?G:Gi,(mod-1)/(mid*2));
        for(int L=0;L<S;L+=mid*2){
            int now=1;
            for(int k=0;k<mid;k++,now=1ll*now*W%mod){
                int x=A[L+k],y=1ll*A[L+k+mid]*now%mod;
                A[L+k]=(x+y)%mod;
                A[L+k+mid]=((x-y)%mod+mod)%mod;
            }
        }
    }
}
int A[N],B[N];
void mul(int *a,int *b,int *ans,int n,int m){
    for(l=0,S=1;S<=n+m;S*=2,l++);
    for(int i=0;i<=S;i++)A[i]=a[i];
    for(int i=0;i<=S;i++)B[i]=b[i];
    for(int i=1;i<=S;i++)cnt[i]=(cnt[i>>1]>>1)+((i&1)<<(l-1));
    NTT(A,1),NTT(B,1);
    for(int i=0;i<=S;i++)A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,0);
    int Inv=kuai(S,mod-2);
    for(int i=0;i<=n+m;i++)ans[i]=1ll*A[i]*Inv%mod;
}
int n,m,a[4][N],b[4][N],ans1[N],ans2[N],ans3[N],ans[N];
vector<int> vec;
char st[N];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",st);
    for(int i=0;i<n;i++){
        if(st[i]=='*')b[1][i]=0;
        else b[1][i]=st[i]-'a'+1;
    }
    scanf("%s",st);
    for(int i=0;i<m;i++){
        if(st[i]=='*')a[1][m-i-1]=0;
        else a[1][m-i-1]=st[i]-'a'+1;
    }
    for(int i=0;i<n;i++){
        b[2][i]=b[1][i]*b[1][i];
        b[3][i]=b[2][i]*b[1][i];
    }
    for(int i=0;i<m;i++){
        a[2][i]=a[1][i]*a[1][i];
        a[3][i]=a[2][i]*a[1][i];
    }
    n--,m--;
    mul(a[3],b[1],ans1,m,n);
    mul(a[2],b[2],ans2,m,n);
    mul(a[1],b[3],ans3,m,n);
    for(int i=0;i<S;i++)ans[i]=((ans1[i]-2ll*ans2[i]%mod+mod)%mod+ans3[i])%mod;
    n++,m++;
    for(int i=n-1;i<m;i++)if(!ans[i])vec.push_back(i-n+2);
    printf("%d\n",vec.size());
    for(int i:vec)printf("%d ",i);
}
2022/1/21 18:26
加载中...