mt19937_64引自tourist的哈希板子引入和时间相关的随机值mt19937_64所以不会被卡掉入参传入string使用#includebits/stdc.h using namespace std; #define rep(i,a,b) for(int i(a);i(b);i) #define per(i,a,b) for(int i(a);i(b);--i) typedef long long ll; typedef double db; typedef pairll,int P; #define fi first #define se second #define pb push_back #define dbg(x) cerr(#x):x ; #define dbg2(x) cerr(#x):xendl; #define SZ(a) (int)(a.size()) #define sci(a) scanf(%d,(a)) #define scll(a) scanf(%lld,(a)) #define pt(a) printf(%d,a); #define pte(a) printf(%d\n,a) #define ptlle(a) printf(%lld\n,a) #define debug(...) fprintf(stderr, __VA_ARGS__) mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); struct hash61 { static const uint64_t md (1LL 61) - 1; static uint64_t step; static vectoruint64_t pw; uint64_t addmod(uint64_t a, uint64_t b) const { a b; if (a md) a - md; return a; } uint64_t submod(uint64_t a, uint64_t b) const { a md - b; if (a md) a - md; return a; } uint64_t mulmod(uint64_t a, uint64_t b) const { uint64_t l1 (uint32_t) a, h1 a 32, l2 (uint32_t) b, h2 b 32; uint64_t l l1 * l2, m l1 * h2 l2 * h1, h h1 * h2; uint64_t ret (l md) (l 61) (h 3) (m 29) (m 35 3) 1; ret (ret md) (ret 61); ret (ret md) (ret 61); return ret - 1; } void ensure_pw(int sz) { int cur (int) pw.size(); if (cur sz) { pw.resize(sz); for (int i cur; i sz; i) { pw[i] mulmod(pw[i - 1], step); } } } vectoruint64_t pref; int n; templatetypename T hash61(const T s) { n (int) s.size(); ensure_pw(n 1); pref.resize(n 1); pref[0] 1; for (int i 0; i n; i) { pref[i 1] addmod(mulmod(pref[i], step), s[i]); } } inline uint64_t operator()(const int from, const int to) const { assert(0 from from to to n - 1); return submod(pref[to 1], mulmod(pref[from], pw[to - from 1])); } }; uint64_t hash61::step (md 2) rng() % (md 1); vectoruint64_t hash61::pw vectoruint64_t(1, 1); string s; int n; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cinns; auto hshash61(s); int l0,rn-1; couths(l,r)endl; return 0; }双哈希/多哈希tips用之前要给用于比较的两个串拼成一个串中间分隔没出现的字符例如2023ccpc网络赛A题中令wt#s#includebits/stdc.h using namespace std; const int N1e610,M2e610,MOD998244353; char s[N],t[N],w[M]; int n,m,up,f[N],way[N],sum[N],sq[N]; namespace Hash{ const int K2; const int bs[K]{19260817,19491001}; const int mod[K]{1000000007,1000000009}; int hs[K][M],pw[K][M]; int cal(int k,int l,int r){ int *valhs[k],*basepw[k]; int wmod[k]; return (val[r]-1ll*val[l-1]*base[r-l1]%ww)%w; } void init(char *w,int up){ for(int k0;kK;k){ int *valhs[k],*basepw[k]; int Bbs[k],Wmod[k]; val[0]base[0]1; for(int i1;iup;i){ base[i]1ll*base[i-1]*B%W; val[i](1ll*val[i-1]*Bw[i])%W; } } } bool same(int x,int y,int len){ for(int k0;kK;k){ if(cal(k,x,xlen-1)!cal(k,y,ylen-1))return 0; } return 1; } int lcp(int x,int y){ if(xup || yup)return 0; int l0,rup-max(x,y)1; while(lr){ int mid(lr)/2; if(same(x,y,mid))lmid1; else rmid-1; } return r; } } using namespace Hash; void add(int x,int y){ xy; if(xMOD)x-MOD; } void add(int *a,int l,int r,int v){ add(a[l],v); add(a[r1],MOD-v); } int main(){ scanf(%s%s,s1,t1); nstrlen(s1); mstrlen(t1); upnm1; sprintf(w1,%s#%s,t1,s1); init(w,up); int s00,s10,s20; add(way,1,1,1); for(int i1;in1;i){ add(s0,way[i]); add(s1,sum[i]); add(s2,sq[i]); if(in1)break; int limmin(m,n-i1); int stm1i; int firmin(lcp(1,st),lim); if(firlim)f[i]lim; else{ int seclcp(fir2,stfir1); f[i]min(firsec1,lim); } int n1(s0s1)%MOD; int n2(s22ll*s1s0)%MOD; int Li1,Rif[i]; add(way,L,R,s0); add(sum,L,R,n1); add(sq,L,R,n2); } printf(%d\n,s2); return 0; }