小学学校网站,网站备案更改需要多久,大兴模版网站建设哪家好,邯郸住房及城乡建设部网站[题目通道](【LK R-03】密码串匹配 - 洛谷)
一道神题。
如果没有修改操作#xff0c;翻转A数组或B数组后就是裸的FFT了 如果每次操作都暴力修改FFT时间复杂度显然爆炸 如果每次操作都不修改#xff0c;记下修改序列#xff0c;询问时加上修改序列的贡献#xff0c;…[题目通道](【LK R-03】密码串匹配 - 洛谷)
一道神题。
如果没有修改操作翻转A数组或B数组后就是裸的FFT了 如果每次操作都暴力修改FFT时间复杂度显然爆炸 如果每次操作都不修改记下修改序列询问时加上修改序列的贡献复杂度仍然爆炸
于是考虑把两种方法结合起来对操作序列分块
#include cstdio
#include cstring
#include cmath
#include iostream
#include algorithm
#define M 1000005
#define mod 998244353
#define g 3
using namespace std;
int n,ll,m,len1,L,power3[M],power_inv3[M],rev[M],H,cnt;
int X[M],Y[M],E[M];
long long A[M],B[M],C[M],tmp_A[M],tmp_B[M],len_inv,sum;
long long add(long long u,long long v){return (uv)mod?u-mod:u;}
long long inv(long long x){return x1?1:(mod-mod/x)*inv(mod%x)%mod;}
long long power(long long x,long long y){long long ans1,nowx;for (register long long iy;i;i1,nownow*now%mod)if (i1) ansans*now%mod;return ans;
}
char get_char(){//快读字母char cgetchar();while (ca||cz) cgetchar();return c-a;
}
int read(){//快读整数)char cgetchar();int ans0;while (c0||c9) cgetchar();while (c0c9) ansans*10c-0,cgetchar();return ans;
}
void Write(long long x){//快速输出if (x10) putchar(x^48);else Write(x/10),putchar((x%10)^48);return;
}
void NTT(long long *A,int flag){//NTT板子for (register int i0;ilen;i)if (irev[i]) swap(A[i],A[rev[i]]);for (register int l1;llen;l1){long long T(flag1?power3[l]:power_inv3[l]);for (register int i0;ilen;i(l1)){long long t1;for (register int j0;jl;j,tt*T%mod){long long uA[ij],vA[ijl]*t%mod;A[ij]add(u,v),A[ijl]add(u,mod-v);}}}return;
}
void mul(){//多项式乘法for (register int i0;ilen;i) tmp_B[i]B[i];NTT(tmp_B,1);for (register int i0;ilen;i) C[i]tmp_A[i]*tmp_B[i]%mod;NTT(C,-1);for (register int i0;ilen;i) C[i]C[i]*len_inv%mod;return;
}
long long query(int x){//处理询问操作long long nowC[xll-1];xll-1;for (register int i1;iX[0];i) nowY[i]*A[x-X[i]];//暴力加上修改块内修改操作贡献return sumE[x]-(xll?E[x-ll]:0)-now*2;
}
int main(){nread(),llread(),mread();H(int)(pow(n*log2(n),0.5))*3;while (lennll) len1,L;for (register int i0;ilen;i) rev[i](rev[i1]1)|((i1)L-1);for (register int i0;in;i) tmp_A[i]A[i]get_char(),E[i]E[i-1]A[i]*A[i];for (register int i0;ill;i) B[i]get_char(),sumB[i]*B[i];for (register int i0,jll-1;ij;i,j--) swap(B[i],B[j]);for (register int l1;llen;l1) power3[l]power(g,(mod-1)/(l1)),power_inv3[l]power(inv(g),(mod-1)/(l1));len_invinv(len);NTT(tmp_A,1);mul();//对密码串T只需要做一次FFTfor (register int i1,opt;im;i){optread();if (opt1) Write(query(read()-1)),putchar(\n);else {X[X[0]]ll-read(),Y[Y[0]]get_char();sum-B[X[X[0]]]*B[X[X[0]]];int tmpB[X[X[0]]];B[X[X[0]]]Y[Y[0]],Y[Y[0]]-tmp;sumB[X[X[0]]]*B[X[X[0]]];}if (X[0]H) mul(),X[0]Y[0]0;//块的末尾暴力做NTT}return 0;
}
