基本计数方法

1. 容斥原理

• $|A∪B∪C|=|A|+|B|+|C|+|B|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|$

2. 排列问题

• 全排列 $P（n,k)=n(n-1)(n-2)...(n-k+1)=n!/(n-k)!$
• 组合数 $C（n,k)=P(n,k)/P(k,k)=n!/((n-k)!k!)$
  • 性质 1： $C(n,0)=C(n,n)=1$
  • 性质 2： $C(n,k)=C(n,n-k)$
  • 性质 3： $C(n,k)+C(n,k+1)=C(n+1,k+1)$
  • 性质 4： $C(n,k+1)=C(n,k)*(n-k)/(k+1)$

3. 递推关系

• 斐波那契（Fibonacci）数列 $f(n)=f(n-1)+f(n-2),f(1)=f(2)=1$
• 卡特兰（Catalan）数列 $f(n)=f(2)f(n-1)+f(3)f(n-2)+...+f(n-1)f(2),f(2)=f(3)=1,[f(k)f(n-k-1)]$

数论

一. 基本概念

1. 素数

//筛素数
const int maxn=10000000+10;
const int maxp=700000;
int vis[maxn];
int prime[maxp];
void sieve(int n){
	int m=(int)sqrt(n+0.5);
	memset(vis,0,sizeof(vis));
	for(int i=2;i<=m;i++) if(!vis[i])//0为素数
		for(int j=i*i;j<=n;j+=i) vis[j]=1;
}
//生成素数表
int gen_prime(int n){
	sieve(n);
	int c=0;
	for(int i=2;i<=n;i++) if(!vis[i])
		prime[c++]=i;
	return c;
}

2. 欧几里得算法

typedef long long ll;
ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}
void gcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){d=a;x=1;y=0;}
	else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

3. 模算数

//返回ab mod n 要求0<=a,b<n
ll mul_mod(ll a,ll b,ll n){
	return a*b%n;
}
//返回a^p mod n,要求0<=a<n
ll pow_mod(ll a,ll p,ll n){
	if(p==0) return 1;
	ll r=pow_mod(a,p/2,n);
	r=r*r%n;
	if(p%2==1) r=r*a%n;
	return r;
}

4. 欧拉phi函数（phi（x）表示等于不超过x且和x互素的整数个数） $φ(x)=n(1-1/p1)(1-1/p2)...(1-1/pk)$

//计算欧拉phi函数
int euler_phi(int n){
	int m=(int)sqrt(n+0.5);
	int ans=n;
	for(int i=2;i<=m;i++) if(n%i==0){
		ans=ans/i*(i-1);
		while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);
}
//用类似筛法的方法计算phi（1），phi（2），...，phi（n）
int phi[maxn];
void phi_table(int n){
	for(int i=2;i<=n;i++) phi[i]=0;
	phi[1]=1;
	for(int i=2;i<=n;i++) if(!phi[i])
		for(int j=i;j<=n;j+=i){
			if(!phi[j]) phi[j]=j;
			phi[j]=phi[j]/i*(i-1);
		}
}

5. 剩余系

//计算模n下a的逆 如果不存在逆，返回-1
ll inv(ll a,ll n){
	ll d,x,y;
	gcd(a,n,d,x,y);
	return d==1?(x+n)%n:-1;
}

其他

• 模拟，贪心，二分，三分，动态规划，容斥原理
• 四舍五入：$floor(pos + 0.5) OR (x+s-1)/s$
• 错排公式：$D(n)=(n-1)(D(n-2)+D(n-1))$
• 判断凹凸多边形：$p1(x1,y1),p2(x2,y2),p3(x3,y3)$ $s(p1,p2,p3)=(x1-x3)(y2-y3)-(x2-x3)(y1-y3)$ 如果s>0则说明这3个点时是按照逆时针的顺序，如果是s<0则说明连接这3个点是按照顺时针的顺序。
• 三角形面积: $|a×b|=|a||b|sin(θ)$ $S=1/2|a×b|$ $p1(x1,y1),p2(x2,y2),p3(x3,y3)$ $v1(x2-x1,y2-y1),v2(x3-x2,y3-y2)$ $v1(x1,y1),v2(x2,y2)$ $a×b=(x1y2-x2y1)$

模板

1. 尺取法，滑动窗口

set<int> s;
while (r<n){
	while (r<n&&!s.count(a[r]))
		s.insert(a[r++]);
	m=max(m,r-l);
	s.erase(a[l++]);
}

2. 归并排序，统计逆序对

exp1：
int A[maxn], T[maxn];
__int64 cnt=0,n;
void merge(int *arr,int *tmp,int l, int mid,int r){
	int i=l, j=mid+1, k=l;
	while (i<=mid&&j<=r){
		if (arr[i]<=arr[j]) tmp[k++]=arr[i++];
		else{tmp[k++]=arr[j++];cnt+=mid-i+1;}
	}
	while (i!=mid+1) tmp[k++]=arr[i++];
	while (j!=r+1) tmp[k++]=arr[j++];
	for (i=l;i<=r; i++) arr[i]=tmp[i];
}
void mergesort(int *arr, int *tmp, int l, int r){
	if (l<r){
		int mid=(l+r)/2;
		mergesort(arr,tmp,l,mid);
		mergesort(arr,tmp,mid+1,r);
		merge(arr,tmp,l,mid,r);
	}
}
exp2:
void mergesort(int *A,int *T,int x,int y){
	if(y-x>1){
		int m=(x+y)/2;
		mergesort(A,T,x,m);
		mergesort(A,T,m,y);
		int i=x,j=m,k=i;
		while(i<m||j<y){
			if(j>=y||(i<m&&a[i]<=a[j])) T[k++]=A[i++];
			else {T[k++]=A[j++];cnt=m-p;}
		}
		for(k=0;k<y;k++) A[k]=T[k];
	}
}

3. 快速幂

int pow(int a,int b){
	int r=1,base=b;
	while(b){
		if(b&1) r*=base;
		base*=base;
		b>>=1;
	}
	return r;
}

4. GCD/LCM

int gcd(int a,int b){
	if(a==0) return b;
	else if(b==0) return a;
	else if(a%2==0&&b%2==0) return 2*gcd(a>>1,b>>1);
	else if(a%2==0) return gcd(a>>1,b);
	else if(b&2==0) return gcd(a,b>>1);
	else return gcd(abs(a-b),min(a,b));
}
int gcd(int a,int b){
	return b==0？a：gcd(b,a%b)；
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

5. 分解质因数，约数个数定理

int apx(ll n){
	ll m=(int)sqrt(n+0.5);
	int sum=1;
	for (ll i=2;i<=m;++i){
		int p=0;
		while (n%i==0) {p++;n/=i;}
		if (p>0) sum*=(p+1);
	}
	if (t>1) sum*=2;
	return sum;
}

6. 快速排序

void quicksort(int *A,int x,int y){
	if(x<y){
		int i=x,j=y,k=A[x];
		while(i<j){
			while(i<j&&A[j]>=k) j--;
			if(i<j) A[i++]=A[j];
			while(i<j&&A[i]<=k) i++;
			if(i<j) A[j--]=A[i];
			a[i]=k;
		}
		quicksort(A,x,i-1);
		quicksort(A,j+1,y);
	}
}

7. 找最长递增子序列（LIS）

PII v[5050];
int a[5050];
//input
sort(v, v + d);
FORi(i, 0, d+1) a[i] = inf;
//找最长递增子序列（LIS）
FORi(i, 0, d) *lower_bound(a, a + d + 1, v[i].second) = v[i].second;//upper_lound为最长不下降子序列
cout << distance(a,lower_bound(a, a + d + 1, inf)) << endl;

8. 斯特灵公式 (Stirling's approximation)

   $n! \approx \sqrt{2\pi n}, \left(\frac{n}{e}\right)^{n}.$

len=(n*log(n)-n+0.5*log(2*n*PI))/(log(10))+1;

9. 回文子串 Manacher 算法

char s[110200], sn[220400];
int p[220400];
int Manacher()
{
	int len=strlen(s);
	sn[0] = '$';
	sn[1] = '#';
	int j = 2;
	for (int i = 0; i < len; i++)
	{
		sn[j++] = s[i];
		sn[j++] = '#';
	}
	sn[j] = '\0';
	int mxlen = -1, mid, mx = 0;
	for (int i = 1; i < j; i++)
	{
		p[i] = i < mx ? min(p[2 * mid - i], mx - i) : 1;
		while (sn[i - p[i]] == sn[i + p[i]]) p[i]++;
		if (mx < i + p[i]) { mid = i; mx = i + p[i]; }
		mxlen = max(mxlen, p[i] - 1);
	}
	return mxlen;
}