常用模板库

数学、数论

namespace math{
	int mu[MAXN],prime[MAXN];
	bitset<MAXN> is_prime;
	int MOD;
	int frac[MAXN];
	int qpow(int a,int b){
		if(b==0) return 1;
		if(b==1) return a;
		int k = qpow(a,b>>1);
		k*=k;k%=MOD;
		if(b&1) k*=a;k%=MOD;
		return k;
	}
	int exgcd(int a,int b,int &x,int &y){
		if(b==0){
			x = 1;y = 0;
			return a;
		}
		int t = exgcd(b,a%b,x,y);
		int g = x;
		x = y;
		y = g-a/b*y;
		return t;
	}
	int inv(int a){
		return qpow(a,MOD-2);
	}
	int ex_inv(int a){
		int x,y;
		exgcd(a,MOD,x,y);
		return (x%m+m)%m;
	}
	int C(int n,int m){
		if(n<m) return 0;
		return frac[n]*ex_inv(frac[m]*frac[n-m]%MOD)%MOD;
	}
	int get(int n,int m){
		return C(m+n-1,m);
	}
	void frac_init(){
		frac[0] = 0;
		for(int i = 1;i<MAXN;i++){
			frac[i] = frac[i-1]*i;
			frac[i]%=MOD;
		}
	}
	int lowbit(int k){
		return k&(-k);
	}
	int bit(int k){
		int sum = 0;
		while(k){
			sum ++;
			k -= lowbit(k);
		}
		return sum;
	}
	int log2(int k){
		for(int i = 0;i<=64;i++){
			int p = 1;
			if(p<<i==k) return i;
		}
		return 0;
	}
	void Euler_sieve(){
		mu[1] = 1;
		for(int i = 2;i<MAXN;i++){
			if(!is_prime[i]){
				prime[++prime[0]] = i;
				mu[i] = -1;
			}
			for(int j = 1;j<=prime[0]&&i*prime[j]<MAXN;j++){
				is_prime[i*prime[j]] = 1;
				if(i%prime[j]==0){
					mu[i*prime[j]] = 0;
					break;
				}else{
					mu[i*prime[j]] = -mu[i];
				}
			}
		}
	}
}