__int128

#include<cstdio>
inline __int128 read(){
	__int128 s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
inline void write(__int128 x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

快速幂模板

int pows(int a,int b){
	int s=1,p=a;
  	while(b){
  		if(b&1)s=s*p;
    	p*=p;
		b>>=1;
 	}
  	return s;
}

lucas模板

int lucas(int x,int y,int p){
    if(!y)return 1;
    return C(x%p,y%p,p)*lucas(x/p,y/p,p)%p;
}

排列组合公式法模板

void init(){
	int i;
	fac[0]=1;
	for(i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
	inv[100000]=pows(fac[100000],mod-2);
	for(i=100000;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
int C(int n,int m){
	if(m>n||m<0)return 0;
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

组合数的各种算法

高精度加减乘除模板

线段树详解