BZOJ 4503 兩個串

2022-05-22 15:57:38 字數 2055 閱讀 7537

我們定義一個函式,\(f(x,y)=(a_x-b_y)^2 b_y\),使得有萬用字元的時候和相等的時候都為0

\[\begin&\sum_^\sum_^ (a_-b_j)^2b_j\\=&\sum_^\sum_^ (a_^2-2a_b_j+b_j^2)b_j\\=&\sum_^\sum_^ a_^2b_j-2a_b_j^2+b_j^3\\=&\sum_^\sum_^ a_^2b_j-\sum_^2a_b_j^2+\sum_^b_j^3\end

\]嘗試把b翻轉一下

\[\begin&\sum_^\sum_^ (a_-b_)^2b_\\=&\sum_^\sum_^ (a_^2-2a_b_+b_^2)b_\\=&\sum_^\sum_^ a_^2b_-2a_b_^2+b_^3\\=&\sum_^\sum_^ a_^2b_-\sum_^\sum_^2a_b_^2+\sum_^\sum_^b_^31\end

\]列舉\(m+i-1\),就變成卷積了

把三個式子分別捲起來

#include #include #include #define int long long

using namespace std;

const int maxn = 300000;

const int mod = 998244353;

const int g = 3;

const int invg = 332748118;

int rev[maxn];

void cal_rev(int n,int lim)

int pow(int a,int b)

return ans;

}void ntt(int *a,int opt,int n,int lim)}}

if(!opt)

}int s[maxn],t[maxn],x[maxn],a[maxn],b[maxn],c[maxn],n,m,ans[maxn],cnt;

char s[maxn];

signed main()

scanf("%s",s);

m=strlen(s);

for(int i=0;it[i]=(s[i]=='?')?0:s[i]-'a'+1;

reverse(t,t+m);

int midlen=1,midlim=0;

while(midlen<(n+m))

midlen<<=1,midlim++;

cal_rev(midlen,midlim);

for(int i=0;ib[i]=1;

for(int i=0;ia[i]=(t[i]*t[i]*t[i])%mod;

ntt(b,1,midlen,midlim);

ntt(a,1,midlen,midlim);

for(int i=0;ic[i]=(a[i]*b[i])%mod;

for(int i=0;ib[i]=(2*s[i])%mod;

for(int i=0;ia[i]=(t[i]*t[i])%mod;

ntt(b,1,midlen,midlim);

ntt(a,1,midlen,midlim);

for(int i=0;ic[i]=(c[i]-a[i]*b[i]+mod)%mod;

for(int i=0;ib[i]=(s[i]*s[i])%mod;

for(int i=0;ia[i]=(t[i])%mod;

ntt(b,1,midlen,midlim);

ntt(a,1,midlen,midlim);

for(int i=0;ic[i]=(c[i]+a[i]*b[i])%mod;

ntt(c,0,midlen,midlim);

// for(int i=0;i// printf("!%lld\n",c[i]);

for(int i=m-1;iif(!c[i])

ans[++cnt]=i-m+1;

printf("%lld\n",cnt);

for(int i=1;i<=cnt;i++)

printf("%lld\n",ans[i]);

return 0;

}

bzoj4503 兩個串

傳送門 題解 我們設匹配函式f a i b i 2 b i 那麼展開f,做卷積就能得出f的值了 對於t i b i 0,顯然當f 0表示匹配...