字符串
KMP
nxt[i]
: $b[1:i]$ 的最长 border $b[1:nxt_i]$,且 $nxt_i<i$。
void init(){
int p=0;
F(i,2,m){
while(p&&b[p+1]!=b[i]) p=nxt[p];//p+1 尝试与 i 匹配
if(b[p+1]==b[i]) p++;
nxt[i]=p;
}
}
void kmp(){
int p=0;
F(i,1,n){
while(p&&(p==m||b[p+1]!=a[i]) p=nxt[p];//p==m
if(b[p+1]==a[i]) p++;
f[i]=p;
}
}
Z 函数
$z_1=0$。
z[i]
:$b[i:n]$ 与 b 的 LCP 长度。
void z_init(){
z[1]=0;//
for(int i=2,l=0,r=0;i<=m;i++){
if(i>r) z[i]=0;
else z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=m&&b[1+z[i]]==b[i+z[i]]) z[i]++;
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
}
void z_alg(){
for(int i=1,l=0,r=0;i<=n;i++){
if(i>r) p[i]=0;
else p[i]=min(z[i-l+1],r-i+1);
while(i+p[i]<=n&&b[1+p[i]]==a[i+p[i]]) p[i]++;
if(i+p[i]-1>r) l=i,r=i+p[i]-1;
}
}
Manacher
p[i]
:以 $i$ 为中心的最长回文半径。$[i-p_i+1,i+p_i+1]$ 为回文串。
void init(){
int m=0;
s[++m]='#';//s[0]='(',s[1]='#'
F(i,1,n) s[++m]=a[i],s[++m]='#';
s[0]='(';s[m+1]=')';
}
void manacher(){
p[1]=1;
for(int i=2,k=1;i<=m;i++){//k=1,当前最优端点属于 1 的回文串
if(i>k+p[k]-1) p[i]=1;
else p[i]=min(k+p[k]-i,p[2*k-i]);
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(i+p[i]>k+p[k]) k=i;
}
}
AC自动机
fail
:指向某状态所表示的字符串的最长后缀。
//AC
struct node{
int trs[26],fail;
}t[N];
int tot=1;//p=1 is used
void ins(){
int p=1;
F(i,1,n){
int c=s[i]-'a';
if(!t[p].trs[c]) t[p].trs[c]=++tot;
p=t[p].trs[c];
}
}
void bd(){
F(i,0,25) t[0].trs[i]=1;
t[1].fail=0;
queue<int>q;
q.push(1);
while(!q.empty()){
int u=q.front();q.pop();
F(i,0,25){
int &v=t[u].trs[i];//&v
if(v) t[v].fail=t[t[u].fail].trs[i],q.push(v);
else v=t[t[u].fail].trs[i];
}
}
}
SA
//SA
int m=256;
int sa[N],rk[N],tmp_rk[N],id[N],ct[N],px[N],ht[N];
bool same(int x,int y,int k){
int p=x+k<=n?tmp_rk[x+k]:-1,
q=y+k<=n?tmp_rk[y+k]:-1;
return tmp_rk[x]==tmp_rk[y]&&p==q;
}
void init(){
F(i,1,n) rk[i]=s[i];
F(i,1,n) ct[rk[i]]++;
F(i,1,m) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[rk[i]]--]=i;
for(int k=1,p=0;k<n;k<<=1,m=p){
p=0;
F(i,n-k+1,n) id[++p]=i;
F(i,1,n)if(sa[i]>k) id[++p]=sa[i]-k;
F(i,0,m) ct[i]=0;
F(i,1,n) ct[px[i]=rk[id[i]]++;
F(i,1,m) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[px[i]]--]=id[i];
F(i,1,n) tmp_rk[i]=rk[i];
p=0;
F(i,1,n) rk[sa[i]]=same(sa[i],sa[i-1],k)?p:++p;//
}
for(int i=1,h=0;i<=n;i++){
if(h) h--;
int j=sa[rk[i]-1];
while(s[i+h]==s[j+h]) h++;
ht[rk[i]]=h;//
}
}
SAM
//SAM
const int SZ=N<<1;
int tot=1,las=1;
struct node{
int trs[26],lk,mxl;
}t[SZ];
void extend(int c){
int p=las,np=las=++tot;
t[np].mxl=t[p].mxl+1;
for(;!t[p].trs[c];p=t[p].lk) t[p].trs[c]=np;
if(!p) t[np].lk=1;
else{
int q=t[p].trs[c];
if(t[q].mxl==t[p].mxl+1) t[np].lk=q;
else{
int nq=++tot;t[nq]=t[q];
t[nq].mxl=t[q].mxl+1;
t[q].lk=t[np].lk=nq;
for(;t[p].trs[c]==q;p=t[p].lk) t[p].trs[c]=nq;
}
}
}
数论
拉格朗日插值
==求点值==:
$O(n^2)$。
int lag(int k){
ll ans=0;
F(i,1,c+1){
ll p=1,q=1;
F(j,1,c+1)if(i^j){
p=p*(k-x[j])%mod;
q=q*(x[i]-x[j])%mod;
}
ans=(ans+p*inv(q)%mod*y[i])%mod;//y[i]
}
return (ans+mod)%mod;
}
==已知的横坐标连续时求点值==:
$O(n)$。
int lag(int k){
if(k<=c+1) return y[k];
pre[0]=1;
F(i,1,c+1) pre[i]=pre[i-1]*(k-i)%mod;
suf[c+1+1]=1;
for(int i=c+1;i>=1;i--) suf[i]=suf[i+1]*(k-i)%mod;
F(i,1,c+1){
ll val=pre[i-1]*suf[i+1]%mod*ifac[i-1]%mod*ifac[c+1-i]%mod*y[i]%mod;
if(val<0) val+=mod;
if((c+1-i)&1) dec(ans,val);
else add(ans,val);
}
return ans;
}
==横坐标连续时求系数==:
$O(n^2)$。
void calc(int *f,int *g,int n){
h[0]=1;
F(i,1,n+1) for(int j=i;j>=0;j--)
h[j]=((j?h[j-1]:0)+(mod-h[j])*i)%mod;
F(i,1,n+1){
memcpy(tmp,h,sizeof(tmp));
F(j,0,n+1)
tmp[j]=((j?tmp[j-1]:0)-tmp[j]+mod)*inv[i]%mod;
int sum=g[i];
F(j,1,n+1)if(j^i)
sum=sum*(i>j:inv[i-j]:mod-inv[j-i])%mod;
F(j,0,n) f[j]=(f[j]+sum*tmp[j])%mod;
}
}
子集DP
for (int i = 0; i < m; i ++)
for (int S = 0; S < (1 << m); S ++)
if (S >> i & 1) // f[S] <- f[S ^ (1 << i)]
线性筛素数
int pClock, prime[N], fac[N];
void sieve(const int &N) {
for (int i = 2; i <= N; i ++) {
if (!fac[i]) fac[i] = i, prime[++ pClock] = i;
for (int j = 1; j <= pClock; j ++) {
if (prime[j] > fac[i] || prime[j] > N / i) break;
fac[i * prime[j]] = prime[j];
}
}
}
####
标签:int,void,++,trs,mod,模板,rk From: https://www.cnblogs.com/nangle/p/18391577