板子

博主线上考试自己用的板子。

快读

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 ;
}