简单记录

基本计数方法

容斥原理

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

排列问题

全排列
$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!)$ $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)$

递推关系

斐波那契（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)]$

数论

一. 基本概念

素数

//筛素数
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;
}

欧几里得算法

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);}
}

模算数

//返回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;
}

欧拉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);
		}
}

剩余系

//计算模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)$

模板

尺取法，滑动窗口

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++]);
}

归并排序，统计逆序对

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];
	}
}

快速幂

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

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;
}

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

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;
}

快速排序

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);
	}
}

找最长递增子序列（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;

斯特灵公式 (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;

回文子串 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;
}

YU-NO

基本计数方法

数论

其他

模板

每个程序员都应该知道的基础数论