板子
博主线上考试自己用的板子。
快读
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
计数题
取模
inline int add(int x){return (x>=mod)?x-mod:x;}
inline void add(int &x,int y){x=add(x+y);return ;}
inline int sub(int x){return (x<0)?x+mod:x;}
inline void sub(int &x,int y){x=sub(x-y);return ;}
inline int power(int x,int b){
int res=1;
while(b){
if(b&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
b>>=1;
}
return res;
}
阶乘预处理与组合数
int fc[maxn],ifc[maxn];
inline int binom(int n,int m){
if(n>m||m<0)return 0;
return 1ll*fc[n]*ifc[m]%mod*ifc[n-m]%mod;
}
void init(int n){
fc[0]=1;for(int i=1;i<=n;i++)fc[i]=1ll*fc[i-1]*i%mod;
ifc[n]=power(fc[n],mod-2);for(int i=n-1;i>=0;i--)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;
return ;
}
字符串题
SAM
int tot=1,lst=1;
int to[2*maxn][26],len[2*maxn],nxt[2*maxn];
int siz[2*maxn];
void extend(int c){
int p=lst,u=++tot;
len[u]=len[p]+1;siz[u]=1;
while(p&&!to[p][c])to[p][c]=u,p=nxt[p];
if(!p)nxt[u]=1;
else{
int d=to[p][c];
if(len[d]==len[p]+1)nxt[u]=d;
else{
int v=++tot;
len[v]=len[p]+1;
for(int i=0;i<26;i++)to[v][i]=to[d][i];
nxt[v]=nxt[d];nxt[d]=nxt[u]=v;
while(p&&to[p][c]==d)to[p][c]=v,p=nxt[p];
}
}
lst=u;
return ;
}