组合计数
逆元预处理
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;
}
数据结构
树状数组
还没找
线段树