前言

所有代码中未加的默认加上“#define ll long long”

板子可改进的地方欢迎指出
多项式好难，人太懒了，现在还没搞定所有板子
上一页：C++竞赛常用实用代码（5）

计算几何

下面的几个板子之间可能互相调用

二维坐标/向量结构体

const double bt=1e-10,inf=pow(2.0,1000000000),PI=acos(-1.0);
struct pv{ //point or vector, 既表示坐标又可表示向量double x,y;pv(){}pv(double X,double Y){x=X,y=Y;}void READ(){scanf("%lf%lf",&x,&y);} //读入double length(){return sqrt(x*x+y*y);} //模长double K(){ //斜率if(fabs(x)<=bt)return inf;else return y/x;}bool operator<(const pv&b)const{ //横坐标排序（多用于求凸包）return x<b.x||(x==b.x&&y<b.y);}double operator*(const pv&b){return x*b.x+y*b.y;}//内积pv operator*(const double&b){return pv(x*b,y*b);}//数乘pv operator/(const double&b){return pv(x/b,y/b);}//数除pv operator+(const pv&b){return pv(x+b.x,y+b.y);}//向量加pv operator-(const pv&b){return pv(x-b.x,y-b.y);}//向量减bool operator==(const pv&b)const{ //判相等return fabs(x-b.x)<=bt&&fabs(y-b.y)<=bt;}bool operator!=(const pv&b)const{ //判不等return fabs(x-b.x)>bt||fabs(y-b.y)>bt;}pv GN(){return pv(y,-x);}//返回一个与它垂直的向量 
};
inline double cro(pv a,pv b){return a.x*b.y-b.x*a.y;} //叉积
inline double dis(pv a,pv b){return (b-a).length();} //距离

二维线段/直线结构体

struct line{ //两点确立线段/直线pv a,b;line(){}line(pv A,pv B){a=A,b=B;}void READ(){a.READ(),b.READ();} //读入pv vecm(){return b-a;} //方向向量void sort(){if(b<a)swap(a,b);} //规范两点位置为从左到右bool ni(pv c){ //判断点c是否在线段上if(c==a||c==b)return 1;return fabs(cro(c-a,c-b))<=bt&&(c-a)*(c-b)<=bt;}bool operator<(const line&y)const{ //横坐标排序if(a!=y.a)return a<y.a;else return b<y.b;}
};

线段、直线相关函数

inline bool check0(line A,line B){//直-直有交(不重合)return fabs(cro(A.vecm(),B.vecm()))>bt;
}
inline bool check1(line A,line b){//直-段有交return cro(A.vecm(),b.a-A.a)*cro(A.vecm(),b.b-A.a)<=bt;
}
inline bool check2(line a,line b){//段-段有交(不平行)if(!check0(a,b))return 0;return check1(a,b)&&check1(b,a);
}
inline bool check3(line a,line b){//段-段有交if(a.ni(b.a)||a.ni(b.b)||b.ni(a.a)||b.ni(a.b))return 1;return check2(a,b);
}inline pv getcr0(line A,line B){//直-直求交(向量*比值法，交点可在线段外)if(!check0(A,B))return pv(inf,inf);double f=cro(B.a-A.a,A.b-A.a),g=cro(A.b-A.a,B.b-A.a);return (B.b-B.a)*(f/(f+g))+B.a;
}
inline pv getcr1(line a,line b){//段-段求交if(a.a==b.a||a.a==b.b)return a.a;if(a.b==b.a||a.b==b.b)return a.b;if(!check2(a,b))return pv(inf,inf);//无交或无法确定交点则返回infreturn getcr0(a,b);
}

三角形相关函数

inline double getS(pv A,pv B,pv C){//三角形面积(叉积法)return fabs(cro(B-A,C-A))/2;
}
inline double getS_(double a,double b,double c){//三角形面积Ⅱ(海伦公式)double p=(a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));
} 
inline pv getCT(pv A,pv B,pv C){//三角形重心return pv((A.x+B.x+C.x)/3,(A.y+B.y+C.y)/3);
}
inline pv getO(pv A,pv B,pv C){//三角形外心if(A==B)return (A+C)/2; //退化情况特判if(A==C||B==C)return (A+B)/2;pv a=(A+B)/2,b=(B+C)/2,n1=(A-B).GN(),n2=(B-C).GN();line l1=line(a,a+n1),l2=line(b,b+n2);return getcr0(l1,l2);
}

多边形相关函数

int n,m;
pv a[MAXN],b[MAXN];
//从a[n]中读入点集 
inline void getcon(){//点集转凸包 sort(a+1,a+1+n),m=0;for(int i=1;i<=n;i++){while(m>1&&cro(b[m]-b[m-1],a[i]-b[m-1])<=bt)m--;b[++m]=a[i];}for(int i=n-1,p=m;i>0;i--){while(m>p&&cro(b[m]-b[m-1],a[i]-b[m-1])<=bt)m--;b[++m]=a[i];}if(n>1)m--; //凸包(逆时针)输出至b[m] 
}
inline double polyS(){//求简单多边形面积(确保点为顺/逆时针) double S=0;for(int i=1;i<=n;i++)S+=cro(a[i],a[i%n+1])/2;return fabs(S);
}
inline pv polycenter(){//求简单多边形重心(确保点为顺/逆时针) pv r=pv(0,0);double sw=0,w;for(int i=1;i<=n;i++){w=cro(a[i]-pv(0,0),a[i%n+1]-pv(0,0));r=r+a[i]*w+a[i%n+1]*w,sw+=w;}r.x/=3*sw,r.y/=3*sw;return r;
}
inline bool insidep(pv x){//判断点是否在多边形内 for(int i=1;i<=n;i++)if(line(a[i],a[i%n+1]).ni(x))return 1;line b=line(x,pv(1e11+3,1e12+7));bool tot=0;for(int i=1;i<=n;i++)tot^=check2(line(a[i],a[i%n+1]),b);return tot;
}

伸展树Splay模板

struct splay{	//结构体int fa,h[2],a,siz,cnt;splay(){}splay(int A,int F){fa=F,h[0]=h[1]=0,a=A,siz=1,cnt=1;}
}t[MAXN];
//子树size，方便调用
#define lsum(x) (t[t[x].h[0]].siz)
#define rsum(x) (t[t[x].h[0]].siz+t[x].cnt)
int IN,root;
inline void update(int x){	//更新节点if(!x)return;t[x].siz=t[t[x].h[0]].siz+t[t[x].h[1]].siz+t[x].cnt;
}
inline bool ids(int x){return t[t[x].fa].h[1]==x;}//得到自己的儿子编号
inline void lin(int x,int y,bool f){	//连一条父子边（不更新）if(x)t[x].h[f]=y;if(y)t[y].fa=x;
}
inline void rott(int x){	//单旋if(!t[x].fa)return;bool d=ids(x),fd=ids(t[x].fa);int fa=t[x].fa,ff=t[fa].fa,sd=t[x].h[d^1];lin(fa,sd,d),lin(ff,x,fd),lin(x,fa,d^1);update(fa),update(x),update(ff);
}
inline void dospl(int x,int to=0){	//双旋到根或指定节点的儿子while(t[x].fa!=to){if(t[t[x].fa].fa!=to){if(ids(t[x].fa)==ids(x))rott(t[x].fa);else rott(x);}rott(x);}
}
inline int ins(int&x,int k){	//插入int fa=t[x].fa;bool d=ids(x);while(x&&t[x].a!=k)fa=x,d=t[x].a<k,x=t[x].h[t[x].a<k];if(!x)t[++IN]=splay(k,fa),t[fa].h[d]=x=IN;else t[x].cnt++,update(x);dospl(x);return x;
}
inline int del(int&rt,int k){	//删除int x=rt;while(x&&t[x].a!=k)x=t[x].h[t[x].a<k];if(!x)return rt;dospl(x),rt=x,t[x].cnt--,update(x);if(t[x].cnt)return rt;if(!t[x].h[1])return t[t[x].h[0]].fa=0,rt=t[x].h[0];int sf=t[x].h[1];while(t[sf].h[0])sf=t[sf].h[0];dospl(sf),rt=sf;lin(rt,t[x].h[0],0),update(rt);return rt;
}
inline int getrk(int&rt,int k){	//查找k的排名int res=0,x=rt;while(t[x].a!=k)res+=t[x].a<k?rsum(x):0,x=t[x].h[t[x].a<k];res+=lsum(x),dospl(x),rt=x;return res+1;
}
inline int getkr(int&rt,int k){	//查找排名为k的数int x=rt;while(lsum(x)>=k||rsum(x)<k){if(rsum(x)<k)k-=rsum(x),x=t[x].h[1];else x=t[x].h[0];}dospl(x),rt=x;return t[x].a;
}
inline int getpr(int&rt,int k){	//查找前缀int a=0,x=rt;k--;while(x&&t[x].a!=k){if(t[x].a<k)a=t[x].a,x=t[x].h[1];else x=t[x].h[0];}if(x)a=t[x].a;return a;
}
inline int getsf(int&rt,int k){	//查找后缀int b=0,x=rt;k++;while(x&&t[x].a!=k){if(t[x].a>k)b=t[x].a,x=t[x].h[0];else x=t[x].h[1];}if(x)b=t[x].a;return b;
}

分裂-合并简化 (大常数化) 版：

struct spl{int fa,h[2],a,siz;spl(){}spl(int A,int F){fa=F,h[0]=h[1]=0,a=A,siz=1;}
}t[MAXN];
int IN,root;//prepare
#define lsum(x) (t[t[x].h[0]].siz)
#define rsum(x) (t[t[x].h[1]].siz+1)
inline void update(int x){if(!x)return;t[x].siz=lsum(x)+rsum(x);
}
inline bool ids(int x){return t[t[x].fa].h[1]==x;}
inline void lin(int x,int y,bool f){if(x)t[x].h[f]=y;if(y)t[y].fa=x;}
inline void rott(int x){if(!t[x].fa)return;bool d=ids(x),fd=ids(t[x].fa);int fa=t[x].fa,ff=t[fa].fa,sd=t[x].h[d^1];lin(fa,sd,d),lin(ff,x,fd),lin(x,fa,d^1);update(fa),update(x),update(ff);
}
inline void dospl(int x,int to=0){while(t[x].fa^to){if(t[t[x].fa].fa^to){if(ids(x)==ids(t[x].fa))rott(t[x].fa);else rott(x);}rott(x);}
}
//split,merge
struct node{int x,y;node(){}node(int X,int Y){x=X,y=Y;}
};
inline node splii(int x,int k){//split by keyif(!x)return node(0,0);while(t[x].h[t[x].a<=k])x=t[x].h[t[x].a<=k];dospl(x);node res;if(t[x].a<=k)res=node(x,t[x].h[1]),t[t[x].h[1]].fa=0,t[x].h[1]=0,update(x);else res=node(t[x].h[0],x),t[t[x].h[0]].fa=0,t[x].h[0]=0,update(x);return res;
}
inline node spltt(int x,int k){//split by sizeif(!x||!k)return node(0,x);t[x].fa=0;int fk=k;while(t[x].h[lsum(x)<fk]){if(lsum(x)<fk)fk-=lsum(x)+1,x=t[x].h[1];else x=t[x].h[0];}dospl(x);node res;if(lsum(x)<k)res=node(x,t[x].h[1]),t[t[x].h[1]].fa=0,t[x].h[1]=0,update(x);else res=node(t[x].h[0],x),t[t[x].h[0]].fa=0,t[x].h[0]=0,update(x);return res;
}
inline int mergg(int x,int y){if(!x||!y)return x^y;t[x].fa=t[y].fa=0;while(t[x].h[1])x=t[x].h[1];dospl(x),lin(x,y,1),update(x);return x;
}

手写可并堆

模板来自关于可并二叉堆的讲解

左偏树

inline bool cmp(int a,int b){return a>b;}//设置比较函数（小根堆）
inline void update(int x){	//维护左偏性if(t[t[x].sn[0]].dis<t[t[x].sn[1]].dis)swap(t[x].sn[0],t[x].sn[1]);t[x].dis=t[t[x].sn[1]].dis+1;
}
inline int merg(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);t[x].sn[1]=merg(t[x].sn[1],y);update(x);return x;
}

斜堆

inline bool cmp(int a,int b){return a>b;}
inline int merg(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);t[x].sn[1]=merg(t[x].sn[1],y);swap(t[x].sn[0],t[x].sn[1]);return x;
}

随机堆

inline bool cmp(ll a,ll b){return a>b;}
inline int mergh(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);bool o=rand()&1;if(!t[x].sn[o^1])o^=1;t[x].sn[o]=mergh(t[x].sn[o],y);return x;
}

inline bool cmp(ll a,ll b){return a>b;}
mt19937 Rand(*new(int));
inline int mergh(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);int o=Rand()&1;if(!t[x].sn[o^1])o^=1;t[x].sn[o]=mergh(t[x].sn[o],y);return x;
}

可持久化

随机堆的可持久化

inline bool cmp(ll a,ll b){return a>b;}
inline int mergh(int x,int y){if(!x||!y)return x^y;if(cmp(t[x].val,t[y].val))swap(x,y);int o=rand()&1;if(!t[x].sn[o^1])o^=1;int res=++IN;t[res]=t[x];t[res].sn[o]=mergh(t[x].sn[o],y);return res;
}

Nimber乘法及系列运算

64位无符号Nimber

#define exp e_x_p   //恶心！居然是关键字！
bool pre_ok;
const uns ll nimg=258,nod=(1<<16)-1;
uns ll ln[1<<16],exp[1<<16];inline uns ll nimul(uns ll a,uns ll b){//Nimber-multiplicationif(a<2||b<2)return a*b;if(pre_ok&&a<=nod&&b<=nod)return exp[(ln[a]+ln[b])%nod];int cp=32;while(cp>1&&a<(1ull<<cp)&&b<(1ull<<cp))cp>>=1;uns ll ah=a>>cp,a1=a^(ah<<cp),bh=b>>cp,b1=b^(bh<<cp);uns ll g=nimul(a1,b1);return nimul(nimul(ah,bh),1ull<<(cp-1))^g^((nimul(ah^a1,bh^b1)^g)<<cp);
}inline void init(){//0~65535以内预处理exp[0]=1,exp[1]=nimg;for(int i=2;i<nod;i++)exp[i]=nimul(exp[i-1],nimg);for(int i=0;i<nod;i++)ln[exp[i]]=i;pre_ok=1;
}inline uns ll ksm(uns ll a,uns ll b){//Nimber快速幂uns ll res=1;for(;b;b>>=1,a=nimul(a,a))if(b&1)res=nimul(res,a);return res;
}inline uns ll getinv(uns ll a){//Nimber求逆元return ksm(a,0ull-2);
}

（转置原理）多项式多点求值

解析
全家桶都没上，直接来多点求值了。

#define ll long long
const ll MOD=998244353;
#define arr vector<ll>
inline ll ksm(ll a,ll b,ll mo){//快速幂ll res=1;for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;return res;
}
//NTT begin
#define g 3ll
int rev[MAXN<<1];//MAXN要设得足够大
ll omg[MAXN<<1];
inline int NTT(arr&a,int inv){int n=a.size(),bit=1;while((1<<bit)<n)bit++;n=(1<<bit);if((int)a.size()<n)a.resize(n);for(int i=0;i<n;i++){rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));if(i<rev[i])swap(a[i],a[rev[i]]);}ll tmp,x,y;omg[0]=1;for(int m=1,mi=(MOD-1)>>1,om;m<n;m<<=1,mi>>=1){tmp=ksm(g,inv<0?MOD-1-mi:mi,MOD),om=0;for(int i=1;i<m;i++)omg[i]=omg[i-1]*tmp%MOD;for(int i=0;i<n;i+=(m<<1),om=0)for(int j=i;j<i+m;j++,om++)x=a[j],y=a[j+m]*omg[om]%MOD,a[j]=(x+y)%MOD,a[j+m]=(x-y+MOD)%MOD;}if(inv<0){ll iv=ksm(n,MOD-2,MOD);for(int i=0;i<n;i++)a[i]=a[i]*iv%MOD;}return n;
}
#undef g
//NTT end
//pre-functions begin
inline void getinv(arr&a){//多项式求逆（不依赖多项式乘法函数，减小常数）arr f,h;int n=a.size(),m=1,N=0;h.push_back(ksm(a[0],MOD-2,MOD));while(m<n){m<<=1,f=a,f.resize(m);f.resize(m<<1),h.resize(m<<1);N=NTT(f,1),NTT(h,1);for(int i=0;i<N;i++)h[i]=(MOD+2-f[i]*h[i]%MOD)*h[i]%MOD;NTT(h,-1),h.resize(m);}a=h,a.resize(n);
}
inline arr mul(arr a,arr b){//返回新数组式多项式乘法int n=a.size(),m=b.size();a.resize(n+m-1),b.resize(n+m-1);int N=NTT(a,1);NTT(b,1);for(int i=0;i<N;i++)a[i]=a[i]*b[i]%MOD;NTT(a,-1),a.resize(n+m-1);return a;
}
inline arr demul(arr a,arr b){//减法卷积int n=a.size(),m=b.size();if(n<m)return arr();reverse(b.begin(),b.end());a.resize(n+m-1),b.resize(n+m-1);int N=NTT(a,1);NTT(b,1);for(int i=0;i<N;i++)a[i]=a[i]*b[i]%MOD;NTT(a,-1);for(int i=0;i<=n-m;i++)a[i]=a[i+m-1];a.resize(n-m+1);return a;
}
//pre-functions end
//segment tree begin
arr t[MAXN<<2];
ll ans[MAXN];
inline void build(int x,int l,int r,const arr&a){//求Tif(l==r){t[x].clear(),t[x].push_back(1);t[x].push_back((MOD-a[l])%MOD);return;}int mid=(l+r)>>1;build(x<<1,l,mid,a),build(x<<1|1,mid+1,r,a);t[x]=mul(t[x<<1],t[x<<1|1]);
}
inline void godown(int x,int l,int r,arr F){//求转置F'if(l==r){ans[l]=F[0];return;}int mid=(l+r)>>1;godown(x<<1,l,mid,demul(F,t[x<<1|1]));godown(x<<1|1,mid+1,r,demul(F,t[x<<1]));
}
//segment tree end
inline void solve(arr&b,arr&a){int n=max(b.size(),a.size());b.resize(n<<1),a.resize(n);build(1,0,n-1,a);getinv(t[1]);godown(1,0,n-1,demul(b,t[1]));
}

奇素数二次剩余

到（6）了才写二次剩余，我果然还是太菜了

inline ll ksm(ll a,ll b,ll mo){//快速幂ll res=1;for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;return res;
}
inline ll sqrtmod(ll a,ll MOD){static mt19937_64 E(*new(int));ll ler=ksm(a,(MOD-1)>>1,MOD);if(!ler)return 0;if(ler^1)return -1;ll b=E()%MOD;while(ksm(b,(MOD-1)>>1,MOD)==1)b=E()%MOD;int t=0;ll s=MOD-1;while(~s&1)s>>=1,t++;ll x=ksm(a,(s+1)>>1,MOD),iva=ksm(a,MOD-2,MOD);for(int i=t-1;i>0;--i){ll w=ksm(iva*x%MOD*x%MOD,1ll<<(i-1),MOD);if(w==1)continue;x=x*ksm(b,s<<(t-i-1),MOD)%MOD;}return min(x,MOD-x);
}

Min_25筛模板

ll n,pr[MAXN/10];
bool nop[MAXN];
int le;
inline void ad(ll&a,ll b){a+=b;if(a>=MOD)a-=MOD;}
int id[MAXN],di[MAXN],m;
ll B,w[MAXN],pre[MAXN];
ll g[MAXN];
inline int ID(ll x){return x<=B?id[x]:di[n/x];}inline ll F(ll p,ll e){//求f(p^e)...
}
inline ll sumF(ll x){//求完全积性假函数的前缀和（去掉1）...
}
inline void prepare_Min25(){B=sqrt(n);nop[0]=nop[1]=1;for(int a=2;a<=B;a++){//线性筛if(!nop[a])pr[++le]=a;for(int i=1,u;i<=le;i++){u=pr[i]*a;if(u>B)break;nop[u]=1;if(a%pr[i]==0)break;}}m=0,pre[0]=0;for(int i=1;i<=le;i++)pre[i]=(pre[i-1]+F(pr[i],1))%MOD;for(ll i=1,la,v;i<=n;i=la+1){//预处理映射、赋初值v=n/i,la=n/v;if(v<=B)id[v]=++m;else di[n/v]=++m;w[m]=v,g[m]=sumF(v);}for(int i=1;i<=le;i++){//亚线性递推求gll z=pr[i]*pr[i];for(int j=1;j<=m;j++){if(z>w[j])break;ad(g[j],MOD - (g[ID(w[j]/pr[i])] - pre[i-1]+MOD) * F(pr[i],1) %MOD);}}//如果有多个g用同样的方法求
}
inline ll askf(ll x,int i){//递归求fif(x<2||pr[i]>x)return 0;ll res=(g[ID(x)]-pre[i-1]+MOD)%MOD;for(int j=i;j<=le;j++){if(pr[j]*pr[j]>x)break;for(ll e=pr[j],k=1;e*pr[j]<=x;e*=pr[j],k++)ad(res,F(pr[j],k)*askf(x/e,j+1)%MOD),ad(res,F(pr[j],k+1));}return res;
}
ll f[MAXN];
void getf(){//递推求ffor(int i=1;i<=m;i++)f[i]=g[i];for(int i=le;i>0;i--){ll z=pr[i]*pr[i];for(int j=1;j<=m;j++){if(z>w[j])break;ll h=pr[i],to;for(int e=1;(to=h*pr[i])<=w[j];e++,h=to)f[j]+=(f[ID(w[j]/h)]-pre[i])*F(pr[i],e)+F(pr[i],e+1);}}
}

久等了！动态树LCT模板

参考这道题的实现吧

struct spl{int fa,h[2],a,s;bool lz;spl(){}spl(int A){fa=h[0]=h[1]=0,a=s=A,lz=0;}
}t[MAXN];
inline void cover(int x){if(!x)return;t[x].lz^=1,swap(t[x].h[0],t[x].h[1]);
}
inline void pushd(int x){if(t[x].lz)cover(t[x].h[0]),cover(t[x].h[1]),t[x].lz=0;
}
inline void update(int x){t[x].s=t[x].a^t[t[x].h[0]].s^t[t[x].h[1]].s;
}
inline bool sd(int x){return x==t[t[x].fa].h[1];}
inline bool isroot(int x){return x!=t[t[x].fa].h[sd(x)];}
inline void lin(int x,int y,bool f){if(x)t[x].h[f]=y;if(y)t[y].fa=x;}
inline void rott(int x){if(!t[x].fa||isroot(x))return;bool f1=sd(x),f2=sd(t[x].fa);int fa=t[x].fa,ff=t[fa].fa,sn=t[x].h[f1^1];if(isroot(fa))t[x].fa=ff;else lin(ff,x,f2);lin(fa,sn,f1),lin(x,fa,f1^1);update(fa),update(x),update(ff);
}
inline void pushtag(int x){if(!isroot(x))pushtag(t[x].fa);pushd(x);
}
inline void splay(int x){pushtag(x);while(!isroot(x)){if(!isroot(t[x].fa)){if(sd(x)==sd(t[x].fa))rott(t[x].fa);else rott(x);}rott(x);}
}
inline void access(int x){for(int y=0;x;y=x,x=t[x].fa)splay(x),t[x].h[1]=y,update(x);
}
inline void makeroot(int x){access(x),splay(x),cover(x);
}
inline void LINK(int x,int y){if(x==y)return;makeroot(x),access(y),splay(y);if(t[x].fa==0)lin(y,x,1),update(y);
}
inline void CUT(int x,int y){makeroot(x),access(x),splay(y);if(!t[y].h[0]&&t[y].fa==x)t[y].fa=0;
}
inline int query(int x,int y){makeroot(x),access(y),splay(x);return t[x].s;
}

Lyndon 分解

void Lyndon(char*s,int n){for(int i=1,j,k;i<=n;){j=i;for(k=i+1;k<=n&&s[j]<=s[k];k++)j=s[j]<s[k]?i:j+1;for(;i<=j;i+=k-j)printf("[%d,%d]\n",i,i+k-j-1);		//输出Lyndon串所在区间}
}

Miller-Rabin素数测试

#define ll long long
#define lll __int128
const lll E=1;
ll ksml(ll a,ll b,const ll&mo){//快速幂ll res=1;for(;b;b>>=1,a=E*a*a%mo)if(b&1)res=E*res*a%mo;return res;
}
mt19937_64 rng(1145141);
bool MillerRabin(const ll&p){if(p==2||p==3||p==5||p==7||p==11)return 1;if((~p&1)||!(p%3)||!(p%5)||!(p%7)||!(p%11))return 0;ll k=p-1,m=0;while(~k&1)k>>=1,m++;for(int cnt=35;cnt--;){ll a=ksml(rng()%(p-3)+2,k,p);if(a==1||a==p-1)continue;for(int t=0,tg=0;t<m;t++){a=E*a*a%p;if(!tg&&a==1)return 0;if(a==p-1)tg=1;}if(a!=1)return 0;}return 1;
}

Pollard-Rho质因数分解

相关函数定义见上面Miller-Rabin

ll gcd(ll a,ll b){for(;b;a%=b,swap(a,b));return a;}
ll PollardRho(const ll&n){while(1){ll d=1,x=rng()%(n-1)+1,y=x,c=rng()%(n-1)+1;for(int len=1,lim=127;;len<<=1,x=y,lim=127){bool hc=0;for(int cnt=len;cnt--;){y=(E*y*y+c)%n,d=E*d*(x-y+n)%n,lim--;if(x==y||!d){hc=1;break;}if(!lim){d=gcd(d,n),lim=127;if(d>1)return d;}}if(hc)break;d=gcd(d,n);if(d>1)return d;}}return 1919810;
}
unordered_map<ll,int>mp;//存质因子及其指数
void findz(ll n,int cnt){if(n==1)return;if(MillerRabin(n)){mp[n]+=cnt;return;}ll d=PollardRho(n);int cg=0;while(n%d==0)n/=d,cg++;findz(d,cg*cnt),findz(n,cnt);
}

Always to be continued(持续更新中)…