模板库

组合计数

逆元预处理

	lx[0]=1;lx[1]=1;for(int i=2;i<N;i++) lx[i]=lx[i-1]*i%mod;inv[N-1]=ksm(lx[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1])*(i+1)%mod;

快速幂

int ksm(int x,int y) {int t=1;while(y){if(y&1)t=t*x%mod;x=x*x%mod;y>>=1;}return t;}

组合数

int C(int x,int y) {if(x<y) return 0;return lx[x]*inv[y]%mod*inv[x-y]%mod;}

lucas

int lucas(int x,int y) {if(x<mod&&y<mod) return C[x][y];return lucas(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;
}

数据结构

树状数组

还没找

线段树