哈希统计

Description

int work(char *s,int n,int base,int p){ long long ans=0; for(int i=1;i<=n;i++) ans=(ans*base+s[i])%p; return ans; } 以上代码为一种字符串hash的写法，给出base和p，试统计长度小于等于n且能使最后hash值为x的字符串（只能包含小写字母）有多少个。

Input

四个数，n，base，p，x(1<=n,p,base<=50000 , 0<=x

Output

一个数表示答案(对998244353取模)

Input示例

2 3 7 5

Output示例

100

---

请允许咱发自内心地说一句:猫太强了！
（猫是本机房的一个dalao）
翻dalao博客看见的题，想了很久很久都只会O(n2)做法……
咱还是太菜了不如回去搞文化

---

思路:
假如是在求长度刚好等于n时的答案，再在过程中累加，显然更加好求。 那么首先可以得到一个简单粗暴的递推式:
令f[i][j]表示目前长度刚好为i，哈希值为j的答案。
令g[i][j]表示目前长度不超过i，哈希值为j的答案。
那么
f[i+1][j∗base+s]+=f[i][j]
g[i+1][j]=g[i][j]+f[i+1][j]
这就获得了一个O(n2)的算法。 然而明显会严重超时。 因为并没有发现什么巧妙的性质，所以考虑使用正义的倍增加速:
令f[i][j]表示目前长度为2i，哈希值为j的答案。
令g[i][j]表示目前长度不超过2i，哈希值为j的答案。
那么
f[i+1][j∗base2i+k]+=f[i][j]∗f[i][k]
g[i+1][j]=g[i][j]
g[i+1][j∗base2i+k]=g[i][j]∗f[i][k]
这样可以发现总复杂度变成了O(n2log2n)，瓶颈是转移的O(n2)。 考虑到转移很明显是一个卷积的形式，可以使用正义的NTT加速转移。
那么总复杂度就变成了O(nlog22n)，成功解决此题~ #include #include #include #include #include using namespace std; typedef long long ll; const int N=150009; const int K=19; const ll md=998244353; ll f[K][N],g[K][N],ans[N]; ll a[N],b[N],c[N],invn,base; int n,p,x,m,rev[N],lens; int stk[K],top; inline ll qpow(ll a,ll b,ll md) { ll ret=1; while(b) { if(b&1) ret=ret*a%md; a=a*a%md; b>>=1; } return ret; } inline void init() { for(n=1;n<(p<<1);n<<=1)lens++; for(int i=0;i>1]>>1)|((i&1)<<(lens-1)); invn=qpow(n,md-2,md); } inline void NTT(ll *a,bool f) { for(int i=0;iif(ifor(int h=2;h<=n;h<<=1) { ll w=qpow(3ll,(md-1)/h,md); if(f)w=qpow(w,md-2,md); for(int j=0;j1ll; for(int k=j;k>1);k++) { ll x=a[k],y=wn*a[k+(h>>1)]%md; a[k]=(x+y)%md; a[k+(h>>1)]=(x-y+md)%md; wn=wn*w%md; } } } if(f) for(int i=0;iint main() { scanf("%d%d%d%d",&m,&base,&p,&x); for(int i='a';i<='z';i++) f[0][i%p]++,g[0][i%p]++; init(); ll bb=base; int cur=1; for(int i=0;(1<<(i+1))<=m;i++,cur=i) { for(int j=0;j0; for(int j=0;j0);NTT(b,0); for(int j=0;j1); for(int j=0;j1][j%p]+=c[j])%=md; for(int j=0;j0; for(int j=0;jfor(int j=0;j0);NTT(b,0); for(int j=0;j1); for(int j=0;j1][j%p]+=c[j])%=md; for(int j=0;j1][j]+=g[i][j])%=md; bb=bb*bb%p; } for(int i=cur;i>=0;i--) if(m>=(1<1<for(int i=0;ifor(int i=stk[--top];top;top--,i=stk[top]) { ll bb=qpow(base,(1<for(int j=0;j0; for(int j=0;jfor(int j=0;j0);NTT(b,0); for(int j=0;j1); for(int j=0;j0; for(int j=0;jfor(int j=0;jprintf("%lld ",ans[x]); return 0; }