算法竞赛笔记

快速幂

$\Theta(\log n)$

int fp(const int a,const int b,const int m){
	int ret=1;
	a%=m;
	while(b!=0){
		if((b&1)==1)
			ret=(ret*a)%m;
		a=(a*a)%m,
		b>>=1;
	};
	return ret;
};

龟速乘

$O(\log m)$

int sm(const int a,const int b,const int m){
	int ret=0;
	while(b!=0){
		if((b&1)==1)
			ret=(ret+a)%m;
		a=(a<<1)%m,
		b>>=1;
	};
	return ret;
}; 

快速排序

$\Omega(n\log n)\qquad\Theta(n\log n)\qquad O(n^2)$

int a[N+1];
void qs(const int begin,const int end){
	int k=a[(begin+end)>>1],left=begin,right=end;
	while(left<=right){
		while((a[left]<t)&&(left<end))
			left++;
		while((a[right]>t)&&(right>begin))
			right--;
		if(left<=right)
			a[left]^=a[right]^=a[left]^=a[right],
			left++,
			right--;
	};
	if(left<end)
		qs(left,end);
	if(right>begin)
		qs(begin,right);
	return void();
};

差分

int n,m,a[N+1],t1,t2,t3,f[N+1];
scanf("%d%d",&n,&m);
for(register int i=0;i<n;i++)
	scanf("%d",&a[i]);
for(register int i=0;i<m;i++){
	scanf("%d%d%d",&t1,&t2,&t3);
	f[t1]+=t3,
	f[t2+1]-=t3;
};
for(register int i=1;i<n;f[i]+=f[i-1],i++);
for(register int i=0;i<n;i++)
	printf("%d ",a[i]+f[i]);

离散化

unique:$O(n)$
lower_bound:$O(\log n)$

memcpy(b,a,sizeof(a));
sort(b+1,b+n+1);
m=unique(b,b+n+1)-b-1;
for(register int i=1;i<=n;i++)
	printf("%d ",lower_bound(b+1,b+m+1,a[i])-b);

前缀和

int n,m,a[N+1],x,y;
scanf("%d%d",&n,&m);
for(register int i=0;i<n;i++)
	scanf("%d",&a[i]);
for(register int i=1;i<n;a[i]+=a[i-1],i++);
for(register int i=0;i<m;i++){
	scanf("%d%d",&x,&y);
	printf("%d\n",a[y]-a[x-1]);
};

高精度

const int MAXN=...;
struct bignum{
	int len,s[MAXN];
	inline bignum(void){
		len=1;
		memset(s,0,sizeof(s));
		return;
	};
	bignum operator=(const char* num){
		len=strlen(num);
		for(register int i=0;i<len;i++)
			s[i]=num[len-i-1]-'0';
		return *this;
	};
	inline bignum operator=(const int num){
		char a[MAXN];
		sprintf(a,"%d",num);
		*this=a;
		return *this;
	};
	inline bignum(const int num){
		*this=num;
		return;
	};
	inline bignum(const char* num){
		*this=num;
		return;
	};
	bignum operator+(const bignum &a){
		bignum c;
		int x=0;
		c.len=max(len,a.len)+1;
		for(register int i=0;i<c.len;i++)
			c.s[i]=s[i]+a.s[i]+x,
			x=c.s[i]/10,
			c.s[i]%=10;
		if(c.s[c.len-1]==0)
			c.len--;
		return c;
	};
	inline bignum operator+=(const bignum &a){
		*this=*this+a;
		return *this;
	};
	bignum operator*(const bignum &a){
		bignum c;
		c.len=len+a.len;
		for(register int i=0;i<len;i++)
			for(register int j=0;j<a.len;j++)
				c.s[i+j]+=s[i]*a.s[j],
				c.s[i+j+1]+=c.s[i+j]/10,
				c.s[i+j]%=10;
		if(c.s[c.len-1]==0)
			c.len--;
		return c;
	};
	inline bignum operator*=(const bignum &a){
		*this=*this*a;
		return *this;
	};
	bool operator<(const bignum &x)const{
		if(len!=x.len)
			return len<x.len;
		for(register int i=len-1;i>=0;i--)
			if(s[i]!=x.s[i])
				return s[i]<x.s[i];
		return false;
	};
	inline bool operator>(const bignum &x)const{
		return x<*this;
	};
	inline bool operator<=(const bignum &x)const{
		return !(*this>x);
	};
	inline bool operator>=(const bignum &x)const{
		return !(*this<x);
	};
	inline bool operator==(const bignum &x)const{
		return !((*this<x)||(*this>x));
	};
	inline bool operator!=(const bignum &x)const{
		return (*this<x)||(*this>x);
	};
};
ostream& operator<<(ostream &out,const bignum &num){
	for(register int i=num.len-1;i>=0;i--)
		cout<<num.s[i];
	return out;
};
inline istream& operator>>(istream &in,bignum &a){
	char num[MAXN];
	in>>num;
	a=num;
	return in;
};

莫队算法

$O(n^{\frac{3}{2}})$

struct data{
    int l,r,id;
}qst[100001];
inline bool cmp(const data a,const data b){
    return (a.l/blck)==(b.l/blck)?a.r<b.r:a.l<b.l;
};
inline void add(const int k){
    if(++cnt[a[k]]==1)
        ans++;
    return void();
};
inline void dec(const int k){
    if(--cnt[a[k]]==0)
        ans--;
    return void();
};
int main(void){
    scanf("%d%d",&n,&q);
    blck=sqrt(n),
    l=1;
    for(register int i=1;i<=n;a[i++]=read());
    for(register int i=1;i<=q;i++)
        qst[i].l=read(),
        qst[i].r=read(),
        qst[i].id=i;
    sort(qst+1,qst+q+1,cmp);
    for(register int i=1;i<=q;i++){
        while(l<qst[i].l)
            dec(l++);
        while(l>qst[i].l)
            add(--l);
        while(r<qst[i].r)
            add(++r);
        while(r>qst[i].r)
            dec(r--);
        if(ans==qst[i].r-qst[i].l+1)
            tag[qst[i].id]=true;
    };
    for(register int i=1;i<=q;i++)
        if(tag[i]==true)
            printf("Yes\n");
        else
            printf("No\n");
    return 0;
};

分块

$\Omega(1)\qquad O(\sqrt n)$

inline bool cmp(const int a,const int b){
	return a<b;
};
void reset(const int p){
	for(register int i=l[pos[p]];i<=r[pos[p]];i++)
		tmp[i]=a[i];
	sort(tmp+l[pos[p]],tmp+r[pos[p]]+1,cmp);
	return void();
};//修改后根据a重新对tmp排序
void modify(const int x,const int y,const int v){//x~y加上v
	if(pos[x]==pos[y]){
		for(register int i=x;i<=y;i++)
			a[i]+=v;
		reset(x);
		return void();
	};
	for(register int i=x;i<=r[pos[x]];i++)
		a[i]+=v;
	for(register int i=l[pos[y]];i<=y;i++)
		a[i]+=v;
	reset(x);
	reset(y);
	for(register int i=pos[x]+1;i<pos[y];i++)
		add[i]+=v;
	return void();
};
int fnd(const int p,const int v){//p所在块中>=v个数
	int tl=l[p],tr=r[p],mid=0;
	while(tl<=tr){
		mid=(tl+tr)>>1;
		if(tmp[mid]<v)
			tl=mid+1;
		else
			tr=mid-1;
	};
	return r[p]-tl+1;
};
int query(const int x,const int y,const int v){//统计x~y中>=v的个数
	int cnt=0;
	if(pos[x]==pos[y]){
		for(register int i=x;i<=y;i++)
			if(a[i]+add[pos[x]]>=v)
				cnt++;
		return cnt;
	};
	for(register int i=x;i<=r[pos[x]];i++)
		if(a[i]+add[pos[i]]>=v)
			cnt++;
	for(register int i=l[pos[y]];i<=y;i++)
		if(a[i]+add[pos[i]]>=v)
			cnt++;
	for(register int i=pos[x]+1;i<pos[y];i++)
		cnt+=fnd(i,v-add[i]);
	return cnt;
};
int main(void){
	scanf("%d%d",&n,&q);
	for(register int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		tmp[i]=a[i];//tmp排序后数组 a原数组
	};
	blk=sqrt(n),
	t=n/blk;
	for(register int i=1;i<=t;i++)
		l[i]=(i-1)*blk+1,
		r[i]=i*blk;
	if(r[t]<n)
		l[t+1]=r[t]+1,
		r[++t]=n;
	for(register int i=1;i<=t;i++)
		for(register int j=l[i];j<=r[i];j++)
			pos[j]=i;
	for(register int i=1;i<=t;i++)
		sort(tmp+l[i],tmp+r[i]+1,cmp);
	for(register int i=1;i<=q;i++){
		scanf("%s%d%d%d",&opr,&t1,&t2,&t3);
		switch(opr[0]){
			case 'M':
				modify(t1,t2,t3);
				break;
			case 'A':
				printf("%d\n",query(t1,t2,t3));
				break;
			default:
				break;
		};
	};
	return 0;
};

尺取法

最长子区间和

l=r=1,
sum=0,
ans=n+1;
while(true){
	while((r<=n)&&(sum<s))
		sum+=a[r++];
	if(sum<s)
		break;
	ans=min(ans,r-l),
	sum-=a[l++];
};
if(ans==n+1)
	printf("0\n");
else
	printf("%d\n",ans);

三分法

单峰函数极值

const double eps=1e-(N-2);
double f(const double k){
	double sum=0;
	for(register int i=0;i<=n+1;i++)
		sum=sum*k+a[i];
	return sum;
};//a系数
while(r-l>eps){
	lmid=l+(r-l)/3,
	rmid=r-(r-l)/3;
	if(f(lmid)<=f(rmid))
		l=lmid;
	else
		r=rmid;
};
printf("%.5lf\n",l);

最大公因数+最小公倍数

定理

$$
\forall a,b\in \mathbb N,\gcd(a,b)\mathrm{lcm}(a,b)=ab
$$

九章算术·更相减损术

$$
\begin{aligned}
\displaylines{
\forall a,b\in \mathbb N,a\ge b,&有\gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b)\\
\forall a,b\in \mathbb N,&有\gcd(2a,2b)=2\gcd(a,b)
}
\end{aligned}
$$

int gcd(int a,int b){
    while(a!=b)
        if(a>b)
            a-=b;
        else
            b-=a;
    return a;
};

欧几里得算法

$$
\forall a,b\in \mathbb N,b\ne 0,\gcd(a,b)=\gcd(b,a\bmod b)
$$

$O(\log n)$

int gcd(const int a,const int b){
	return b?gcd(b,a%b):a;
};
inline int lcm(const int a,const int b){
	return a/gcd(a,b)*b;
};

Lucas定理

若$p\in\mathbb P$，则对于$\forall m\in\mathbb Z,1\leq m\leq n$，有：
$$
\mathrm{\large C}n^m\equiv \mathrm{\large C}{n\bmod p}^{m\bmod p}\mathrm{\large C}_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}\pmod p
$$
$O(f(p)+g(n)\log n)$，$f(n)$为预处理组合数的复杂度，$g(n)$为单次求组合数的复杂度。

inline int icn(const int a){
	if(a>tot){
		for(register int i=tot+1;i<=a;i++)
			rec[i]=(rec[i-1]*i)%p;
		tot=a;
	};
	return rec[a];
};
int fpow(int a,int b){
	int ret=1;
	a%=p;
	while(b>0){
		if((b&1)==1)
			ret=(ret*a)%p;
		a=(a*a)%p,
		b>>=1;
	};
	return ret;
};
inline int fc(const int a,const int b){
	if(a<b)
		return 0;
	return icn(a)*fpow(icn(b),p-2)%p*fpow(icn(a-b),p-2)%p;
};
inline int lcs(const int a,const int b){
	if(b==0)
		return 1;
	return fc(a%p,b%p)*lcs(a/p,b/p)%p;
};
tot=0,
rec[0]=1;
printf("%d\n",lcs(n,m));

中国剩余定理

设$m_1,m_2,\cdots,m_n\in\mathbb Z$两两互质，$\displaystyle m=\prod_{i=1}^n{m_i}, \ \displaystyle M_i=\frac{m}{m_i}$，$t_i$是线性同余方程$\displaystyle M_it_i\equiv 1\pmod{m_i}$的一个解。对于任意的$a_1,a_2,\cdots,a_n\in \mathbb Z$，方程组
$$
\begin{cases}
\displaylines{
x\equiv a_1\pmod{m_1}\\
x\equiv a_2\pmod{m_2}\\
\qquad\qquad\vdots\\
x\equiv a_n\pmod{m_n}
}
\end{cases}
$$
有整数解，解为$\displaystyle x=\sum_{i=1}^n{a_iM_it_i}$。

算法流程

1、计算$\displaystyle m=\prod_{i=1}^n{m_i}$。
2、对于第$i$个方程：
3、计算$\displaystyle M_i=\frac{m}{m_i}$。
4、计算$M_i^{-1}\pmod{m_i}$。
5、计算$c_i=M_iM_i^{-1}$（不要对$m_i$取模）。
6、方程组的唯一解为：$\displaystyle x=\left(\sum_{i=1}^n{a_ic_i}\right)\bmod m$。

void exgcd(long long int a,long long int b,long long int &x,long long int &y){
	if(b==0){
		x=1,
		y=0;
		return void();
	};
	exgcd(b,a%b,y,x);
	y-=a/b*x;
	return void();
};
inline long long int inv(const long long int a,const long long int b){
	long long int x=0,y=0;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
};
for(register int i=1;i<=n;i++)
	br[i]=read(),
	ar[i]=read(),
	k*=br[i];
for(register int i=1;i<=n;i++)
	ans=(ans+ar[i]*k/br[i]*inv(k/br[i],br[i]))%k;

素数筛

Eratosthenes筛法

$O(n\log\log n)$

bool notprime[N+1];
notprime[0]=notprime[1]=true;
for(register int i=2;i<=n;i++)
	if(notprime[i]==false)
		for(register int j=i;j<n/i;j++)
			notprime[i*j]=true;

线性筛

$O(n)$

int mindiv[N+1],prime[N+1],tot;
for(register int i=2;i<=n;i++){
	if(mindiv[i]==0){
		mindiv[i]=i,
		prime[tot++]=i;
		printf("%d ",i);
	};
	for(register int j=0;prime[j]*i<=n;j++){
		mindiv[prime[j]*i]=prime[j];
		if(prime[j]==mindiv[i])
			break;
	};
};

乘法逆元

若$b,m\in\mathbb{Z},b\bot m$，并且$b\mid a$，则$\exist x\in\mathbb{Z},\frac{a}{b}\equiv ax\pmod m$。称$x$为 $b$的模$m$乘法逆元 ，记为$b^{-1}\pmod m$。
1、当$p\in\mathbb{P}$时，$b^{p-2}=b^{-1}\pmod p$。
2、求解同余方程$bx\equiv 1\pmod m$。

扩展欧几里得求逆元

int exgcd(const int a,const int b,int &x,int &y){
	if(b==0){
		x=1,
		y=0;
		return a;
	};
	t=exgcd(b,a%b,y,x),
	y-=(a/b)*x;
	return t;
};
inline int inv(const int a,const int md){
	exgcd(a,md,x,y);
	return (x%md+md)%md;
};

线性求逆元

inv[1]=1;
for(register int i=2;i<=n;i++)
	inv[i]=(long long int)(p-p/i)*inv[p%i]%p;

快速幂求逆元

$b\pmod p$的逆元为$b^{p-2}\pmod p$

int fp(const int a,const int b,const int m){
	int ret=1;
	while(b!=0){
		if((b&1)==1)
			ret=(ret*a)%m;
		a=(a*a)%m,
		b>>=1;
	};
	return ret;
};
inline int getinv(const int a,const int m){
	return fp(a,m-2,m);
};

高斯-约旦消元法

srand((unsigned)time(NULL));
scanf("%d",&n);
for(register int i=1;i<=n;i++)
	for(register int j=i+1;j<=n;j++){
		jdg=rand()%10000+1;
		if((jdg&1)==1)
			for(register int k=1;k<=n+1;k++)
				swp(map[i][k],map[j][k]);
	};//防止各种hack数据
for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n+1;j++)
		scanf("%lf",&a[i][j]);
for(register int i=1;i<=n;i++){
	maxn=i;
	for(register int j=i+1;j<=n;j++)//选出该列最大系数
		if(fabs(a[j][i])>fabs(a[maxn][i]))
			maxn=j;
	for(register int j=1;j<=n+1;j++)
		swp(a[i][j],a[maxn][j]);
	if(a[i][i]==0)
		continue;//最大值等于0则说明该列都为0，肯定无解
	for(register int j=1;j<=n;j++)
		if(i!=j){
			tmp=a[j][i]/a[i][i];
			for(register int k=i+1;k<=n+1;k++)
				a[j][k]-=a[i][k]*tmp;
		};//每一项都减去一个数（即加减消元）
};//输出的结果要记得除以该项系数，消去常数
for(register int i=1;i<=n;i++){
	if(a[i][i]==0){
		if(a[i][n]!=0){
			printf("无解\n");
			return 0;
		}
		else
			flag=true;
		continue;
	};
	ans[i]=map[i][n]/map[i][i];
	if(ans[i]==-0.00)
		ans[i]=0.00;
};
if(flag==true){
	printf("无穷多实数解\n");
	return 0;
};
for(register int i=0;i<n;i++)
	printf("x%d=%.2lf\n",i+1,ans[i]);

Bézout定理

$\forall a,b\in\mathbb Z$，$\exist x,y\in\mathbb Z, \ ax+by=\gcd(a,b)$

$ax+by=c,x\in \mathbb Z^+,y\in \mathbb Z^+\Leftrightarrow\gcd(a,b)\mid c$

推广

$$
\begin{aligned}
\displaylines{
c=&\sum{A_i\times X_i}\\
c_{\mathrm{min}}=&\gcd(A_i)
}
\end{aligned}
$$

线性同余方程

定理

1、方程$ax+by=c$与方程$\displaystyle ax\equiv c\pmod b$是等价的，有整数解的充要条件为$\gcd(a,b)\mid c$。

根据定理 1，方程$ax+by=c$，我们可以先用扩展欧几里得算法求出一组$x_0,y_0$，也就是$ax_0+by_0=\gcd(a,b)$，然后两边同时除以$\gcd(a,b)$，再乘$c$。然后就得到了方程$\displaystyle a\frac{c}{\gcd(a,b)}x_0+b\frac{c}{\gcd(a,b)}y_0=c$，然后我们就找到了方程的一个解。

2、若$\gcd(a,b)=1$，且$x_0$、$y_0$为方程$ax+by=c$的一组解，则该方程的任意解可表示为：$x=x_0+bt$，$y=y_0-at$,且对$\forall t\in\mathbb Z$都成立。

根据定理 2，可以求出方程的所有解。但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特解$\displaystyle x=(x\bmod t+t)\bmod t$，其中$\displaystyle t=\frac{b}{\gcd(a,b)}$。

最小整数解：

$$
ax\equiv 1\pmod b
$$

//long long int
int exgcd(const int a,const int b,int &x,int &y){
	int res=0;
	if(b==0){
		x=1,
		y=0;
		return a;
	};
	res=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return res;
};
gcd=exgcd(a,b,x,y),
a/=gcd,
b/=gcd,
c/=gcd,
x*=c,
b=abs(b);
if(a%b==0)
	printf("Impossible\n");
else
	printf("%d\n",(x%b+b)%b);

同余基本性质

1、$a_1,b_1,a_2,b_2\in\mathbb Z,m\in\mathbb{N^+}$，当$\displaystyle a_1\equiv b_1\pmod m,a_2\equiv b_2\pmod m$成立时，有$\displaystyle a_1\pm a_2\equiv b_1\pm b_2\pmod m$。

2、$a_1,b_1,a_2,b_2\in\mathbb Z,m\in\mathbb{N^+}$，当$\displaystyle a_1\equiv b_1\pmod m,a_2\equiv b_2\pmod m$成立时，有$\displaystyle a_1a_2\equiv b_1b_2\pmod m$。

3、$a,b,c\in\mathbb Z,m\in\mathbb {N^+}$，当$\displaystyle a+b\equiv c\pmod m$成立时，有$\displaystyle a\equiv c-b\pmod m$。

4、$a,b\in\mathbb Z, \ k,m\in\mathbb{N^+}$，当$\displaystyle a\equiv b\pmod m$成立时，有$\displaystyle ak\equiv bk\pmod{mk}$。

5、$a,b\in\mathbb Z, \ d,m\in\mathbb{N^+}, \ d\mid a, \ d\mid b, \ d\mid m$，则当$\displaystyle a\equiv b\pmod m$成立时，有$\displaystyle \frac{a}{d}\equiv\frac{b}{d}\quad\left(\bmod{\frac{m}{d}}\right)$。

6、$a,b\in\mathbb Z, \ d,m\in\mathbb{N^+}, \ d\mid m$，则当$\displaystyle a\equiv b\pmod m$成立时，有$\displaystyle a\equiv b\pmod d$。

7、$a,b\in\mathbb Z, \ d,m\in\mathbb{N^+}$，则当$\displaystyle a\equiv b\pmod m$成立时，有$\gcd(a,m)=\gcd(b,m)$，则：
$$
\begin{cases}
\displaylines{
d\mid a & :d\mid m, \ d\mid b\\
d\mid b & :d\mid m, \ d\mid a
}
\end{cases}
$$

二元一次不定方程

int exgcd(const int a,const int b,int &tx,int &ty){
	int ans=0;
	if(b==0){
		tx=1,
		ty=0;
		return a;
	};
	ans=exgcd(b,a%b,ty,tx);
	ty-=a/b*tx;
	return ans;
};
gcd=exgcd(a,b,x,y);
if(c%gcd!=0){
	printf("-1\n");
	continue;
};
x*=c/gcd,
y*=c/gcd,
p=b/gcd,
q=a/gcd;
if(x<0)//将x提高到最小正整数 
	k=ceil((1.0-x)/p),
	x+=p*k,
	y-=q*k;
else//将x降低到最小正整数 
	k=(x-1)/p,
	x-=p*k,
	y+=q*k;
if(y>0){//有正整数解
	printf("%d ",(y-1)/q+1);//解的个数
	printf("%d ",x);//x的最小正整数值
	printf("%d ",(y-1)%q+1);//y的最小正整数值
	printf("%d ",x+(y-1)/q*p);//x的最大正整数值
	printf("%d\n",y);//y的最大正整数值
}
else{//无正整数解
	printf("%d ",x);//x的最小正整数值
	printf("%d\n",y+q*(int)ceil((1.0-y)/q));//y的最小正整数值
};

矩阵乘法

设$A$是$n\times m$矩阵，$B$是$m\times p$矩阵，则$C=A\times B$是$n\times p$矩阵，并且$\forall i\in[1,n]$，$\forall j\in[1,p]$：
$$
C_{i,j}=\sum_{k=1}^m{A_{i,k}\times B_{k,j}}
$$

加速递推

$$
f_n=p\times f_{n-1}+q\times f_{n-2}
$$

求$\displaystyle f_n \bmod m$：
$$
\left[
\begin{matrix}
f_1&f_2
\end{matrix}
\right]
\times
\left[
\begin{matrix}
\displaylines{
0&q\\
1&p
}
\end{matrix}
\right]^{n-2}
$$

void mul(void){
	long long int ret[2];
	memset(ret,0,sizeof(ret));
	for(register int i=0;i<2;i++)
		for(register int j=0;j<2;j++)
			ret[i]=(ret[i]+f[j]*a[j][i])%m;
	memcpy(f,ret,sizeof(ret));
	return void();
};
void mulself(void){
	long long int ret[2][2];
	memset(ret,0,sizeof(ret));
	for(register int i=0;i<2;i++)
		for(register int j=0;j<2;j++)
			for(register int k=0;k<2;k++)
				ret[i][j]=(ret[i][j]+a[i][k]*a[k][j])%m;
	memcpy(a,ret,sizeof(ret));
	return void();
};
int main(void){
	scanf("%d%d%d%d%d%d",&p,&q,&f[0],&f[1],&n,&m);
	n-=2,
	a[0][0]=0,
	a[1][0]=1;
	a[0][1]=q,
	a[1][1]=p;
	while(n!=0){
		if(n&1==1)
			mul();
		mulself();
		n>>=1;
	};
	printf("%d\n",f[1]);
	return 0;
};

博弈论+SG函数

定义

游戏过程中面临的状态称为局面 。整局游戏第一个行动的称为先手 第二个行动的称为后手 。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败 。最优策略 指若在某一局面下存在何种行动，是的行动后对手面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜 。

公平组合游戏ICG

1、由两名玩家交替行动
2、在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
3、不能行动的玩家判负

有向图游戏

给定一个DAG，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。任何一个ICG都可以转化为有向图游戏：把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设$S\in\mathbb N$。
$$
{\rm mex}(S)=\min_{x\in\mathbb N,x\in S}{x}
$$

SG函数

在有向图游戏中，对于每个节点$x$，设从$x$出发共有$k$条有向边，分别到达节点$y_1,y_2,\cdots ,y_k$。

$$
\operatorname{SG}(x)=\operatorname{mex}({\operatorname{SG}(y_1),\operatorname{SG}(y_2),\cdots,\operatorname{SG}(y_k)})
$$

特别地，设整个有向图游戏$G$的起点$s$，有${\rm SG}(G)={\rm SG}(s)$。

有向图游戏的和

设$G_1,G_2,\cdots ,G_m$是$m$个有向图游戏。定义有向图游戏$G$，它的行动规则是任选某个有向图游戏$G_i$，并在$G_i$上行动一步。$G$被称为有向图$G_1,G_2,\cdots ,G_m$的和。
$$
{\rm SG}(G)=\bigoplus_{i=1}^m{\rm SG}(G_m)
$$

定理

1、有向图游戏的某个局面必胜，当且仅当该局面对应节点的${\rm SG}()>0$。

2、有向图游戏的某个局面必败，当且仅当该局面对应节点的${\rm SG}()=0$。

NIM博弈

有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。

先手必胜当且仅当：
$$
\bigoplus_{i=1}^n{A_i}\ne 0
$$

ans=0;
for(register int i=1;i<=n;i++){
	scanf("%d",&tmp);
	ans^=tmp;
};
if(ans==0)
	printf("后手必胜\n");
else
	printf("先手必胜\n");

威佐夫博弈

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。

若两堆物品的初始值为$(x,y)$，且$x<y$，则另$z=y-x$；
记$\displaystyle w=(\mathrm{int})\left(\frac{\sqrt{5}+1}{2}\times z\right)$；
若$w=x$，则先手必败，否则先手必胜。

scanf("%d%d",&x,&y);
if((int)(((sqrt(5)+1)/2)*(max(x,y)-min(x,y)))==min(x,y))
	printf("先手必败\n");
else
	printf("先手必胜\n");

巴什博奕

A和B一块报数，每人每次报最少$1$个，最多报$4$个，看谁先报到$30$。

第一次报数，A报$k$个数，那么B报$5-k$个数，那么B报数之后问题就变为，A和B一块报数，看谁先报到$25$了，进而变为$20,15,10,5$，当到$5$的时候，不管A怎么报数，最后一个数肯定是B报的，可以看出，作为后手的B在个游戏中是不会输的。

那么如果我们要报$n$个数，每次最少报一个，最多报$m$个，我们可以找到这么一个整数$k$和$r$，使$n=k\times (m+1)+r$，代入上面的例子我们就可以知道，如果$r=0$，那么先手必败；否则，先手必胜。

if(n%(m+1)==0)
	printf("后手必胜\n");
else
	printf("先手必胜\n");

斐波那契博弈

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

先手胜当且仅当$n$不是斐波那契数（$n$为物品总数）

const int N=55;
f[1]=f[2]=1,
flag=false;
for(register int i=3;i<=N;i++)
	f[i]=f[i-1]+f[i-2];
for(register int i=1;i<=N;i++)
	if(f[i]==n){
		flag=true;
		break;
	};
if(flag==true)
	printf("先手必败\n");
else
	printf("先手必胜\n");

算术基本定理

$\forall N\in\mathbb N^+$能唯一分解为有限个质数的乘积，可写作：
$$
N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}
$$
其中$\forall c_i\in \mathbb N^+,p_i\in \mathbb P$，且满足$p_1<p_2<\cdots <p_m$

推论

$N$的正约数集合可写作：
$$
{ p_1^{b_1}p_2^{b_2}\cdots p_m^{b_m} },0\le b_i\le c_i
$$
$N$的正约数个数为：
$$
(c_1+1)(c_2+1)\cdots(c_m+1)=\prod_{i=1}^m{(c_i+1)}
$$
$N$的所有正约数的和为：
$$
(1+p_1+p_1^2+\cdots+p_1^{c_1})\cdots(1+p_m+p_m^2+\cdots+p_m^{c_m})=\prod_{i=1}^m{\sum_{j=0}^{c_i}{(p_i)^j}}
$$

因数

整除的性质

1、$a\mid b\Leftrightarrow -a\mid b\Leftrightarrow a\mid -b\Leftrightarrow |a|\mid |b|$

2、$a\mid b, \ b\mid c\Rightarrow a\mid c$

3、$a\mid b, \ a\mid c\Leftrightarrow\forall x,y\in\mathbb{Z},a\mid xb+yc$

4、$a\mid b, b\mid a\Rightarrow b=\pm a$

5、$a\mid b\Leftrightarrow ma\mid mb, \ m\neq 0$

6、$a\mid b\Rightarrow |a|\leq |b|, \ b\neq 0$

7、$a\mid b\Leftrightarrow a\mid c, \ a\neq 0, \ b=qa+c$

试除法

质因数分解

$O(\sqrt n)$

void divide(int n){
	for(register int i=2;i<=sqrt(n);i++)
		if(n%i==0){
			prm[++cnt]=i,
			chk[cnt]=0;
			while(n%i==0)
				n/=i,
				chk[cnt]++;
		};
	if(n>1)
		prm[++cnt]=n,
		chk[cnt]=1;
	for(register int i=1;i<=m;i++)
		printf("%d %d\n",prm[i],chk[i]);
	return void();
};

正约数集合

$O(\sqrt n)$

for(register int i=1;i*i<=n;i++)
	if(n%i==0){
		fct[++cnt]=i;
		if(i!=n/i)
			fct[++cnt]=n/i;
	};
for(register int i=1;i<=cnt;i++)
	printf("%d",fct[i]);

倍数法

$O(n\log n)$

vector<int> fct[];
for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n/i;j++)
		fct[i*j].push_back(i);
for(register int i=1;i<=n;i++){
	for(register int j=0;j<fct[i].size();j++)
		printf("%d ",fct[i][j]);
	putchar('\n');
};

推论

一个整数$N$的约数个数上界为$2\sqrt n$。

$[1,N]$每个数的约数个数的总和$\approx N\log N$。

欧拉函数

$[1,N]$中与$N$互质的数的个数被称为欧拉函数，记为$\varphi(N)$。

若在算术基本定理中，$N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，则：
$$
\varphi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\cdots\times\frac{p_m-1}{p_m}=N\times\prod_{p\mid N,p\in\mathbb P}{\left(1-\frac{1}{p}\right)}
$$

质数分布密度： 对于一个足够大的$N\in\mathbb Z$，不超过$N$的质数大约有$\displaystyle \frac{N}{\ln N}$个。

int phi(int n){
	int ans=n;
	for(register int i=2;i*i<=n;i++)
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0)
				n/=i;
		};
	if(n>1)
		ans=ans/n*(n-1);
	return ans;
};

欧拉筛

$O(n\log n)$

void euler(const int n){
	for(register int i=2;i<=n;i++)
		phi[i]=i;
	for(register int i=2;i<=n;i++)
		if(phi[i]==i)
			for(register int j=i;j<=n;j+=i)
				phi[j]=phi[j]/i*(i-1);
	return void();
};

性质

1、$\forall n>1,[1,n]$中与$n$互质的数的和为$\displaystyle \frac{n\varphi(n)}{2}$。

2、若$a\bot b$，则$\varphi(ab)=\varphi(a)\varphi(b)$。

3、若$f$是积性函数，且在算术基本定理中$\displaystyle n=\prod_{i=1}^m{p_i^{c_i}}$，则$\displaystyle f(n)=\prod_{i=1}^m{f(p_i^{c_i})}$。

4、设$p\in\mathbb P$，若$p\mid n$且$p^2\mid n$，则$\displaystyle \varphi(n)=\varphi\left(\frac{n}{p}\right)\times p$。

5、设$p\in\mathbb P$，若$p\mid n$但$p^2\nmid n$，则$\displaystyle \varphi(n)=\varphi\left(\frac{n}{p}\right)\times(p-1)$

6、$\displaystyle \sum_{d\mid n}{\varphi(d)}=n$

欧拉定理

若$a,n\in\mathbb N^+,a\bot n$，则$\displaystyle a^{\varphi(n)}\equiv 1\pmod n$。

费马小定理

若$p\in\mathbb P$，则对任意$\displaystyle a\in\mathbb Z$，有$\displaystyle a^p\equiv a\pmod p$。

推论

若$a,n\in\mathbb N^+,a\bot n$，则对$\forall b\in\mathbb N^+$，有$\displaystyle a^b\equiv a^{\displaystyle b\bmod\varphi(n)}\pmod n$。

当$a,n$不一定$a\bot n$且$b>\varphi(n)$时，有$\displaystyle a^b\equiv a^{\displaystyle b\bmod\varphi(n)+\varphi(n)}\pmod n$。

同余类与剩余系

$\displaystyle \forall a\in[0,m-1],\forall x,y\in A={a+km}(k\in\mathbb{Z}),x\equiv y\pmod m,x\bmod m=a$，$A$称为一个模$m$的同余类 $\overline{a}$。

模$m$的同余类一共有$m$个，分别为$\overline{0},\overline{1},\overline{2},\cdots,\overline{m-1}$。它们构成$m$的完全剩余系。

$1\sim m$中与$m$互质的数代表的同余类共有$\varphi(m)$个，它们构成$m$的简化剩余系 。

排列组合

$$
\begin{aligned}
\displaylines{
\mathrm{\large C}_n^m=&\frac{n!}{m!(n-m)!}=
\begin{pmatrix}
n\\
m
\end{pmatrix}\\
\mathrm{\large P}_n^m=&\frac{n!}{(n-m)!}
}
\end{aligned}
$$

c[1][0]=c[1][1]=1;
for(register int i=2;i<=n;i++){
	c[i][0]=1;
	for(register int j=1;j<=m;j++)
		c[i][j]=c[i-1][j]+c[i-1][j-1];
};

组合数性质

1、对称恒等式：
$$
\mathrm{\large C}n^m=\mathrm{\large C}n^{n-m}
$$
2、加法公式：
$$
\mathrm{\large C}n^m=\mathrm{\large C}{n-1}^m+\mathrm{\large C}{n-1}^{m-1}
$$
3、
$$
\sum{i=0}^n{\mathrm{\large C}n^i}=2^n
$$
4、吸收恒等式：
$$
\mathrm{\large C}n^k=\frac{n}{k}\mathrm{\large C}{n-1}^{k-1}
$$
5、
$$
\sum{i=0}^n{(-1)^i}\mathrm{\large C}n^i=[n=0]
$$
6、
$$
\sum{i=0}^m{\mathrm{\large C}n^i\mathrm{\large C}{m}^{m-i}}=\mathrm{\large C}{m+n}^m
$$
7、
$$
\sum{i=0}^n{\mathrm{\large C}n^i}^2=\mathrm{\large C}{2n}^n
$$
8、
$$
\sum_{i=0}^n{i\mathrm{\large C}n^i}=n2^{n-1}
$$
9、
$$
\sum{i=0}^n{i^2\mathrm{\large C}n^i}=n(n+1)2^{n-2}
$$
10、上指标求和法：
$$
\sum{i=0}^n\mathrm{\large C}i^k=\mathrm{\large C}{n+1}^{k+1}, \ n,m\geq 0
$$
11、
$$
\mathrm{\large C}n^r\mathrm{\large C}r^k=\mathrm{\large C}n^k\mathrm{\large C}{n-k}^{r-k}
$$
12、
$$
\sum{i=0}^n\mathrm{\large C}{n-i}^i={\mathrm{\large Fib}}{n+1}
$$
13、
$$
\sum{l=0}^n\mathrm{\large C}l^k=\mathrm{\large C}{n+1}^{k+1}
$$
14、平行求和法：
$$
\sum_{i=1}^n\mathrm{\large C}{k+i}^k=\mathrm{\large C}{k+n+1}^n
$$
15、
$$
{(x+y)}^k=\sum_i{\mathrm{\large C}k^ix^iy^{k-i}}, \ r\in\mathbb{N},\left|\frac{x}{y}\right|<1
$$
16、上指标反转：
$$
\mathrm{\large C}n^m={(-1)}^m\mathrm{\large C}{m-n-1}^n
$$
17、范德蒙德卷积：
$$
\sum_i{\mathrm{\large C}k^{m+i}\mathrm{\large C}s^{n-i}}=\mathrm{\large C}{k+x}^{m+n}
$$
18、
$$
\sum{-q\leq k\leq l}{\mathrm{\large C}{l-k}^m\mathrm{\large C}{q+k}^n}=\mathrm{\large C}{l+q+1}^{m+n+1}, \ l+q,m,n\geq 0
$$

杨辉恒等式

$$
\sum_{i=1}^n\sum_{j=1}^m\mathrm{\large C}j^i=\sum{i=1}\mathrm{\large C}_{m+1}^{i+1}
$$

二项式定理

$$
\begin{aligned}
\displaylines{
(a+b)^n=&\sum_{k=0}^n{\mathrm{\large C}n^ka^kb^{n-k}}\\
(ax+by)^k=&\sum{i=0}^k\mathrm{\large C}_k^ia^ib^{k-i}x^iy^{k-i}
}
\end{aligned}
$$

多重集

$\displaystyle S=\bigcup_{i=1}^k, \ n=\sum_{i=1}^k{n_i}$。
$S$的全排列个数为：
$$
\frac{n!}{\displaystyle \prod_{i=1}^k{n_i!}}
$$
从$S$中取出$r$个元素组成一个多重集，产生的不同多重集数量为：
$$
\begin{cases}
\displaylines{
\displaystyle \mathrm{\large C}{k+r-1}^{k-1} & :r\le n_i,\forall i\in [1,k]\\
\displaystyle \mathrm{\large C}{k+r-1}^{k-1}-\sum_{i=1}^k{\mathrm{\large C}{k+r-n_i-2}^{k-1}}+\sum{1\le i<j\le k}{\mathrm{\large C}{k+r-n_i-n_j-3}^{k-1}}-\cdots +\cos{k\pi}\times \mathrm{\large C}{\displaystyle k+r-\sum_{i=1}^k{n_i}-(k+1)}^{k-1} & :r\le n
}
\end{cases}
$$

圆排列

$$
\mathrm{\large Q}^r_n=\frac{\mathrm{\large P}^r_n}{r}
$$

错排问题

$1,2,\cdots,n$的错排问题，$i$不在第$i$个位置的排列方法。

设$f_n$为$n$个不同元素的错排方案。

$n$先不动，把另外的$n-1$个数错排，方案是：$f_{n-1}$，然后$n$和另外的$n-1$个每一个交换，共有$(n-1)f_{n-1}$种方案。

$n$和其他的$n-1$个之一交换，其余的$n-2$个错排，共有$(n-1)f_{n-2}$种方案。

$$
\begin{aligned}
\displaylines{
f_n=&(n-1)(f_{n-1}+f_{n-2})\\
f_1=&0\\
f_2=&1\\
f_n=&n!\left(\sum_{i=2}^n\cos i\pi\frac{1}{i!}\right)
}
\end{aligned}
$$

Catalan数列

给定$n$个$0$和$n$个$1$，它们按照某种顺序排成长度为$2n$的序列，满足任意前缀中$0$的个数都不少于$1$的个数的序列的数量为：
$$
{\mathrm{\large Cat}}n=\frac{\mathrm{\large C}{2n}^n}{n+1}
$$

推论

1、$n$个左括号和$n$个右括号组成的合法括号序列的数量为${\mathrm{\large Cat}}_n$。

2、$1,2,\cdots,n$经过一个栈，形成的合法出栈序列的数量为${\mathrm{\large Cat}}_n$。

3、$n$个节点构成的不同二叉树的数量为${\mathrm{\large Cat}}_n$。

4、在平面直角坐标系上，每一步只能向上或向右走，从$(0,0)$走到$(n,n)$并且除两个端点外不接触直线$y=x$的路线数量为$2{\mathrm{\large Cat}}_{n-1}$。

5、折线定理：给定$n$个$1$和$m$个$0$，组成一个字符串，要求在任一的前$k$个字符中，$1$的个数不能少于$0$的个数，字符串数：
$$
\mathrm{\large C}{n+m}^m-\mathrm{\large C}{n+m}^{m-1}
$$

拉格朗日四平方和定理

每个正整数均可表示为4个整数的平方和。

容斥原理

设$S$为一个集合，$S_1,S_2,\cdots ,A_n\subseteq S$。
$$
\displaylines{
\left| \bigcup_{i=1}^n{S_i}\right| =\sum_{i=1}^n{\vert S_i\vert}-\sum_{i=1}^n{\vert S_i\cap S_j\vert }+\sum_{1\le i<j<k\le n}{\vert S_i\cap S_j\cap S_k\vert}+\cdots +\cos{(n+1)\pi}\left| \bigcap_{i=1}^n{S_i}\right|\\
\left| \bigcap_{i=1}^n{S_i}\right| =\sum_{i=1}^n{\vert S_i\vert}-\sum_{i=1}^n{\vert S_i\cap S_j\vert }+\sum_{1\le i<j<k\le n}{\vert S_i\cap S_j\cap S_k\vert}+\cdots +\cos{(n+1)\pi}\left| \bigcup_{i=1}^n{S_i}\right|
}
$$

加权形式

设$S$是一个集合，$\forall x\in S$定义权函数$m(x)>0$，$S_1,S_2,\cdots,S_n\subseteq S$。$\displaystyle \forall A\subseteq S,m(A)=\sum_{i\in A}m(i), \ \displaystyle Q=\bigcup_{i=1}^n{i}$。
$$
\displaylines{
m\left(\bigcup_{i=1}^nS_i\right)=\sum_{i=1}^n\cos(i+1)\pi\sum_{K\subseteq Q,|K|=i}m\left(\bigcap_{j\in K}S_i\right)\\
m\left(\bigcap_{i=1}^nS_i\right)=\sum_{i=1}^n\cos(i+1)\pi\sum_{K\subseteq Q,|K|=i}m\left(\bigcup_{j\in K}S_i\right)
}
$$

Mŏbíus函数

设$N\in\mathbb N^+$按照算术基本定理分解质因数为$N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，定义函数：
$$
\mu(n)=
\begin{cases}
\displaylines{
0 & :\exist i\in[1,m],c_i>1\\
1 & :m\equiv 0(\mod 2),\forall i\in[1,m],c_i=1\\
-1 & :m\equiv 1(\mod 2),\forall i\in[1,m],c_i=1
}
\end{cases}
$$

Jordan筛法公式

设$\displaystyle S_1,S_2,S_3,\cdots,S_n\subseteq S, \ Q=\bigcup_{i=1}^n{i}$，在$S$中所有恰属于$p$个集合的元素的权和为：
$$
M_n^p=\sum_{i=p}^n\cos(i-p)\pi C_i^p\sum_{K\subset Q,|K|=k}m\left(\bigcap_{j\in K}S_j\right)
$$

Sylvester公式

设$\displaystyle S_1,S_2,S_3,\cdots,S_n\subseteq S, \ Q=\bigcup_{i=1}^n{i}$，在$S$中不属于任何集合的元素的权和为：
$$
M_n^0=m(S)+\sum_{K\subseteq Q}\cos |K|\pi m\left(\bigcap_{i\in K}S_i\right)
$$

康托展开

（树状数组优化）

inline long long int lowbit(const long long int x){
	return x&-x;
};
inline long long int ask(long long int pos){
	long long int ret=0;
	while(pos>0)
		ret+=tree[pos],
		pos-=lowbit(pos);
	return ret;
};
inline void add(long long int pos){
	while(pos<=n)
		tree[pos]++,
		pos+=lowbit(pos);
	return void();
};
long long int cantor(void){
	ans=0;
    memset(tree,0,sizeof(tree));
	for(register long long int j=n;j>=1;t[j--]=read());
	for(register long long int i=1;i<=n;i++){
		ans+=1ll*fac[i-1]*ask(t[i]);
		add(t[i]);
	};
	return ans+1;
};

逆康托展开

const int fac[]={...}
vector<int>v,a;//存放当前可选数、所求排列组合
inline bool cmp(const long long int a,const long long int b){
	return a<b;
};
void decantor(const int k){
    tmp=read()-1;
	v.clear();
	a.clear();
	for(register long long int j=1;j<=n;v.push_back(j++));
    for(register int i=n;i>=1;i--){
        t=x/fac[i-1],
        x=r=x%fac[i-1];
        sort(v.begin(),v.end());
        a.push_back(v.at(t));
        v.erase(v.begin()+t);
    };
    for_each(a.begin(),a.end(),f);
	putchar('\n');
    return void();
};

Prüfer序列

对树建立Prüfer序列

1、找到编号最小的度数为$1$的点。
2、删除该节点并在序列中添加与该节点相连的节点的编号。
3、重复$1,2$操作，直到整棵树只剩下两个节点。

线性构造

指针指向编号最小的叶节点。每次删掉它之后，如果产生了新的叶节点且编号比指针指向的更小，则直接继续删掉，否则自增找到下一个编号最小的叶节点。

void tp(void){
	for(register int i=1;i<=n-1;i++)
		fa[i]=read(),
		cnt[fa[i]]++;
	for(register int i=1,j=1;i<=n-1;i++,j++){
		while(cnt[j]!=0)
			j++;
		pr[i]=fa[j];
		while((i<=n-2)&&(--cnt[pr[i]]==0)&&(pr[i]<j))
			pr[i+1]=fa[pr[i]],
			i++;
	};
	for(register int i=1;i<=n-2;i++)
        printf("%d ",pr[i]);
	return void();
};

用Prüfer序列重建树

1、每次取出Prüfer序列中最前面的元素$u$。
2、在点集中找到编号最小的没有在Prüfer序列中出现的元素$v$。
3、给$u,v$连边然后分别删除。
4、最后在点集中剩下两个节点，给它们连边。

线性重建

指针指向编号最小的度数为$1$的节点。每次将它与当前枚举到的Prüfer序列的点连接之后，如果产生了新的度数为$1$的节点且编号比指针指向的更小，则直接继续将它与下一个Prüfer序列的点连接，否则自增找到下一个编号最小的度数为$1$的节点。

void pt(void){
	for(register int i=1;i<=n-2;i++)
		pr[i]=read(),
		cnt[pr[i]]++;
	pr[n-1]=n;
	for(register int i=1,j=1;i<=n-1;i++,j++){
		while(cnt[j]!=0)
			j++;
		fa[j]=pr[i];
		while((i<=n-1)&&(--cnt[pr[i]]==0)&&(pr[i]<j))
			fa[pr[i]]=pr[i+1],
			i++;
	};
	for(register int i=1;i<=n-1;i++)
        printf("%d ",fa[i]);
	return void();
};

性质

1、在构造完Prüfer序列后原树中会剩下两个结点，其中一个一定是编号最大的点$n$。

2、每个结点在序列中出现的次数是其度数$-1$。（没有出现的就是叶结点）

3、一棵$n$个节点的无根树唯一地对应了一个长度为$n-2$的数列，数列中的每个数都在$[1,n]$。

4、$n$个点的无向完全图的生成树的计数：$n^{(n−2)}$，即$n$个点的有标号无根树的计数。

5、$n$个节点的度依次为$d_1,d_2,\cdots,d_n$的无根树共有$\displaystyle \frac{(n-2)!}{\displaystyle \prod_{i=1}^n{(d_i-1)!}}$个，因为此时Prüfer编码中的数字$i$恰好出现$d_i−1$次，$(n−2)!$是总排列数。

6、$n$个点的有标号有根树的计数：
$$
n^{(n−2)}\times n=n^{(n−1)}
$$

图连通方案数

一个$n$个点$m$条边的带标号无向图有$k$个连通块。设$s_i$表示每个连通块的数量。我们希望添加$k-1$条边使得整个图连通。方案数：
$$
n^{k-2}\prod_{i=1}^k{s_i}
$$

Cayley公式

完全图$K_n$有$n^{n-2}$棵生成树。$n^{n-1}$棵有根树。

线性空间

线性空间 是一个关于以下两个运算封闭的向量集合：
1、向量加法$\overrightarrow a+\overrightarrow b$。
2、标量乘法（数乘运算）$k\overrightarrow a$。

给定$\overrightarrow{a_1},\overrightarrow{a_2},\cdots ,\overrightarrow{a_k}$，若$\overrightarrow b$能由$\overrightarrow{a_1},\overrightarrow{a_2},\cdots ,\overrightarrow{a_k}$经过向量加法和标量乘法运算得出，则称$\overrightarrow b$能被$\overrightarrow{a_1},\overrightarrow{a_2},\cdots ,\overrightarrow{a_k}$表出 。

$\overrightarrow{a_1},\overrightarrow{a_2},\cdots ,\overrightarrow{a_k}$能表出的所有向量构成一个线性空间，$\overrightarrow{a_1},\overrightarrow{a_2},\cdots ,\overrightarrow{a_k}$被称为这个线性空间的生成子集 。

任意选出线性空间中的若干个向量，如果其中存在一个向量能被其他向量表出，则称这些向量线性相关 ，否则称这些向量线性无关 。

线性无关的生成子集（或线性空间的极大线性无关子集）被称为线性空间的基底 （基 ）。一个线性空间的所有基包含的向量个数都相等，这个数被称为线性空间的维数 。

对于一个$n$行$m$列的矩阵，我们把它的每一行看作一个长度为$m$的向量（行向量 ）。矩阵的$n$个行向量能够表出的所有向量构成一个一维线性空间，这个线性空间的维数称为矩阵的行秩 。矩阵的行秩一定等于列秩，它们都被称为矩阵的秩 。

若$b\in\mathbb Z$能由$a_1,a_2,\cdots ,a_k\in\mathbb Z$经异或运算得出，则称$b$能被$a_1,a_2,\cdots ,a_k$表出 。

$a_1,a_2,\cdots ,a_k$能表出的所有证书构成一个异或空间，$a_1,a_2,\cdots ,a_k$被称为这个异或空间的生成子集 。

任意选出异或空间中的若干个整数，如果其中存在一个整数能被其他整数表出，则称这些整数线性相关 ，否则称这些整数线性无关 。异或空间的基 就是异或空间中一个线性无关的生成子集（或异或空间的极大线性无关子集）。

线性基

若$b\in\mathbb Z$能由$a_1,a_2,\cdots ,a_k\in\mathbb Z$经异或运算得出，则称$b$能被$a_1,a_2,\cdots ,a_k$表出 。

$a_1,a_2,\cdots ,a_k$能表出的所有证书构成一个异或空间，$a_1,a_2,\cdots ,a_k$被称为这个异或空间的生成子集 。

任意选出异或空间中的若干个整数，如果其中存在一个整数能被其他整数表出，则称这些整数线性相关 ，否则称这些整数线性无关 。异或空间的基 就是异或空间中一个线性无关的生成子集（或异或空间的极大线性无关子集）。

性质

1、线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
2、线性基是满足性质1的最小的集合。
3、线性基没有异或和为$0$的子集。
4、线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
5、线性基中每个元素的二进制最高位互不相同。

构造

void add(int x){
	for(register int i=51;i>=0;i--){
		if((x>>i)==0)
			continue;
		if(p[i]==0){
			p[i]=x;
			break;
		};
		x^=p[i];
	};
	return void();
};
scanf("%d",&n);
for(register int i=1;i<=n;i++){
	a[i]=read();
	add(a[i]);
};

查询异或最大值

int query_min(void){
    int ans=0;
    for(register int i=51;i>=0;i--)
		ans=max(ans,ans^p[i]);
    return ans;
};

求可异或出的数的个数

void add(int x){
	for(register int i=51;i>=0;i--){
		if((x>>i)==0)
			continue;
		if(p[i]==0){
			p[i]=x,
			cnt++;
			break;
		};
		x^=p[i];
	};
	return void();
};
scanf("%d",&n);
for(register int i=1;i<=n;i++){
	a[i]=read();
	add(a[i]);
};
printf("%d\n",(1LL<<cnt)%md);

不等式

均值不等式

$a_i\geq 0, \ \forall i\in[1,n]$
平方平均数： $\displaystyle Q_n=\sqrt{\frac{\displaystyle \sum_{i=1}^n{a_i^2}}{n}}$
算术平均数： $\displaystyle A_n=\frac{\displaystyle \sum_{i=1}^n{a_i}}{n}$
几何平均数： $\displaystyle G_n=\sqrt[n]{\prod_{i=1}^na_i}$
调和平均数： $\displaystyle H_n=\frac{n}{\displaystyle \sum_{i=1}^n{\frac{1}{a_i}}}$
“调几算方”： $H_n\leq G_n\leq A_n\leq Q_n$
取等条件： $a_i=0, \ \forall i\in[1,n]\Rightarrow Q_n=A_n=G_n=H_n$

Cauchy不等式

$$
\sum_{i=1}^n{a_i^2}\sum_{i=1}^n{b_i^2}\geq{\left(\sum_{i=1}^n{a_ib_i}\right)}^2
$$

取等条件：

$$
a_i=kb_i, \ i\in[1,n]
$$

推论

$$
\begin{aligned}
\displaylines{
\frac{\displaystyle\sum_{i=1}^na_i}{n}&\leq\sqrt{\frac{\displaystyle\sum_{i=1}^na_i^2}{n}}\\
\sum_{i=1}^n\frac{x_i^2}{y_i}&\geq\frac{\displaystyle\left(\sum_{i=1}^nx_i\right)^2}{\displaystyle\sum_{i=1}^ny_i}
}
\end{aligned}
$$

排列不等式

$\forall i,j\in[1,n], \ i,j\in\mathbb Z, \ i<j, \ a_i\leq a_j, \ b_i\leq b_j$，$d_1,d_2,\cdots,d_n$是$1\sim n$的任意一个排列。
$$
\sum_{i=1}^n{a_ib_{n-i+1}}\leq\sum_{i=1}^n{a_ib_{d_i}}\leq\sum_{i=1}^n{a_ib_i}
$$

和式

和式处理

设$K$是一个有限整数集合（指标集） 。
分配率： $\displaystyle \sum_{k\in K}{ca_k}=c\sum_{k\in K}{a_k}$

结合律： $\displaystyle \sum_{k\in K}{(a_k+b_k)}=\sum_{k\in K}{a_k}+\sum_{k\in K}{b_k}$

交换律： $\displaystyle \sum_{k\in K}{a_k}=\sum_{\pi(k)\in K}{a_{\pi(k)}}$

扰动法

将头尾两项分离并试图得出一个关于$S$的方程的方法称为扰动法。
求等比数列的和$\displaystyle S=\sum_{0\leq k<n}{x^k}$：
$$
\begin{aligned}
\displaylines{
S= & x^0-x^n+\sum_{1\leq k\leq n}{x^k}\\
= & x^0-x^n+xS
}
\end{aligned}
$$

交换求和顺序

$$
\sum_i\sum_j{a_{i,j}}[P(i,j)]=\sum_j\sum_i{a_{i,j}}[P(i,j)]
$$

三角求和

$$
\begin{aligned}
\displaylines{
&\sum_{1\leq i\leq j\leq n}{a_ia_j}+\sum_{1\leq j\leq i\leq n}{a_ia_j}\\
=&2S\\
=&\left(\sum_{i=1}^n{a_i}\right)\left(\sum_{j=1}^n{a_j}\right)+\sum_{i=1}^n{a_i^2}
}
\end{aligned}
$$

换元

$$
\begin{aligned}
\displaylines{
H_n=&\sum_{i=1}^n{\frac{1}{i}}\\
\sum_{1\leq j<k\leq n}{\frac{1}{k-j}}=&\sum_{i=1}^{n-1}{H_i}
}
\end{aligned}
$$

下降幂

$$
r^{\underline{k}}=r(r-1)(r-2)\cdots(r-k+1)
$$

二项式系数

$$
C_r^k=
\begin{cases}
\displaylines{
\displaystyle \frac{r^{\underline{k}}}{k!} & :k\geq 0\\
0 & :k<0
}
\end{cases}
$$

生成函数

形式幂级数

对于无限数列（缺项补0） ${f_0,f_1,\cdots}$，其对应的形式幂级数 为：
$$
F(x)=\sum_{i\geq 0}{f_ix^i}
$$

求导

定义$f(x)$的导函数为$\displaystyle f’(x)=\lim_{h\rightarrow 0}{\frac{f(x+h)-f(x)}{h}}$。

求$k$次导函数得到的结果记为$f^{(k)}$。如果使用求导算子$D$ 也可以写成$D^kf$。
$$
\begin{aligned}
\displaylines{
(x^{\alpha})’=&\alpha x^{\alpha -1}\\
(\ln x)’=&\frac{1}{x}\\
(e^x)’=&e^x
}
\end{aligned}
$$

复杂函数求导

$$
\begin{aligned}
\displaylines{
(f+g)’=&f’+g’\\
(fg)’=&f’g+fg’\\
(f(g))’=&f’(g)g’
}
\end{aligned}
$$

替代算子

$$
\vartheta f(x)=xf’(x)
$$

常见幂级数

$$
\begin{aligned}
\displaylines{
\sum_{i\geq 0}{C_{i+k-1}^ix^i}=&\frac{1}{(1-x)^k}\\
\ln\frac{1}{1-x}=&\sum_{i\geq 1}{\frac{x^i}{i}}\\
e^x=&\sum_{i\geq 0}{\frac{x^i}{i!}}
}
\end{aligned}
$$

高阶差分

$$
\begin{aligned}
\displaylines{
\Delta f(x)= & f(x+1)-f(x)\\
\Delta^2 f(x)= & \Delta f(x+1)-\Delta f(x)\\
= & f(x+2)-2f(x+1)+f(x)\\
\Delta^n f(x)= & \sum_i\mathrm{\large C}_n^i{(-1)}^{n-i}f(x+i)
}
\end{aligned}
$$

0/1分数规划

给定整数$a_1,a_2,\cdots ,a_n$以及$b_1,b_2,\cdots ,b_n$，求一组解$x_i,1\leq i\leq n,x_i\in{0,1}$，使下式最大化：
$$
\frac{\displaystyle \sum_{i=1}^na_ix_i}{\displaystyle \sum_{i=1}^nb_ix_i}
$$

$$
\displaylines{
\sum_{i=1}^n(a_i-Lb_i)x_i\geq 0\\
\Downarrow\\
\left(\sum_{i=1}^na_ix_i\right)-L\sum_{i=1}^nb_ix_i\geq 0\\
\Downarrow\\
\frac{\displaystyle \sum_{i=1}^na_ix_i}{\displaystyle \sum_{i=1}^nb_ix_i}\geq L
}
$$

$$
\begin{cases}
\displaylines{
\frac{\displaystyle \sum_{i=1}^na_ix_i}{\displaystyle \sum_{i=1}^nb_ix_i}\geq L & :\displaystyle \exist {x_1,x_2,\cdots ,x_n},\sum_{i=1}^n(a_i-Lb_i)x_i\geq 0\\
\frac{\displaystyle \sum_{i=1}^na_ix_i}{\displaystyle \sum_{i=1}^nb_ix_i}<L & :\displaystyle \forall {x_1,x_2,\cdots ,x_n},\sum_{i=1}^n(a_i-Lb_i)x_i<0
}
\end{cases}
$$

二分法

二分一个$mid$然后判定图上是否存在一个环$S$

使得$\displaystyle \frac{\displaystyle \sum_{i=1}^ta_{v_i}}{\displaystyle \sum_{i=1}^tb_{e_i}}>mid$。

即该环是否满足$\displaystyle \sum_{i=1}^t(a_{v_i}-mid\times b_{e_i})>0$。

若是则$l=mid$，否则$r=mid$。

但是这样在图中判定显然很麻烦，所以我们试着把上式两边同时乘$-1$。

变成$\displaystyle \sum_{i=1}^t(mid\times b_{e_i}-a_{v_i})<0$。

这样我们就把问题转化成了判定图中是否存在负环。

bool chk(const double val){
	memset(dis,0,sizeof(dis));
	memset(vis,true,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	q.clear();
	for(register long long int i=1;i<=n;i++)
		q.push_back(i);
	while(q.empty()==false){
		rec=q.front();
		q.pop_front();
		vis[rec]=false;
		for(register long long int i=head[rec];i!=0;i=nxt[i])
			if(dis[ver[i]]>dis[rec]+val*(double)edge[i]-(double)f[rec]){
				dis[ver[i]]=dis[rec]+val*(double)edge[i]-(double)f[rec];
				if(vis[ver[i]]==false){
					vis[ver[i]]=true;
					if((q.empty()==false)&&(dis[ver[i]]<dis[q.front()]))
						q.push_front(ver[i]);
					else
						q.push_back(ver[i]);
					cnt[ver[i]]++;
					if(cnt[ver[i]]==n+1)
						return true;
				};
			};
	};
	return false;
};
l=0,r=...;
while(r-l>EPS){
	mid=(l+r)/2;
	if(chk(mid)==true)
		l=mid,
		ans=l;
	else
		r=mid;
};
printf("%.2lf\n",ans);

导数

函数	原函数	导函数
常函数	$y=C$	$y’=0$
指数函数	$y=a^x\y=e^x$	$y’=a^x\ln a\y’=e^x$
幂函数	$y=x^n$	$y’=nx^{n-1}$
对数函数	$y=\log_ax\y=\ln x$	$\displaystyle y’=\frac{1}{x\ln a}\y’=\frac{1}{x}$
正弦函数	$y=\sin x$	$y’=\cos x$
余弦函数	$y=\cos x$	$y’=-\sin x$
正切函数	$y=\tan x$	$y’=\sec^2x$
余切函数	$y=\cot x$	$y’=-\csc^2x$
正割函数	$y=\sec x$	$y’=\sec x\tan x$
余割函数	$y=\csc x$	$y’=-\csc x\cot x$
反正弦函数	$y=\arcsin x$	$\displaystyle y’=\frac{1}{\sqrt{1-x^2}}$
反余弦函数	$y=\arccos x$	$\displaystyle y’=-\frac{1}{\sqrt{1-x^2}}$
反正切函数	$y=\arctan x$	$\displaystyle y’=\frac{1}{1+x^2}$
反余切函数	$y=\mathrm{arccot} \ x$	$\displaystyle y’=-\frac{1}{1+x^2}$
双曲线函数	$y=\sh x$	$y’=\ch x$

四则运算

$$
\begin{aligned}
\displaylines{
(u\pm v)’=&u’\pm v’\\
(uv)’=&u’v+uv’\\
\left(\frac{u}{v}\right)=&\frac{u’v-uv’}{v^2}
}
\end{aligned}
$$

牛顿-莱布尼茨公式

$$
\int_a^bf(x)\mathrm dx=F(b)-F(a)=\left.F(x)\right|_a^b
$$

l’Hôpital’s法则

$$
\lim\frac{f(x)}{g(x)}=\lim\frac{f’(x)}{g’(x)}
$$

斐波那契数列

定义：$\mathrm{\large F}_0=0,\mathrm{\large F}1=1,\mathrm{\large F}n=\mathrm{\large F}{n-1}+\mathrm{\large F}{n-2}$

卢卡斯数列

定义：$\mathrm{\large L}_0=2,\mathrm{\large L}1=1,\mathrm{\large L}n=\mathrm{\large L}{n-1}+\mathrm{\large L}{n-2}$

通项公式

$$
\begin{aligned}
\displaylines{
\mathrm{\large F}_n=&\frac{\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n}{\sqrt 5}=\left[\frac{\left(\frac{1+\sqrt 5}{2}\right)^n}{\sqrt 5}\right]（比内公式）\\
\mathrm{\large L}_n=&\left(\frac{1+\sqrt 5}{2}\right)^n+\left(\frac{1-\sqrt 5}{2}\right)^n\
}
\end{aligned}
$$

矩阵形式

$$
\displaylines{
\begin{aligned}
\left[
\begin{matrix}
\mathrm{\large F}{n-1} & \mathrm{\large F}n
\end{matrix}
\right]
=&
\left[
\begin{matrix}
\mathrm{\large F}{n-2} & \mathrm{\large F}{n-1}
\end{matrix}
\right]
\times
\left[
\begin{matrix}
0 & 1\
1 & 1
\end{matrix}
\right]\
P=&\left[
\begin{matrix}
0 & 1\
1 & 1
\end{matrix}
\right]\
\left[
\begin{matrix}
\mathrm{\large F}n & \mathrm{\large F}{n+1}
\end{matrix}
\right]=&\left[
\begin{matrix}
\mathrm{\large F}_0 & \mathrm{\large F}_1
\end{matrix}
\right]
\times P^n
\end{aligned}
}
$$

快速倍增法

$$
\begin{aligned}
\displaylines{
\mathrm{\large F}{2k}=&\mathrm{\large F}k(2\mathrm{\large F}{k+1}-\mathrm{\large F}k)\\
\mathrm{\large F}{2k+1}=&\mathrm{\large F}{k+1}^2+\mathrm{\large F}_k^2
}
\end{aligned}
$$

pair<int,int> fib(const int n){
    if(n==0)
        return {0,1};
    pair<int,int> p=fib(n>>1);
    const int c=p.first*(2*p.second-p.first),d=p.first*p.rist+p.second*p.second;
    if(n&1==1)
        return {d,c+d};
    return {c,d};
};

性质

1、卡西尼性质：$\mathrm{\large F}{n-1}\mathrm{\large F}{n+1}-\mathrm{\large F}_n^2={(-1)}^n$

2、附加性质：$\mathrm{\large F}{n+k}=\mathrm{\large F}k\mathrm{\large F}{n+1}+\mathrm{\large F}{k-1}\mathrm{\large F}n$（当$k=n$时：$\mathrm{\large F}{2n}=\mathrm{\large F}n(\mathrm{\large F}{n+1}+\mathrm{\large F}_{n-1})$，且$\forall k\in\mathbb N,\mathrm{\large F}n\mid \mathrm{\large F}{nk}$）

3、GCD性质：$\gcd(\mathrm{\large F}_m,\mathrm{\large F}n)=\mathrm{\large F}{\gcd(m,n)}$

数列

等差数列（A.P.）

通项公式

$$
\displaylines{
a_n=a_1+(n-1)d\\
\begin{cases}
a_1=S_1 & :n=1\\
a_n=S_n-S_{n-1} & :n\geq 2
\end{cases}
}
$$

等差中项

$$
A=\frac{a+b}{2}
$$

前$n$项和

$$
\begin{aligned}
\displaylines{
S_n=&n\frac{a_1+a_n}{2}\\
S_{2n-1}=&(2n-1)a_n\\
S_{2n+1}=&(2n+1)a_{n+1}
}
\end{aligned}
$$

性质

1、$\forall a_m,a_n, \ a_n=a_m+(n-m)d$

2、$a_1+a_n=a_2+a_{n-1}=a_3+a_{n-2}=\cdots =a_k+a_{n-k+1},k\in\mathbb{N^+}$

3、$m,n,p,q\in\mathbb{N^+}, \ m+n=p+q$，有$a_m+a_n=a_p+a_q$。

4、$\forall k\in\mathbb{N^+}$，有$S_k,S_{2k}-S_k,\cdots ,S_{nk}-S_{(n-1)k}$成等差数列。

等比数列（G.P.）

等比中项

$$
G^2=ab
$$

通项公式

$$
\begin{aligned}
\displaylines{
a_n=&a_1q^{n-1}\\
a_n=&S_n-S_{n-1},n\geq 2
}
\end{aligned}
$$

前$n$项和

$$
S_n=\begin{cases}
\displaylines{
\displaystyle\frac{a_1(1-q^n)}{1-q} & :q\neq 1\\
na_1 & :q=1
}
\end{cases}
$$

性质

1、$m,n,p,q\in\mathbb{N^+}, \ m+n=p+q$，则$a_ma_n=a_pa_q$。

2、在等比数列中，依次每$k$项之和仍成等比数列。

3、$a_1a_n=a_2a_{n-1}=a_3a_{n-2}=\cdots =a_ka_{n-k+1}, \ k\in{1,2,\cdots,n}$

4、$\forall a_m,a_n, \ a_n=a_mq^{(n-m)}$

概率与数学期望

在概率论中，我们把一个随机试验的某种可能结果称为样本点 ，把所有可能的结果构成的集合称为样本空间 。在一个给定的样本空间中，随机事件 就是样本空间的子集，即由若干个样本点构成的集合，随机变量 就是把样本点映射为实数的函数。随机变量分为离散型与连续型两种，离散型随机变量就是取值有限或可数的随机变量。

定义

设样本空间$\Omega$，$\forall A\in\Omega, \ \exist P(A)\in\mathbb{R}$，$A$为随机事件，满足：
1、$P(A)\geq 0$
2、$P(\Omega)=1$
3、对于若干个两两互斥事件$A_1,A_2,\cdots$有$\displaystyle \sum_i P(A_i)=P\left(\bigcup_i A_i\right)$。
则称$P(A)\in\mathbb R$为随机事件$A$发生的概率 ，$0\leq P(A)\leq 1$。

若随机变量$X$的取值有$x_1,x_2,\cdots$，一个随机事件可以表示为$X=x_i$，其概率为$P(X=x_i)=p_i$，则称$\displaystyle E(x)=\sum_i p_ix_i=\sum_{\omega\in\Omega}X(\omega)P(\omega)$为随机变量$X$的数学期望 ，数学期望是线性函数。

性质

1、期望的线性性&乘积的期望： $E(aX+bY)=aE(X)+bE(Y)$

2、全期望公式： 设$X,Y$是随机变量，$\displaystyle E(Y)=\sum_iP(X=x_i)E[Y\mid(X=x_i)]$。

古典定义

如果一个试验满足两条：
1、试验只有有限个基本结果；
2、试验的每个基本结果出现的可能性是一样的；

这样的试验便是古典试验。对于古典试验中的事件$A$，它的概率定义为$\displaystyle P(A)=\frac{m}{n}$，其中$n$表示该试验中所有可能出现的基本结果的总数目，$m$表示事件$A$包含的试验基本结果数。

统计定义

如果在一定条件下，进行了$n$次试验，事件$A$发生了$N_A$次，如果随着$n$逐渐增大，频率$\displaystyle \frac{N_A}{n}$逐渐稳定在某一数值$p$附近，那么数值$p$称为事件$A$在该条件下发生的概率，记做$P(A)=p$。

公理化定义

设$E$是随机试验，$S$是它的样本空间（事件空间的同义词）。对$E$的每一个事件$A$赋予一个实数，记为$P(A)$，称为事件$A$的概率。这里$P(A)$是一个从集合到实数的映射，$P(A)$满足以下公理：

非负性： 对于一个事件$A$，有概率$P(A)\in[0,1]$。

规范性： $P(S)=1$。

可加性： 若$A\cap B=\emptyset$，则$P(A\cup B)=P(A)+P(b)$。

由$(S,P)$构成的这样的一个系统称为一个概率空间 。

计算

广义加法公式： 对任意两个事件$A,B$，$P(A\cup B)=P(A)+P(B)-P(A\cap B)$。

条件概率： 记$P(B\mid A)$表示在$A$事件发生的前提下，$B$事件发生的概率，则$\displaystyle P(B\mid A)=\frac{P(AB)}{P(A)}$（其中$P(AB)$为事件$A$和事件$B$同时发生的概率）。

乘法公式： $P(AB)=P(A)P(B\mid A)=P(B)P(A\mid B)$

全概率公式： 若$\displaystyle \forall i,j, \ A_i\cap A_j=\emptyset, \ \sum_{i=1}^nA_i=1$，则有$\displaystyle P(B)=\sum_{i=1}^nP(A_i)P(B\mid A_i)$。

贝叶斯定理： $\displaystyle P(B_i\mid A)=\frac{P(B_i)P(A\mid B_i)}{\displaystyle \sum_{j=1}^nP(B_j)P(A\mid B_j)}$

独立性

随机事件的独立性

我们称两个事件 $A,B$独立 ，当$P(A\cap B)=P(A)P(b)$。

我们称若干个事件$A_i,i\in[1,n]$互相独立 ，当对于其中任何一个子集，该子集中的事件同时发生的概率，等于其中每个事件发生概率的乘积。形式化地说：
$$
P\left(\bigcap_{E\in T}{E}\right)=\prod_{E\in T}P(E), \ \forall T\subseteq\bigcup_{i=1}^n{A_i}
$$

随机变量的独立性

$I(X)$表示随机变量$X$的取值范围。

我们称两个随机变量 $X,Y$独立 ，当$P[(X=\alpha)\cap (Y=\beta)]=P(X=\alpha)P(Y=\beta), \ \forall\alpha\in I(X), \ \beta\in I(Y)$，即$(X,Y)$取任意一组值的概率，等于$X$和$Y$分别取对应值的概率乘积。

我们称若干个随机变量$X_i, \ i\in[1,n]$互相独立 ，当$(X_1,\cdots,X_n)$取任意一组值的概率，等于每个$X_i$分别取对应值的概率乘积。形式化地说：
$$
P\left(\bigcap_{i=1}^nX_i=F_i\right)=\prod_{i=1}^nP(X_i=F_i), \ \forall F_i\in I(X_i), \ i\in [1,n]
$$

事件的计算

和事件： 相当于并集 。若干个事件中只要其中之一发生，就算发生了它们的和事件。

积事件： 相当于交集 。若干个事件必须全部发生，才算发生了它们的积事件。

取模运算

基本性质

1、若$p\mid(a-b)$，则$\displaystyle a\equiv b\pmod p$。

2、$\displaystyle a\bmod p=b\bmod p$意味$\displaystyle a\equiv b\pmod p$。

3、对称性：$\displaystyle a\equiv b\pmod p$等价于$\displaystyle b\equiv a\pmod p$。

4、传递性：若$\displaystyle a\equiv b\pmod p, \ b\equiv c\pmod p$，则$\displaystyle a\equiv c\pmod p$。

运算法则

1、
$$
(a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p
$$
2、
$$
(a-b)\bmod p=(a\bmod p-b\bmod p)\bmod p
$$
3、
$$
(ab)\bmod p=[(a\bmod p)(b\bmod p)]\bmod p
$$
4、
$$
a^b\bmod p=\left[{(a\bmod p)}^b\right]\bmod p
$$
5、结合律
$$
\begin{aligned}
\displaylines{
\left[(a+b)\bmod p+c\right]\bmod p=&[a+(b+c)\bmod p]\bmod p\\
{[(ab)\bmod p]c}\bmod p=&{a[(bc)\bmod p]}\bmod p
}
\end{aligned}
$$
6、交换律
$$
\begin{aligned}
\displaylines{
(a+b)\bmod p=&(b+a)\bmod p\\
(ab)\bmod p=&(ba)\bmod p
}
\end{aligned}
$$
7、分配率
$$
\begin{aligned}
\displaylines{
(a+b)\bmod p=&(a\bmod p+b\bmod p)\bmod p\\
{[(a+b)\bmod p]c}\bmod p=&[(ac)\bmod p+(bc)\bmod p]\bmod p
}
\end{aligned}
$$

重要定理

1、若$\displaystyle a\equiv b\pmod p$，则$\displaystyle \forall c, \ a+c\equiv b+c\pmod p$。

2、若$\displaystyle a\equiv b\pmod p$，则$\displaystyle \forall c, \ ac\equiv bc\pmod p$。

3、若$\displaystyle a\equiv b\pmod p, \ c\equiv d\pmod p$，则$\displaystyle a+c\equiv b+d\pmod p, \ a-c\equiv b-d\pmod p, \ ac\equiv bd\pmod p$。

秦九韶算法

$$
\begin{aligned}
\displaylines{
&f(x)\\
=&\sum_{i=0}^na_ix^i\\
=&\left(\sum_{i=1}^na_ix^{i-1}\right)x+a_0\\
=&\left[\left(\sum_{i=2}^na_ix^{i-2}\right)x+a_1\right]x+a_0\\
&\qquad\qquad\qquad\vdots\\
=&{\cdots[(a_nx+a_{n-1})x+a_{n-2}]x+\cdots +a_1}x+a_0
}
\end{aligned}
$$

---

$$
\begin{aligned}
\displaylines{
v_1&=a_nx+a_{n-1}\\
v_2&=v_1x+a_{n-2}\\
&\qquad\vdots\\
f(x)=v_n&=v_{n-1}x+a_0
}
\end{aligned}
$$

对于一个$n$次多项式，至多做$n$次乘法和$n$次加法。

int sum=a[n];
for(register int i=n;i>=1;i--)
	sum=(sum*k+a[i-1])%P;

偏导数

设函数$z=f(x,y)$在点$(x_0,y_0)$的某一邻域内有定义，当$y$固定在$y_0$而$x$在$x_0$处有增量$\Delta x$时，相应地函数有增量$f(x_0+\Delta x,y_0)-f(x_0,y_0)$，如果$\displaystyle\lim_{\Delta x\rightarrow 0}\frac{f(x_0+\Delta x,y_0)-f(x_0,y_0)}{\Delta x}$存在，则称此极限为函数$z=f(x,y)$在点$(x_0,y_0)$处对$x$的偏导数，记为$\displaystyle\left.\frac{\partial z}{\partial x}\right|{x=x_0, \ y=y_0}$，$\displaystyle\left.\frac{\partial f}{\partial x}\right|{x=x_0, \ y=y_0}$，$\displaystyle\left.z_x\right|_{x=x_0, \ y=y_0}$或$f_x(x_0,y_0)$。

同理可定义函数$z=f(x,y)$在点$(x_0,y_0)$处对$y$的偏导数，为$\displaystyle\lim_{\Delta y\rightarrow 0}\frac{f(x_0,y_0+\Delta y)-f(x_0,y_0)}{\Delta y}$，记为$\displaystyle\left.\frac{\partial z}{\partial y}\right|{x=x_0, \ y=y_0}$，$\displaystyle\left.\frac{\partial f}{\partial y}\right|{x=x_0, \ y=y_0}$，$\displaystyle\left.z_y\right|_{x=x_0, \ y=y_0}$或$f_y(x_0,y_0)$。

如果函数$z=(x,y)$在区域$D$内任意一点$(x,y)$处对$x$的偏导数都存在，那么这个偏导数就是$x$、$y$的函数，它就称为函数$z=f(x,y)$对自变量$x$的偏导数，记作$\dfrac{\partial z}{\partial x}$，$\dfrac{\partial f}{\partial x}$，$z_x$或$f_x(x,y)$。

同理可以定义函数$z=f(x,y)$对自变量$y$的偏导数，记作$\dfrac{\partial z}{\partial y}$，$\dfrac{\partial f}{\partial y}$，$z_y$或$f_y(x,y)$。

偏导数的概念可以推广到二元以上函数，如$u=f(x,y,z)$在$(x,y,z)$处：
$$
\begin{aligned}
\displaylines{
f_x(x,y,z)=&\lim_{\Delta x\rightarrow 0}\frac{f(x+\Delta x,y,z)-f(x,y,z)}{\Delta x}\\
f_y(x,y,z)=&\lim_{\Delta y\rightarrow 0}\frac{f(x,y+\Delta y,z)-f(x,y,z)}{\Delta y}\\
f_z(x,y,z)=&\lim_{\Delta z\rightarrow 0}\frac{f(x,y,z+\Delta z)-f(x,y,z)}{\Delta z}
}
\end{aligned}
$$

高阶偏导数

二阶及二阶以上的偏导数统称为高阶偏导数。函数$z=f(x,y)$的二阶偏导数为：

纯偏导

$$
\begin{aligned}
\displaylines{
\frac{\partial}{\partial x}\left(\frac{\partial z}{\partial x}\right)=&\frac{\partial^2z}{\partial x^2}=f_{xx}(x,y),\\
\frac{\partial}{\partial y}\left(\frac{\partial z}{\partial y}\right)=&\frac{\partial^2z}{\partial y^2}=f_{yy}(x,y)
}
\end{aligned}
$$

混合偏导

$$
\begin{aligned}
\displaylines{
\frac{\partial}{\partial y}\left(\frac{\partial z}{\partial x}\right)=&\frac{\partial^2z}{\partial x\partial y}=f_{xy}(x,y),\\
\frac{\partial}{\partial x}\left(\frac{\partial z}{\partial y}\right)=&\frac{\partial^2z}{\partial y\partial x}=f_{yx}(x,y)
}
\end{aligned}
$$

Lagrange乘数法

多元函数极值

求函数$f(x,y)=3axy-x^3-y^3(a>0)$的极值。

解：
解方程组
$$
\begin{cases}
\displaylines{
f_x=3ay-3x^2=0\\
f_y=3ax-3y^2=0
}
\end{cases}
$$
驻点$(0,0),(a,a)$。
$$
A=f_{xx}=-6x, \ B=f_{xy}=3a, \ C=f_{yy}=-6y
$$
在点$(0,0)$处，$AC-B^2=\left.(36xy-9x^2)\right|_{(0,0)}=-9a^2<0$
$\therefore f(0,0)$不是极值。
在点$(a,a)$处，$AC-B^2=\left.(36xy-9a^2)\right|_{(a,a)}=27a^2>0$且$A=-6a<0$
$\therefore f(a,a)=a^3$是极大值。

Lagrange乘数法

求函数$z=f(x,y)$在条件$\varphi(x,y)=0$下的可能极值点，先构造拉格朗日函数
$$
\displaylines{
L(x,y,\lambda)=f(x,y)+\lambda\varphi(x,y)\\
\mathrm{s.t.}
\begin{cases}
L_x’=f_x(x,y)+\lambda\varphi_x(x,y)=0\\
L_y’=f_y(x,y)+\lambda\varphi_y(x,y)=0\\
L_{\lambda}’=\varphi(x,y)=0
\end{cases}
}
$$
解出$x,y,\lambda$，其中$x,y$就是可能的极值点的坐标。

---

（温州高三一模）已知$x,y,z\in\mathbb R^+, \ x+y+z=1$，则$\sqrt{xy}+\sqrt{xz}-y-z$的最大值为_。

$$
\displaylines{
f(x,y,z)=\sqrt{xy}+\sqrt{xz}-y-z+\lambda(x+y+z-1)\\
\begin{cases}
f’(x)=\dfrac{\sqrt y}{2\sqrt x}+\dfrac{\sqrt z}{2\sqrt x}+\lambda=0\\
f’(y)=\dfrac{\sqrt x}{2\sqrt y}-1+\lambda=0\\
f’(z)=\dfrac{\sqrt x}{2\sqrt z}-1+\lambda=0
\end{cases}
}
$$

由$f’(x)-f’(y)=\dfrac{\sqrt y}{2\sqrt x}+\dfrac{\sqrt z}{2\sqrt x}-\dfrac{\sqrt x}{2\sqrt y}+1=0$
$\therefore x+2y=1$，原式化简为：$24y^2-12y+1=0$
$$
\displaylines{
y_1=\frac{3-\sqrt 3}{12}\\
y_2=\frac{3+\sqrt 3}{12}
}
$$
$\therefore y=z=\dfrac{3-\sqrt 3}{12}$，带回$x+y+z=1, \ x=\dfrac{3+\sqrt 3}{6}$
$\therefore \sqrt{xy}+\sqrt{xz}-y-z$最大值为$\dfrac{\sqrt 3-1}{2}$。

---

已知$5x^2y^2+y^4=1, \ x,y\in\mathbb R$，则$x^2+y^2$的最小值是_。

解：
设$a=x^2, \ b=y^2$，转为求$a+b$的最小值。
$$
\displaylines{
f(a,b)=a+b+\lambda(5ab+b^2-1)\\
\begin{cases}
f’(a)=1+5\lambda b=0\\
f’(b)=1+5\lambda a+2\lambda b=0
\end{cases}
}
$$
整理得：$5\lambda b=5\lambda a+2\lambda b\Rightarrow 5b=5a+2b\Rightarrow 3b=5a$
$$
a=\frac{3}{5}b, \ 3b^2+b^2=1, \ b^2=\frac{1}{4}, \ b=\frac{1}{2}, \ a=\frac{3}{10}
$$
$\therefore a+b=\dfrac{4}{5}$

积分

积分
$\displaystyle\int\mathrm dx$	$x$
$\displaystyle\int x^n\mathrm dx$	$\dfrac{x^{n+1}}{n+1}$
$\displaystyle\int\frac{\mathrm dx}{x}$	$\ln x$
$\displaystyle\int e^x\mathrm dx$	$e^x$
$\displaystyle\int a^x\mathrm dx$	$\dfrac{a^x}{\ln a}$
$\displaystyle\int\sin x\mathrm dx$	$-\cos x$
$\displaystyle\int\cos x\mathrm dx$	$\sin x$
$\displaystyle\int\tan x\mathrm dx$	$-\ln\cos x$
$\displaystyle\int\cot x\mathrm dx$	$\ln\sin x$
$\displaystyle\int\frac{\mathrm dx}{\cos^2x}$	$\tan x$
$\displaystyle\int\frac{\mathrm dx}{\sin^2x}$	$-\cot x$

海伦公式

$$
\displaylines{
\begin{aligned}
S=&\sqrt{p(p-a)(p-b)(b-c)}\\
p=&\frac{a+b+c}{2}
\end{aligned}
}
$$

婆罗摩笈多公式

$$
\begin{aligned}
S=&\sqrt{(s-a)(s-b)(s-c)(s-d)}\\
s=&\frac{a+b+c+d}{2}
\end{aligned}
$$

Floyd

$O(n^3)$

memset(dis,0x3f,sizeof(dis));
for(register int i=1;i<=n;i++)
  	dis[i][i]=0;
for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n;j++)
		for(register int k=1;k<=n;k++)
			if((i!=j)&&(j!=k)&&(k!=i))
				dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);

最小环

memset(dis,0x3f,sizeof(dis));
memset(org,0x3f,sizeof(org));
for(register int i=1;i<=n;i++)
	dis[i][i]=org[i][i]=0;
for(register int i=1;i<=m;i++)
	t1=read(),
	t2=read(),
	t3=read(),
	dis[t1][t2]=min(dis[t1][t2],t3),
	dis[t2][t1]=min(dis[t2][t1],t3),
	org[t1][t2]=min(org[t1][t2],t3),
	org[t2][t1]=min(org[t2][t1],t3);
for(register int k=1;k<=n;k++){
	for(register int i=1;i<k;i++)
		for(register int j=i+1;j<k;j++)
			ret=min(ret,dis[i][j]+org[i][k]+org[k][j]);
	for(register int i=1;i<=n;i++)
		for(register int j=1;j<=n;j++)
			dis[j][i]=dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
};
if(ret!=0x3f3f3f3f3f3f3f3f)
	printf("%d\n",ret);
else
	printf("No solution.\n");

中继点计数

for(register int i=1;i<=n;i++)
	dis[i][i]=0;
for(register int i=1;i<=m;i++)
	t1=read(),
	t2=read(),
	dis[t1][t2]=dis[t2][t1]=read(),
	cnt[t1][t2]=cnt[t2][t1]=1;
for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n;j++)
		for(register int k=1;k<=n;k++)
			if((i!=j)&&(j!=k)&&(i!=k)){
				if(dis[j][k]>dis[j][i]+dis[i][k]){
					dis[j][k]=dis[j][i]+dis[i][k],
					cnt[j][k]=cnt[j][i]*cnt[i][k];
					continue;
				};
				if(dis[j][k]==dis[j][i]+dis[i][k])
					cnt[j][k]+=cnt[j][i]*cnt[i][k];
			};
for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n;j++)
		for(register int k=1;k<=n;k++)
			if((i!=j)&&(j!=k)&&(i!=k)&&(dis[j][k]==dis[j][i]+dis[i][k]))
				...

Kruskal

$O(m\log m)$

struct data{
	int s,e,w;
}e[N+1];
sort(e,e+n,cmp);
for(register int i=0;i<n;i++)
	if(find(e[i].s)!=find(e[i].e)){
		ans+=e[i].w;
		unio(e[i].s,e[i].e);
	};

Dijkstra

$O(m\log n)$

邻接矩阵

$O(n^2)$

const int inf=1e8,start=1;
int t1,t2,t3,a[N+1][N+1],dis[N+1],rec,v,e;
bool check[N+1];
scanf("%d%d",&v,&e);
for(register int i=1;i<=v;i++)
	for(register int j=1;j<=v;j++)
		a[i][j]=i^j?inf:0;
for(register int i=0;i<e;i++){
	scanf("%d%d%d",&t1,&t2,&t3);
	a[t1][t2]=t3;
};
for(register int i=1;i<=v;i++)
	dis[i]=a[start][i];
check[start]=true;
for(register int i=1;i<=v-1;i++){
	minn=inf;
	for(register int j=1;j<=v;j++)
		if((check[j]==false)&&(dis[j]<minn))
			minn=dis[rec=j];
	check[rec]=true;
	for(register int j=1;j<=v;j++)
		dis[j]=min(dis[j],dis[rec]+a[rec][j]);
};

最短路计数

priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > >q;
int main(void){
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0,
	ans[1]=1;
	q.push(make_pair(0,1));
	while(q.empty()==false){
		rec=q.top().second;
		q.pop();
		if(vis[rec]==true)
			continue;
		vis[rec]=true;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis[ver[i]]>dis[rec]+1){
				dis[ver[i]]=dis[rec]+1,
				ans[ver[i]]=ans[rec];
				q.push(make_pair(-dis[ver[i]],ver[i]));
			}
			else
				if(dis[ver[i]]==dis[rec]+1)
					ans[ver[i]]=(ans[ver[i]]+ans[rec])%100003;
	};
	return 0;
};

路径输出

priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > >q;
void dij(const int start){
	int rec=0;
	for(register int i=1;i<=n;i++)
		dis[i]=map[start][i],
		path[i]=-1;
 	if(vis[start]==true)
		continue;
	vis[start]=true;
	q.push(make_pair(-dis[start],start));
	while(q.empty()==false){
		rec=q.top().second;
		q.pop();
		vis[rec]=true;
		for(register int i=head[rec];i!=0;i=next[i])
			if((vis[ver[i]]==false)&&(dis[ver[i]]>dis[rec]+edge[i])){
				dis[ver[i]]=dis[rec]+edge[i],
                path[ver[i]]=rec;
				q.push(make_pair(-dis[ver[i]],ver[i]));
			};
	};
	return void();
};
void prt(void){
	for(register int i=2;i<=n;i++){
		printf("%d ",i);
		p=i;
		while(path[p]!=-1){
			printf("%d ",path[p]);
			p=path[p];
		};
		printf("1\n");
	};
	return void();
};

次短路径

遍历所有最短路上的边，将其删除，再跑最短路，求出的最小值为次短路。如果相等，严格次短路为次小值。

struct data{
	int x,y,z;
}rec[];
priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> >>q[2];
void dij(const int id,const int k){
	memset(vis,false,sizeof(vis));
	q[id].push(make_pair(-dis[id][k],k));
	dis[id][k]=0;
	while(q[id].empty()==false){
		ret=q[id].top().second;
		q[id].pop();
		if(vis[ret]==true)
			continue;
		vis[ret]=true;
		for(register int i=head[ret];i!=0;i=next[i])
			if((vis[ver[i]]==false)&&(dis[id][ver[i]]>dis[id][ret]+edge[i])){
				dis[id][ver[i]]=dis[id][ret]+edge[i];
				q[id].push(make_pair(-dis[id][ver[i]],ver[i]));
			};
	};
	return void();
};
int main(void){
	memset(dis,0x7f,sizeof(dis));
	ans=min2=2100000000;
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++){
		rec[i].x=read(),
		rec[i].y=read(),
		rec[i].z=read();
		add(rec[i].x,rec[i].y,rec[i].z);
		add(rec[i].y,rec[i].x,rec[i].z);
	};
	dij(0,1);
	dij(1,n);
	min1=dis[0][n];
	for(register int i=1;i<=m;i++){
		t1=rec[i].x,
		t2=rec[i].y;
		if(dis[0][t1]+dis[1][t2]>dis[0][t2]+dis[1][t1])
			swap(t1,t2);
		if(dis[0][t1]+dis[1][t2]+rec[i].z==min1)
			continue;
		ans=min(ans,dis[0][t1]+dis[1][t2]+rec[i].z);
	};
	for(register int i=1;i<=m;i++){
		t1=rec[i].x,
		t2=rec[i].y;
		if(dis[0][t1]+dis[1][t2]>dis[0][t2]+dis[1][t1])
            t1^=t2^=t1^=t2;
		if(dis[0][t1]+dis[1][t2]+rec[i].z!=min1)
			continue;
		min2=min(min2,rec[i].z);
	};
	printf("%d\n",min(ans,min1+(min2<<1)));
	return 0;
};

Prim

$O(n^2+m)$

void prim(const int start){
	memset(dis,0x3f,sizeof(dis));
	dis[start]=0;
	for(register int i=1;i<=n;i++){
		minn=INF;
		for(register int j=1;j<=n;j++)
			if((vis[j]==false)&&(dis[j]<minn))
				minn=dis[j],
				rec=j;
		ans+=minn,
		vis[rec]=true;
		for(register int j=1;j<=n;j++)
			dis[j]=min(dis[j],mp[rec][j]);
	};
	return void();
};

堆优化

$O((n+m)\log n)$

priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > >q;
void prim(const int start){
	memset(dis,0x3f,sizeof(dis));
	dis[start]=0;
	q.push(make_pair(-dis[start],start));
	while((q.empty()==false)&&(cnt<n)){
		len=q.top().first,
		rec=q.top().second;
		q.pop();
		if(vis[rec]==true)
			continue;
		vis[rec]=true,
		cnt++,
		sum+=len;
		for(register int i=head[rec];i!=0;i=nxt[i])
			if(dis[ver[i]]>edge[i]){
				dis[ver[i]]=edge[i];
				q.push(make_pair(-dis[ver[i]],ver[i]));
			};
	};
	if(cnt==n)
		printf("%d\n",sum);
	return void();
};

SPFA

$O(nm)$

queue<int> q;
int main(void){
	fill(dis+1,dis+n+1,2147483647);
	dis[start]=0,
	vis[start]=true;
	q.push(start);
	while(q.empty()==false){
		rec=q.front();
		q.pop();
		vis[rec]=false;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis[ver[i]]>dis[rec]+edge[i]){
				dis[ver[i]]=dis[rec]+edge[i];
				if(vis[ver[i]]==false){
					vis[ver[i]]=true;
					q.push(ver[i]);
				};
			};
	};
	return 0;
};

判负环

bool spfa(const int start){
	int rec=0;
	q.push(start);
	vis[start]=true,
	dis[start]=0;
	while(q.empty()==false){
		rec=q.front();
		q.pop();
		vis[rec]=false;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis[ver[i]]>dis[rec]+edge[i]){
				dis[ver[i]]=dis[rec]+edge[i],
				if(vis[ver[i]]==false){
					vis[ver[i]]=true;
					q.push(ver[i]);
                    cnt[ver[i]]++;
                    if(cnt[ver[i]]>=n+1)
                        return true;
				};
			};
	};
	return false;
};
if(spfa(1)==true)
	printf("有负环\n");
else
	printf("无负环\n");

SLF优化

deque<int>q;
...
rec=q.front();
q.pop_front();
...
if(vis[ver[i]]==false){
	vis[ver[i]]=true;
	if((q.empty()==false)&&(dis[ver[i]]<dis[q.front()]))
		q.push_front(ver[i]);
	else
		q.push_back(ver[i]);
};
...

LLL优化

...
rec=q.front();
q.pop();
if(dis[rec]*cnt>sum){
	q.push(p);
	continue;
};
sum-=dis[p],
cnt--,
...
if(vis[ver[i]]==false){
	vis[ver[i]]=true;
	q.push(ver[i]);
	cnt++;
	sum+=dis[ver[i]];
};
...

Kosaraju

$O(n+m)$

void dfs(const int k){
    vis[k]=true;
    for(register int i=head[k];i!=0;i=next[i])
        if(vis[ver[i]]==false)
            dfs(ver[i]);
    rec.push_back(k);
    return void();
};
void rev_dfs(const int k,const int val){
    vis[k]=true,
    mrk[k]=val;
    for(register int i=rev_head[k];i!=0;i=rev_next[i])
        if(vis[rev_ver[i]]==false)
            rev_dfs(rev_ver[i],val);
    return void();
};
int kosaraju(void){
    int ret=0;
    for(register int i=1;i<=n;i++)
        if(vis[i]==false)
            dfs(i);
    memset(vis,false,sizeof(vis));
    for(vector<int>::reverse_iterator it=rec.rbegin();it!=rec.rend();it++)
        if(vis[*it]==false)
            rev_dfs(*it,ret++);
    return ret;
};
bool judge(void){
    memset(vis,false,sizeof(vis));
    for(register int i=1;i<=n;i++)
        if(mrk[i]==cnt-1)
            src=i,
            sum++;
    rev_dfs(src,1);
    for(register int i=1;i<=n;i++)
        if(vis[i]==false)
            return false;
    return true;
};

Tarjan

给定无向连通图$G=(V,E)$。

若对于$x\in V$，从图中删去节点$x$以及所有与$x$关联的边之后，$G$分裂成两个或两个以上不相连的子图，则称$x$为$G$的割点 。

若对于$e\in E$，从图中删去边$e$之后，$G$分裂成两个不相连的子图，则称$e$为$G$的桥 或割边 。

$O(n+m)$

无向图割边

割边判定定理

无向边$(x,y)$是桥，当且仅当搜索树上存在$x$的一个子节点$y$，满足：
$$
dfn_x<low_y
$$
桥一定是搜索树中的边，一个简单环中的边一定都不是桥。

inline void add(const int x,const int y){
	ver[++tot]=y,
	next[tot]=head[x],
	head[x]=tot;
	return void();
};
void tarjan(const int k,const int e){
	dfn[k]=low[k]=++nmb;
	for(register int i=head[k];i!=0;i=next[i])
		if(dfn[ver[i]]==0){
			tarjan(ver[i],i);
			low[k]=min(low[k],low[ver[i]]);
			if(dfn[k]<low[ver[i]])//割边判定法则：dfn[x]<low[y]
				vis[i]=vis[i^1]=true;
		}
		else
			if(i!=(e^1))//成对变换
				low[k]=min(low[k],dfn[ver[i]]);
	return void();
};
tot=1;//2、3 4、5...
for(register int i=1;i<=m;i++){
	t1=read(),
	t2=read();
	add(t1,t2);
	add(t2,t1);
};
for(register int i=1;i<=n;i++)
	if(dfn[i]==0)
		tarjan(i,0);
for(register int i=2;i<tot;i+=2)
	if(vis[i]==true)
		printf("%d %d\n",ver[i^1],ver[i]);

无向图割点

割点判定法则

若$x$不是搜索树的根节点（DFS的起点），则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$，满足：
$$
dfn_x\leq low_y
$$
特别地，若$x$是搜索树的根节点，则$x$是割点当且仅当搜索树上存在至少两个子节点$y_1,y_2$满足上述条件。

void tarjan(const int k){
	int cnt=0;
	dfn[k]=low[k]=++nmb,
	for(register int i=head[k];i!=0;i=next[i])
		if(dfn[ver[i]]==0){
			tarjan(ver[i]);
			low[k]=min(low[k],low[ver[i]])；
			if(dfn[k]<=low[ver[i]]){
				cnt++;
				if((k!=1)||(cnt>1))
					chk[k]=true;
			};//割点判定法则：不是根节点：dfn[n]<=low[y]
		}     //              是根节点：至少存在2个满足
		else
			low[k]=min(low[k],dfn[ver[i]]);
	return void();
};

LCA

vector<pair<int,int> >ques[];
void dfs(const int start,const int last){
	for(register int i=head[start];i!=0;i=next[i])
		if(ver[i]!=last){
			dfs(ver[i],start);
			unio(ver[i],start);
		};
	for(register int i=0;i<ques[start].size();i++)
		if(vis[ques[start].at(i).first]==true)
			ans[ques[start].at(i).second]=getf(ques[start].at(i).first);
	vis[start]=true;
	return void();
};
int main(void){
	scanf("%d%d%d",&n,&m,&s);
	for(register int i=1;i<=n;fa[i]=i,i++);
		for(register int i=1;i<=n-1;i++){
			t1=read(),
			t2=read();
			add(t1,t2);
			add(t2,t1);
		};
	for(register int i=1;i<=m;i++){
		t1=read(),
		t2=read();
		ques[t1].push_back(make_pair(t2,i));
		ques[t2].push_back(make_pair(t1,i));
	};
	dfs(s,0);
	for_each(ans+1,ans+m+1,f);
	return 0;
};

Johnson

$O(nm\log m)$

void spfa(const int start){
	memset(dis1,0x7f,sizeof(dis1));
	dis1[start]=0,
	vis[start]=true,
	q1.push(start);
	while(q1.empty()==false){
		rec=q1.front();
		q1.pop();
		vis[rec]=false;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis1[ver[i]]>dis1[rec]+edge[i]){
				dis1[ver[i]]=dis1[rec]+edge[i];
				if(vis[ver[i]]==false){
					vis[ver[i]]=true;
					q1.push(ver[i]);
					hal[ver[i]]++;
					if(hal[ver[i]]>=n+1){
						flag=true;
						return void();
					};
				};
			};
	};
	return void();
};
void dij(const int start){
	memset(vis,false,sizeof(vis));
	for(register int i=1;i<=n;dis2[i++]=INF);
	dis2[start]=0,
	vis[start]=false;
	q2.push(make_pair(-dis2[start],start));
	while(q2.empty()==false){
		rec=q2.top().second;
		q2.pop();
		if(vis[rec]==true)
			continue;
		vis[rec]=true;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis2[ver[i]]>dis2[rec]+edge[i]){
				dis2[ver[i]]=dis2[rec]+edge[i];
				if(vis[ver[i]]==false)
					q2.push(make_pair(-dis2[ver[i]],ver[i]));
			};
	};
	return void();
};
int main(void){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++){
		t1=read(),
		t2=read(),
		t3=read();
		if(t1==t2)
			continue;
		add(t1,t2,t3);
	};
	for(register int i=1;i<=n;add(0,i++,0));
	spfa(0);
	if(flag==true){
		printf("-1\n");
		return 0;
	};
	for(register int i=1;i<=n;i++)
		for(register int j=head[i];j!=0;j=next[j])
			edge[j]+=dis1[i]-dis1[ver[j]];
	for(register int i=1;i<=n;i++){
		dij(i);
		for(register int j=1;j<=n;j++)
			printf("dis[%d][%d]=%d\n",i,j,dis2[j]+dis1[j]-dis1[i]);
	};
	return 0;
};

分层图

// M=m*(2+k*4) N=n+k*n
priority_queue<pair<int,int>,vector<pair<int,int> > ,less<pair<int,int> > >q;
int main(void){
	memset(dis,0x7f,sizeof(dis));
	for(register int i=1;i<=m;i++){
		t1=read(),
		t2=read(),
		t3=read();
		add(t1,t2,t3);
		add(t2,t1,t3);
		for(register int j=1;j<=k;j++){
			add(t1+n*j,t2+n*j,t3);
			add(t2+n*j,t1+n*j,t3);
			add(t1+n*(j-1),t2+n*j,0);
			add(t2+n*(j-1),t2+n*j,0);
		};
	};
	dis[start]=0;
	q.push(make_pair(-dis[start],start));
	while(q.empty()==false){
		rec=q.top().second;
		q.pop();
		if(vis[rec]==true)
			continue;
		vis[rec]=true;
		for(register int i=head[rec];i!=0;i=next[i])
			if((vis[ver[i]]==false)&&(dis[ver[i]]>dis[rec]+edge[i])){
				dis[ver[i]]=dis[rec]+edge[i];
				q.push(make_pair(-dis[ver[i]],ver[i]));
			};
	};
	for(register int i=0;i<=k;i++)
		ans=min(ans,dis[end+n*i]);
	return 0;
};

差分约束系统

把每个变量$X_i$看作有向图中的一个节点$i$，对于每个约束条件$X_i-X_j\leq c_k$，从节点$j$向节点$i$连一条长度为$c_k$的有向边。

注意到如果$\displaystyle \bigcup_{i=1}^n{a_i}$是一组解，那么$\displaystyle \forall \Delta, \ \bigcup_{i=1}^n{a_i+\Delta}$显然也是一组解。所以不妨先求一组负数解，假设$\forall i, \ X_i\leq 0$，然后增加一个$0$号节点，令$X_0=0$。这样一来，就多了$N$个形如$X_i-X_0\leq 0$的约束条件，应从节点$0$向每个节点$i$连一条长度为$0$的有向边。

设$dist_0=0$，以$0$为起点求单源最短路。若图中存在负环，则给定的差分约束系统无解。否则，$X_i=dist_i$就是差分约束系统的一组解。

约束条件形如$X_i-X_j\geq c_k$，从$j$到$i$连长度为$c_k$的有向边，改为计算单源最长路，若图中有正环则无解。也可以把约束条件转化成$X_j-X_i\leq -c_k$，按照单源最短路进行计算。

注意加入$0$点后多出$m$条边。

(Bellman Ford)

int main(void){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&z);
		add_edge(y,x,z);
	};
	for(register long long int i=1;i<=n;i++)
		add(0,i,0);
	// memset(dis,0x3f,sizeof(dis));
	// dis[1]=0;非负(可能出现inf)
	for(register int i=1;i<=n-1;i++)
		for(register int j=1;j<=n;j++)
			for(register int k=head[j];k!=0;k=next[k])
				dis[ver[k]]=min(dis[ver[k]],dis[j]+edge[k]);
	for(register int i=1;i<=n;i++)
		for(register int j=head[i];j!=0;j=next[j])
			if(dis[ver[j]]>dis[i]+edge[j]){
				printf("NO\n");
				return 0;
			};
	// for(register int i=1;i<=n;i++)
	// minn=min(minn,dis[i]);
	// for(register int i=1;i<=n;i++)
	// printf(“%d”,dis[i]-minn);整体平移除负
	for_each(dis+1,dis+n+1,f);
	printf("\n");
	return 0;
};

SPFA最长路径

bool spfa(const int start){
	queue<int>q;
	memset(vis,false,sizeof(vis));
	memset(dis,-1,sizeof(dis));
	memset(in,0,sizeof(in));
	vis[start]=true,
	dis[start]=0,
	in[start]=1;
	q.push(start);
	while(q.empty()==false){
		rec=q.front();
		q.pop();
		vis[rec]=false;
		for(register int i=head[rec];i!=0;i=next[i])
			if(dis[ver[i]]<dis[rec]+edge[i]){
				dis[ver[i]]=dis[rec]+edge[i];
				if(vis[ver[i]]==false){
					vis[ver[i]]=true;
					q.push(ver[i]);
					in[ver[i]]++;
					if(in[ver[i]]>n+1)
						return false;
				};
			};
	};
	return true;
};
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
	u=read(),
	v=read(),
	w=read();
	add(u,v,-w);
};
for(register int i=1;i<=n;i++)
	add(0,i,0);
if(spfa(0)==true){
	for_each(dis+1,dis+n+1,f);
	putchar('\n');
}
else
	printf("NO\n");

树的直径

$O(n)$

void dfs1(const int k,const int last){
	if(deep[k]>maxn)
		maxn=deep[rec=k];
	for(register int i=head[k];i!=0;i=next[i])
		if(ver[i]!=last){
			deep[ver[i]]=deep[k]+1;
			dfs1(ver[i],k);
		};
	return void();
};
void dfs2(const int k,const int last){
	if(deep[k]>maxn)
		maxn=deep[rec=k];
	for(register int i=head[k];i!=0;i=next[i])
		if(ver[i]!=last){
			deep[ver[i]]=deep[k]+1,
			fa[ver[i]]=k;
			dfs2(ver[i],k);
		};
	return void();
};
void dfsk(const int k,const int last){
	maxdeep[k]=deep[k];
	for(register int i=head[k];i!=0;i=next[i])
		if(ver[i]!=last){
			deep[ver[i]]=deep[k]+1;
			dfsk(ver[i],k);
			maxdeep[k]=max(maxdeep[k],maxdeep[ver[i]]);
		};
	return void();
};
dfs1(1,0);
maxn=0;
memset(deep,0,sizeof(deep));
dfs2(rec,0);
cntr=rec;
for(register int i=1;i<=(deep[rec]+1)>>1;i++)
	cntr=fa[cntr];
memset(deep,0,sizeof(deep));
dfsk(cntr,0);
for(register int i=1;i<=n;i++)
	ans[i]=maxdeep[i]-deep[i];
sort(ans+1,ans+n+1,cmp);
for(register int i=K+1;i<=n;i++)
	maxans=max(maxans,ans[i]+1);

无向图双连通分量

若一张无向连通图不存在割点，则称为点双连通图 。若一张无向连通图不存在桥，则称它为边双连通图 。

无向图的极大点双连通子图被称为点双连通分量 ，简记为v-DCC 。无向连通图的极大边双连通子图被称为边双连通分量 ，简记为e-DCC 。二者统称为双连通分量 ，简记为DCC 。

一个双连通子图$G’=(V’,E’)$极大 （$V’\subseteq V,E’\subseteq E$），是指$\nexists G’’=(V’’,E’’)\supseteq G’,\ V’\subseteq V’’\subseteq V, \ E’\subseteq E’’\subseteq E$，$G’’$也是双连通子图。

定理

一张无向连通图是点双连通图，当且仅当满足下列两个条件之一：
1、图的顶点数不超过2。
2、图中任意两点都同事包含在至少一个简单环中。
简单环指的是不自交的环。

一张无向连通图是边双连通图，当且仅当任意一条边都包含在至少一个简单环中。

e-DCC

//省略Tarjan割边
void dfs(const long long int k){
	color[k]=cnt;
	for(register long long int i=head[k];i!=0;i=next[i])
		if((color[ver[i]]==0)&&(vis[i]==false))
			dfs(ver[i]);
	return void();
};
for(register int i=1;i<=n;i++)
	if(color[i]==0){
		cnt++;
		dfs(i);
	};
printf("%d\n",tot);
for(register int i=1;i<=n;i++)
	printf("%d=>%d\n",i,color[i]);

v-DCC

stack<int>stk;
vector<int>ans[];
void tarjan(const int k){
	int flag=0;
	dfn[k]=low[k]=++nmb;
	stk.push(k);
	if((k==rt)&&(head[k]==0)){
		ans[++cnt].push_back(k);
		return void();
	};//孤立点
	for(register int i=head[k];i!=0;i=next[i])
		if(dfn[ver[i]]==0){
			tarjan(ver[i]);
			low[k]=min(low[k],low[ver[i]]);
			if(dfn[k]<=low[ver[i]]){
				flag++;
				if((k!=rt)||(flag>1))
					chk[k]=true;
				cnt++,
                tmp=0;
				while(tmp!=ver[i]){
					tmp=stk.top();
					stk.pop();
					ans[cnt].push_back(tmp);
				};
				ans[cnt].push_back(k);
			};
		}
		else
			low[k]=min(low[k],dfn[ver[i]]);
	return void();
};
for(register int i=1;i<=m;i++)
	if(dfn[i]==0){
		rt=i;
		tarjan(i);
	};
for(register int i=1;i<=cnt;i++){
	printf("#%d:\n",i);
	for(register int j=0;j<ans[i].size();j++)
		printf("%d ",ans[i].at(j));
	putchar('\n');
};

缩点

e-DCC

inline void addc(const int x,const int y){
	verc[++totc]=y,
	nextc[totc]=headc[x],
	headc[x]=totc;
	return void();
};
totc=1;
for(register int i=2;i<=tot;i++)
	if(color[ver[i]]!=color[ver[i^1]])
		addc(color[ver[i]],color[ver[i^1]]);
//点数=tot 边数（有重边）=totc/2
for(register int i=2;i<totc;i+=2)
	printf("%d %d\n",verc[i],verc[i^1]);

v-DCC

nmb=cnt;
for(register int i=1;i<=n;i++)
	if(chk[i]==true)
		idc[i]=++nmb;
totc=1;
for(register int i=1;i<=cnt;i++)
	for(register int j=0;j<ans[i].size();j++)
		if(chk[ans[i].at(j)]==true){
			addc(i,idc[ans[i].at(j)]);
			addc(idc[ans[i].at(j)],i);
		}
		else
			color[ans[i].at(j)]=i;
//缩点后点数=num 边数=totc/2
//1~cnt为原图v-DCC编号 >cnt为原图割点
for(register int i=2;i<totc;i+=2)
	printf("%d %d\n",verc[i^1],ver[i]);

Hierholzer

给定一张无向图，若存在一条从节点$S$到节点$T$的路径，恰好不重不漏地经过每条边一次（可以重复经过图中的节点），则称该路径为$S$到$T$的欧拉路 。

特别地，若存在一条从节点$S$出发的路径，恰好不重不漏地经过每条边一次（可以重复经过图中的节点），最终回到起点$S$，则称该路径为欧拉回路 。存在欧拉回路的无向图被称为欧拉图 。

欧拉图判定

一张无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。

欧拉路存在性判定

一张无向图中存在欧拉路，当且仅当无向图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度数都是偶数。这两个度数为奇数的节点就是欧拉路的起点$S$和终点$T$。

---

有向图：
$O(nm+m^2)$
路径输出：$O(n+m\log m)$

vector<pair<int,int> >edge[];
stack<int>ans;
inline bool cmp(const pair<int,int>a,const pair<int,int>b){
	return a.first<b.first;
};
void dfs(const int k){
	for(register int i=rec[k];i<edge[k].size();i=fmax(i+1,rec[k]))
		if(vis[edge[k].at(i).second]==false){
			vis[edge[k].at(i).second]=true,
			rec[k]=i+1;
			dfs(edge[k].at(i).first);
		};
	ans.push(k);
	return void();
};
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
	t1=read(),
	t2=read(),
	out[t1]++,
	in[t2]++;
	edge[t1].push_back(make_pair(t2,i));
};

//欧拉路判定
for(register int i=1;i<=n;i++)
	if(out[i]!=in[i]){
		cnt++;
		if(in[i]+1==out[i])
			start=i;
		if(out[i]+1==in[i])
			ed=i;
	};
if((cnt!=0)&&(cnt!=2)){
	printf("No\n");
    return 0;
};
if(cnt==0)
	start=ed=1;
if((start==0)||(ed==0)){
	printf("No\n");
    return 0;
};

//字典序最小
for(register int i=1;i<=n;i++)
	sort(edge[i].begin(),edge[i].end(),cmp);

dfs(start);
while(ans.empty()==false){
	printf("%d ",ans.top());
	ans.pop();
};
putchar('\n');

有向图强连通分量

给定一张有向图。若对于图中任意两个节点$x,y$，既存在从$x$到$y$的路径，也存在从$y$到$x$的路径，则称该有向图是强连通图 。

有向图的极大强连通子图被称为强连通分量 。简记为SCC 。

SCC

强连通分量判定法则

在追溯值得计算过程中，若从$x$回溯前，有$low_x=dfn_x$成立，则栈中从$x$到栈顶的所有节点构成一个强连通分量。

void tarjan(const int k){
    dfn[k]=low[k]=++cnt,
    chk[k]=true;
    stk.push(k);
    for(register int i=head[k];i!=0;i=next[i])
        if(dfn[ver[i]]==0){
            tarjan(ver[i]);
            low[k]=min(low[k],low[ver[i]]);
        }
        else
            if(chk[ver[i]]==true)
                low[k]=min(low[k],dfn[ver[i]]);
    if(dfn[k]==low[k]){//SCC判定法则
        int tmp=0;
        col++,
        rec[col]++;
        while(true){
            tmp=stk.top();
            stk.pop();
            rec[col]++,
            color[tmp]=col,
            chk[tmp]=false;
            if(tmp==k)
                break;
        };
        //...
    };
    return void();
};
for(register int i=1;i<=n;i++)
	if(dfn[i]==0)
		tarjan(i);
for(register int i=1;i<=col;i++)
	if(rec[i]>maxn)
		maxn=rec[pos=i];
printf("%d\n",rec[pos]);
for(register int i=1;i<=n;i++)
	if(color[i]==pos)
		printf("%d ",i);

缩点

inline void addc(const int x,const int y){
	verc[++totc]=y,
	nextc[totc]=headc[x],
	headc[x]=totc;
	return void();
};
for(register int i=1;i<=n;i++)
	for(register int j=head[i];j!=0;j=next[j])
		if(color[i]!=color[ver[j]])
			addc(color[i],color[ver[j]]);

二分图

任意两条边都没有公共端点的边的集合被称为图的一组匹配 。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配 。

对于任意一组匹配$S$（$S$是一个边集），属于$S$的边被称为匹配边 ，不属于的边被称为非匹配边 。匹配边的端点被称为匹配点 ，其他节点被称为非匹配点 。

如果在二分图中存在一条连接两个非匹配点的路径$path$，使得非匹配边匹配边在$path$上交替出现，那么称$path$是匹配$S$的增广路。

性质&推论

1、长度$len\bmod 2=1$。
2、路径上第$1+2n$条边是非匹配边，第$2n$条边是匹配边。
3、二分图的一组匹配$S$是最大匹配，当且仅当图中不存在$S$的增广路。

二分图判定

$O(n+m)$

bool dfs(const long long int k,const long long int val){
	bool ret=true;
	color[k]=val;
	for(register long long int i=head[k];i!=0;i=nxt[i]){
		if(color[k]==color[ver[i]])
			ret=false;
		if((color[ver[i]]==0)&&(dfs(ver[i],3-val)==false))
			ret=false;
	};
	return ret;
};

匈牙利算法

二分图最大权匹配
$O(nm)$

vector<int>g[];
bool dfs(const int k){
	for(register int i=0;i<g[k].size();i++)
		if(vis[g[k].at(i)]==false){
			vis[g[k].at(i)]=true;
			if((rec[g[k].at(i)]==-1)||(dfs(rec[g[k].at(i)])==true)){
				rec[g[k].at(i)]=k;
				return true;
			};
		};
	return false;
};
inline void mag(void){
	memset(rec,-1,sizeof(rec));
	for(register int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		if(dfs(i)==true)
			sum++;
	};
	return void();
};
int main(void){
	scanf("%d%d%d",&n,&m,&e);
	for(register int i=1;i<=e;i++)
		g[t1].push_back(t2);
	mag();
	printf("%d\n",sum);
	return 0;
};

染色

void paint(const int k,const int col){
	color[k]=col;
	for(vector<int>::iterator it=a[k].begin();it!=a[k].end();it++)
		if(color[*it]==0)
			paint(*it,3-col);
	return void();
};
for(register int i=1;i<=n;i++)
	if(color[i]==0)
		paint(i,1);
//---------------------------------------
bool dfs(const int k){
	for(vector<int>::iterator it=a[k].begin();it!=a[k].end();it++)
		if(vis[*it]==false){
			vis[*it]=true;
			if((rec[*it]==0)||(dfs(rec[*it])==true)){
				rec[*it]=k;
				return true;
			};
		};
	return false;
};
int hgr(void){
	int ret=0;
	for(register int i=1;i<=n;i++){
      
		if(color[i]!=1)
			continue;
      
		memset(vis,false,sizeof(vis));
		if(dfs(i)==true)
			ret++;
	};
	return ret;
};

同余最短路

给定$m$个整数，求这$m$个整数能拼凑出多少的其他整数（这$m$个整数可以重复取）或给定$m$个整数，求这$m$个整数不能拼凑出的最小（最大）的整数（$\leq h$）。

对于$\forall r\in[1,a_1)$建立一个点，对于每个点$u$连一条到$v=(u+a_i)\bmod a_1, \ i\in[2,m]$的边，长度为$a_i$，从0开始跑最短路，可以到$\dfrac{h−dis_r}{a_1}+1$个整数。

int query(const int k){
	int ret=0;
	for(register int i=0;i<a[1];i++)
		if(dis[i]<=k)
			ret+=(k-dis[i])/a[1]+1;
	return ret;
};
for(register int i=0;i<a[1];i++)
	for(register int j=2;j<=n;j++)
		add(i,(i+a[j])%a[1],a[j]);
spfa(0);
printf("%d\n",query(h));//能拼凑出其他整数（≤h）的数量

建图

按边建图

struct data{
	int nl,nr,w;
	set<int>setl,setr;
	vector<int>vecl,vecr;
}a[101];
for(register int i=1;i<=n;i++){
	nmb=read(),
	a[nmb].w=read(),
	t1=read(),
	t2=read();
	for(register int j=1;j<=t1;j++){
		t3=read();
		a[nmb].setl.insert(t3);
		a[nmb].vecl.push_back(t3);
	};
	for(register int j=1;j<=t2;j++){
		t3=read();
		a[nmb].setr.insert(t3);
		a[nmb].vecr.push_back(t3);
	};
};
for(register int i=1;i<=n;i++){
	if(a[i].nl==0){
		a[i].nl=++tot;
		for(register int j=0;j<a[i].setl.size();j++){
			if(a[a[i].vecl[j]].setr.count(i)==1)
				a[a[i].vecl[j]].nr=a[i].nl;
			if(a[a[i].vecl[j]].setl.count(i)==1)
				a[a[i].vecl[j]].nl=a[i].nl;
		};
	};
	if(a[i].nr==0){
		a[i].nr=++tot;
		for(register int j=0;j<a[i].setr.size();j++){
			if(a[a[i].vecr[j]].setr.count(i)==1)
				a[a[i].vecr[j]].nr=a[i].nr;
			if(a[a[i].vecr[j]].setl.count(i)==1)
				a[a[i].vecr[j]].nl=a[i].nr;
		};
	};
};
for(register int i=1;i<=n;i++){
	add(a[i].nl,a[i].nr,a[i].w);
	add(a[i].nr,a[i].nl,a[i].w);
};

并查集

$O(\alpha(n))$

int fa[N+1],size[N+1];
for(register int i=0;i<n;fa[i]=i,size[i++]=1);
int find(const int x){//路径压缩
	return x==fa[x]?x:fa[x]=find(fa[x]);
};
inline void unio(const int a,const int b){
	const int ta=find(a),tb=find(b);
	fa[ta]=tb;
	return void();
};
inline void unio(const int a,const int b){//按秩合并
	int ta=find(a),tb=find(b);
	if(size[ta]>size[tb])
		swap(ta,tb);
	size[tb]+=size[ta],
	fa[ta]=tb,
	size[ta]=0;
	return void();
};

带权并查集

//dis：x到fa[x]的边权和 size：树根集合大小
for(register int i=1;i<=n;i++)
	fa[i]=i,
	size[i]=...;
int find(const int x){
	if(fa[x]==x)
		return x;
	const int root=find(fa[x]);
	dis[x]+=dis[fa[x]];
	return fa[x]=root;
};
inline void unio(const int a,const int b){
	const int ta=find(a),tb=find(b);
	if(ta==tb)
		return void();
	fa[ta]=tb,
	dis[ta]=size[tb],
	size[tb]+=size[ta];
	return void();
};

树状数组

$O(\log n)$

int a[N+1];
inline int lowbit(const int t){
	return t&-t;
};
void add(int pos,const int val){
	while(pos<=N)
		a[pos]+=val,
		pos+=lowbit(pos);
	return void();
};
int sum(int pos){
	int ret=0;
	while(pos>0)
		ret+=a[pos],
		pos-=lowbit(pos);
	return ret;
};

二维树状数组

inline int lowbit(const int x){
	return x&-x;
};
void add(int x,const int y,const int val){
	int ty=0;
	while(x<=n){
		ty=y;
		while(ty<=n)
			tree[x][ty]+=val,
			ty+=lowbit(ty);
		x+=lowbit(x);
	};
	return void();
};
int ask(int x,const int y){
	int res,ty;
	res=ty=0;
	while(x>0){
		ty=y;
		while(ty>0)
			res+=tree[x][ty],
			ty-=lowbit(ty);
		x-=lowbit(x);
	};
	return res;
};
////////////////////////////
void add(const int md,const int x,const int y,const int val){
    for(register int i=x;i<=n;i+=lowbit(i))
        for(register int j=y;j<=m;j+=lowbit(j))
            tree[md][i][j]+=val;
    return void();
};
int sum(const int md,const int x,const int y){
    int ret=0;
    for(register int i=x;i>0;i-=lowbit(i))
        for(register int j=y;j>0;j-=lowbit(j))
            ret+=tree[md][i][j];
    return ret;
};

逆序对

for(register int i=n;i>=1;i--){
    insert(a[i],1);
    ans+=query(a[i]-1);
};

区间种类数

inline bool cmp(const data a,const data b){
    return a.r<b.r;
};
inline int lowbit(const int x){
    return x&-x;
};
void add(int pos,const int val){
    while(pos<=n)
        tree[pos]+=val,
        pos+=lowbit(pos);
    return void();
};
int sum(int pos){
    int ret=0;
    while(pos>0)
        ret+=tree[pos],
        pos-=lowbit(pos);
    return ret;
};
int main(void){
    scanf("%d",&n);
    for(register int i=1;i<=n;a[i++]=read());
    scanf("%d",&m);
    for(register int i=1;i<=m;i++)
        qst[i].l=read(),
        qst[i].r=read(),
        qst[i].n=i;
    sort(qst+1,qst+m+1,cmp);
    for(register int i=1;i<=m;i++){
        for(register int j=next;j<=qst[i].r;j++){
            if(rec[a[j]]!=0)
                add(rec[a[j]],-1);
            add(j,1);
            rec[a[j]]=j;
        };
        next=qst[i].r+1,
        ans[qst[i].n]=sum(qst[i].r)-sum(qst[i].l-1);
    };
    for(register int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
};

线段树

$O(\log n)$

struct data{
	int l,r,w,f;
}tree[N<<2|1];
void build(const int l,const int r,const int k){//建树
    const int m=(l+r)>>1;
	tree[k].l=l,
	tree[k].r=r;
	if(tree[k].l==tree[k].r){
		scanf("%d",&tree[k].w);
		return void();
	};
	build(l,m,k<<1);
	build(m+1,r,k<<1|1);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
	return void();
};
inline void pushdown(const int k){//懒惰标记下传
	tree[k<<1].f+=tree[k].f,
	tree[k<<1|1].f+=tree[k].f,
	tree[k<<1].w+=tree[k].f*(tree[k<<1].r-tree[k<<1].l+1),
	tree[k<<1|1].w+=tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1),
	tree[k].f=0;
	return void();
};
void add_point(const int k){//单点修改
    const int m=(tree[k].l+tree.r)>>1;
	if(tree[k].l==tree[k].r){
		tree[k].w+=k;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(x<=m)
		add_point(k<<1);
	else
		add_point(k<<1|1);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
	return void();
};
void ask_point(const int k){//单点询问
    const int m=(tree[k].l+tree[k].r)>>1;
	if(tree[k].l==tree[k].r){
		ret=tree[k].w;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(x<=m)
		ask_point(k<<1);
	else
		ask_point(k<<1|1);
	return void();
};
void ask_range(const int k){//区间询问
    const int m=(tree[k].l+tree[k].r)>>1;
	if((tree[k].l>=x)&&(tree[k].r<=y)){
		ans+=tree[k].w;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(x<=m)
		ask_range(k<<1);
	if(y>m)
		ask_range(k<<1|1);
	return void();
};
void add_range(const int k){//区间修改
    int m=(tree[k].l+tree[k].r)>>1;
	if((tree[k].l>=x)&&(tree[k].r<=y)){
		tree[k].w+=(tree[k].r-tree[k].l+1)*tek,
		tree[k].f+=tek;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(x<=m)
		add_range(k<<1);
	if(y>m)
		add_range(k<<1|1);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
	return void();
};

线段树2

struct data{
	int w,add,mul;
}tree[400001];
void build(const int l,const int r,const int k){
    const int m=(l+r)>>1;
	tree[k].mul=1;
	if(l==r){
		tree[k].w=read()%p;
		return void();
	};
	build(l,m,k<<1);
	build(m+1,r,k<<1|1);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%p;
	return void();
};
inline void pushdown(const int k,const int l,const int r){
	const int m=(l+r)>>1;
	tree[k<<1].w=(tree[k<<1].w*tree[k].mul+tree[k].add*(m-l+1))%p,
	tree[k<<1|1].w=(tree[k<<1|1].w*tree[k].mul+tree[k].add*(r-m))%p,
	tree[k<<1].mul=(tree[k<<1].mul*tree[k].mul)%p,
	tree[k<<1|1].mul=(tree[k<<1|1].mul*tree[k].mul)%p,
	tree[k<<1].add=(tree[k<<1].add*tree[k].mul+tree[k].add)%p,
	tree[k<<1|1].add=(tree[k<<1|1].add*tree[k].mul+tree[k].add)%p,
	tree[k].mul=1,
	tree[k].add=0;
	return void();
};
void mul_range(const int k,const int l,const int r){//区间乘
    const int m=(l+r)>>1;
	if((L<=l)&&(R>=r)){
		tree[k].w=(tree[k].w*val)%p,
		tree[k].mul=(tree[k].mul*val)%p,
		tree[k].add=(tree[k].add*val)%p;
		return void();
	};
	pushdown(k,l,r);
	if(L<=m)
		mul_range(k<<1,l,m);
	if(R>m)
		mul_range(k<<1|1,m+1,r);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%p;
	return void();
};
void add_range(const int k,const int l,const int r){//区间加
    const int m=(l+r)>>1;
	if((L<=l)&&(R>=r)){
		tree[k].add=(tree[k].add+val)%p,
		tree[k].w=(tree[k].w+val*(r-l+1))%p;
		return void();
	};
	pushdown(k,l,r);
	if(L<=m)
		add_range(k<<1,l,m);
	if(R>m)
		add_range(k<<1|1,m+1,r);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%p;
	return void();
};
void ask_range(const int ,const int l,const int r){//区间求和
    const int m=(l+r)>>1;
	if((L<=l)&&(R>=r)){
		ans=(ans+tree[k].w)%p;
		return void();
	};
	pushdown(k,l,r);
	if(L<=m)
		ask_range(k<<1,l,m);
	if(R>m)
        ask_range(k<<1|1,m+1,r);
	return void();
};

线段树优化建边

struct data{
	int l,r;
}tree[];
void build(int &k,const int l,const int r,const int md){
	const int mid=(l+r)>>1;
	if(l==r){
		k=l;
		return void();
	};
	k=++cnt;
	build(tree[k].l,l,mid,md);
	build(tree[k].r,mid+1,r,md);
	if(md==1){
		add(k,tree[k].l,0);
		add(k,tree[k].r,0);
		return void();
	};
	add(tree[k].l,k,0);
	add(tree[k].r,k,0);
	return void();
};
void modify(const int k,const int a,const int L,const int R,const int val,const int md,const int l,const int r){
	const int mid=(l+r)>>1;
	if((l>=L)&&(r<=R)){
		if(md==1)
			add(a,k,val);
		else
			add(k,a,val);
		return void();
	};
	if(L<=mid)
		modify(tree[k].l,a,L,R,val,md,l,mid);
	if(R>mid)
		modify(tree[k].r,a,L,R,val,md,mid+1,r);
	return void();
};
cnt=n;
build(root1,1,n,1);
build(root2,1,n,2);
add(u,v,w);//u->v:w
modify(root1,u,l,r,w,1,1,n);//u->[l,r]:w
modify(root2,v,l,r,w,2,1,n);//[l,r]->v:w

扫描线

struct data1{
	int l,r,sum,len;
}tree[N<<2];
struct data2{
	int l,r,h,mark;
}scanline[N<<1];
inline bool cmp1(const data2 a,const data2 b){
	return a.h<b.h;
};
inline bool cmp2(const int a,const int b){
	return a<b;
};
void build(const int k,const int l,const int r){
    const int m=(l+r)>>1;
	tree[k].l=l,
	tree[k].r=r;
	if(tree[k].l==tree[k].r)
		return void();
	build(k<<1,l,m);
	build(k<<1|1,m+1,r);
	return void();
};
void modify(const int k,const int l,const int r,const int val){
	if((a[tree[k].r+1]<=l)||(r<=a[tree[k].l]))
		return void();
	if((l<=a[tree[k].l])&&(a[tree[k].r+1]<=r)){
		tree[k].sum+=val;
		if(tree[k].sum>0)
			tree[k].len=a[tree[k].r+1]-a[tree[k].l];
		else
			tree[k].len=tree[k<<1].len+tree[k<<1|1].len;
		return void();
	};
	modify(k<<1,l,r,val);
	modify(k<<1|1,l,r,val);
	if(tree[k].sum>0)
		tree[k].len=a[tree[k].r+1]-a[tree[k].l];
	else
		tree[k].len=tree[k<<1].len+tree[k<<1|1].len;
	return void();
};
int main(void){
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
		t1=read(),
		t2=read(),
		t3=read(),
		t4=read(),
		scanline[i<<1].l=scanline[(i<<1)-1].l=t1,
		scanline[i<<1].r=scanline[(i<<1)-1].r=t3,
		scanline[(i<<1)-1].h=t2,
		scanline[i<<1].h=t4,
		scanline[(i<<1)-1].mark=1,
		scanline[i<<1].mark=-1,
		a[(i<<1)-1]=t1,
		a[i<<1]=t3;
	sort(scanline+1,scanline+(n<<1)+1,cmp1);
	sort(a+1,a+(n<<1)+1,cmp2);
	build(1,1,unique(a+1,a+(n<<1)+1)-a-2);
	for(register int i=1;i<(n<<1);i++){
		modify(1,scanline[i].l,scanline[i].r,scanline[i].mark);
		ans+=tree[1].len*(scanline[i+1].h-scanline[i].h);
	};
	return 0;
};

左偏树

(TLEx1)

inline int merge(int x,int y){
	if((x==0)||(y==0))
		return x|y;
	if((val[x]>val[y])||((val[x]==val[y])&&(x>y)))
		swap(x,y);
	ch[x][1]=merge(ch[x][1],y),
	fa[ch[x][1]]=x;
	if(dis[ch[x][0]]<dis[ch[x][1]])
        ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];
	dis[x]=dis[ch[x][1]]+1;
	return x;
};
int getf(const int x){
	return fa[x]==0?x:getf(fa[x]);
};
inline void pop(const int x){
	val[x]=-1,
	fa[ch[x][0]]=fa[ch[x][1]]=0;
	merge(ch[x][0],ch[x][1]);
	return void();
};
int main(void){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;val[i++]=read());
	for(register int i=1;i<=m;i++){
		opr=read(),
		x=read();
		if(opr==1){
			y=read();
			if((val[x]==-1)||(val[y]==-1))
				continue;
			fx=getf(x),
			fy=getf(y);
			if(fx==fy)
				continue;
			merge(fx,fy);
		}
		else
			if(val[x]==-1)
				printf("-1\n");
			else{
				printf("%d\n",val[getf(x)]);
				pop(getf(x));
			};
	};
	return 0;
};

ST表

令$f_{i,j}=\max{[i,i+2^j-1]}$。

显然$f(i,0)=a_i$。

根据定义式，第二维就相当于倍增的时候“跳了$2^j-1$步”，依据倍增的思路，写出状态转移方程：$f_{i,j}=\max{f_{i,j-1},f_{i+2^{j-1},j-1}}$。

对于每个询问$[l,r]$，我们把它分成两部分：$f_{l,l+2^s-1}$与$f_{r-2^s+1,r}$，其中$s=\lfloor\log_2(r-l+1)\rfloor$。两部分的结果的最大值就是回答。

预处理：$\Theta(n\log n)$
查询：$\Theta(1)$

int f[N][log(N)];
inline int query(int l,int r){
	const int k=log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
};
for (register int i=1;i<=n;i++)
	f[i][0]=a[i];
int t=log(n)/log(2);
for(register int i=1;i<=t;i++)
	for(register int j=1;j<=n-(1<<i)+1;j++)
		f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);

珂朵莉树

$O(n\log\log n)$

struct data{
	int l,r;
	mutable long long int val;
	inline bool operator<(const data &a)const{
		return l<a.l;
	};
	data(int L,int R=-1,long long int Val=0):l(L),r(R),val(Val){};
};
set<data>s;
inline set<data>::iterator split(const int pos){
	set<data>::iterator it=s.lower_bound(data(pos));
	if((it!=s.end())&&(it->l==pos))
		return it;
	it--;
	const int tl=it->l,tr=it->r;
	const long long int tv=it->val;
	s.erase(it);
	s.insert(data(tl,pos-1,tv));
	return s.insert(data(pos,tr,tv)).first;
};
inline void assign(const int l,const int r,const long long int val){//区间推平
	set<data>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(data(l,r,val));
	return void();
};
void add(const int l,const int r,const long long int val){//区间加
	set<data>::iterator itr=split(r+1),itl=split(l);
	for(register set<data>::iterator it=itl;it!=itr;it++)
		it->val+=val;
	return void();
};
long long int kthele(const int l,const int r,int k){//第k值
	set<data>::iterator itr=split(r+1),itl=split(l);
	vector<pair<long long int,int> >vc;
	vc.clear();
	for(register set<data>::iterator it=itl;it!=itr;it++)
		vc.push_back(make_pair(it->val,it->r-it->l+1));
	sort(vc.begin(),vc.end());
	for(register vector<pair<long long int,int> >::iterator it=vc.begin();it!=vc.end();it++){
		k-=it->second;
		if(k<=0)
			return it->first;
	};
	return -1;
};
long long int query(const int l,const int r,const int x,const int y){
	set<data>::iterator itr=split(r+1),itl=split(l);
	long long int res=0;
	for(register set<data>::iterator it=itl;it!=itr;it++)
		res=(res+(long long int)(it->r-it->l+1)*qpow(it->val,x,y))%y;
	return res;
};
void modify(const int l,const int r){
	set<data>::iterator itr=split(r+1),itl=split(l);
	for(register set<data>::iterator it=itl;it!=itr;it++)
		it->val^=1;
	return void();
};
int sum(const int l,const int r){
	set<data>::iterator itr=split(r+1),itl=split(l);
	int rec=0;
	for(register set<data>::iterator it=itl;it!=itr;it++)
		if(it->val==true)
			rec+=it->r-it->l+1;
	return rec;
};
int cnt(const int l,const int r){
	set<data>::iterator itr=split(r+1),itl=split(l);
	int tmp=0,res=0;
	for(register set<data>::iterator it=itl;it!=itr;it++)
		if(it->val==true)
			tmp+=it->r-it->l+1;
		else
			res=max(res,tmp),
			tmp=0;
	return max(res,tmp);
};
int main(void){
	for(register int i=1;i<=n;i++)
		s.insert(data(i,i,a[i]));
	return 0;
};

vector平衡树

tree.insert(lower_bound(tree.begin(),tree.end(),t),t);//插入t
tree.erase(lower_bound(tree.begin(),tree.end(),t));//删除t
printf("%d\n",lower_bound(tree.begin(),tree.end(),t)-tree.begin()+1);//查询t的排名
printf("%d\n",tree.at(t-1));//查询排名为t的数
printf("%d\n",tree.at(lower_bound(tree.begin(),tree.end(),t)-tree.begin()-1));//求t的前驱
printf("%d\n",tree.at(upper_bound(tree.begin(),tree.end(),t)-tree.begin()));//求t的后继 

可持久数组

struct data{
	int l,r,w;
}tree[40*1000001];
int n,m,a,b,c,d,root[1000001],top,t[1000001];
inline int add(const int k){
	tree[++top]=tree[k];
	return top;
};
int build_tree(int k,const int begin,const int end){
    const int m=(begin+end)>>1;
	k=++top;
	if(begin==end){
		tree[k].w=t[begin];
		return top;
	};
	tree[k].l=build_tree(tree[k].l,begin,m);
	tree[k].r=build_tree(tree[k].r,m+1,end);
	return k;
};
int update(int k,const int begin,const int end,const int x,const int val){
    const int m=(begin+end)>>1;
	k=add(k);
	if(begin==end){
		tree[k].w=val;
        return k;
    };
	if(x<=m)
		tree[k].l=update(tree[k].l,begin,m,x,val);
	else
		tree[k].r=update(tree[k].r,m+1,end,x,val);
};
int query(const int k,const int begin,const int end,const int x){
    const int m=(begin+end)>>1;
	if(begin==end)
		return tree[k].w;
	if(x<=m)
		return query(tree[k].l,begin,m,x);
	else
		return query(tree[k].r,m+1,end,x);
};
int main(void){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
		t[i]=read();
	root[0]=build_tree(0,1,n);
	for(register int i=1;i<=m;i++){
		a=read(),
        b=read(),
        c=read();
		if(b==1){
			scanf("%d",&d);
			root[i]=update(root[a],1,n,c,d);//版本a基础上将t_c修改为d
		}
		else{
			printf("%d\n",query(root[a],1,n,c));
			root[i]=root[a];//访问版本a中t_c的值，生成一样版本的对象应为a
		};
	};
	return 0;
};

二叉堆

int n,opr,heap[1000001],heap_size,a;
void put(const int k){
	int now=heap_size,next;
	heap[++heap_size]=k;
	while(now>1){
		next=now>>1;
		if(heap[next]<=heap[now])
			break;
		heap[next]^=heap[now]^=heap[next]^=heap[now],
		now=next;
	};
	return void();
};
inline int get(void){
	return heap[1];
};
void delet(void){
	int now=1,next;
	heap[1]=heap[heap_size--];
	while(now<<1<=heap_size){
		next=now<<1;
		if(heap[next]>heap[next+1])
			next|=1;
		if(heap[next]>=heap[now])
			break;
		heap[next]^=heap[now]^=heap[next]^=heap[now],
		now=next;
	};
	return void();
};

对顶堆

#include <queue>
#include <vector>
priority_queue<int,vector<int>,less<int> >q1;
priority_queue<int,vector<int>,greater<int> >q2;
inline int myabs(const int x){
    return x<0?-x:x;
};
inline void insrt(const int k){
    if((q2.size()==0)||(k>q2.top()))
        q2.push(k);
    else
        q1.push(k);
    return void();
};
void refrsh(void){
    while(myabs(q1.size()-q2.size())>1)
        if(q1.size()>q2.size()){
            q2.push(q1.top());
            q1.pop();
        }
        else{
            q1.push(q2.top());
            q2.pop();
        };
    return void();
};
inline int getmid(void){
    refrsh();
    if(q2.size()>q1.size())
        return q2.top();
    return q1.top();
};
void init(void){
    while(q1.empty()==false)
        q1.pop();
    while(q2.empty()==false)
        q2.pop();
    return void();
};

Huffman树

$$
\min\left\lbrace\sum w_il_i\right\rbrace
$$

struct data{
	int w,h;
	friend bool operator<(const data a,const data b){
		return (a.w>b.w)||((a.w==b.w)&&(a.h>b.h));
	};
}rec;
priority_queue<data>q;
inline data lnk(const int a,const int b){
	data tmp;
	tmp.w=a,
	tmp.h=b;
	return tmp;
};
for(register int i=1;i<=n;i++)
	q.push(lnk(read(),1));
while((q.size()-1)%(k-1)!=0)
	q.push(lnk(0,1));
while(q.size()>=k){
	maxh=-1,
	sumw=0;
	for(register int i=1;i<=k;i++){
		rec=q.top();
		q.pop();
		maxh=max(maxh,rec.h),
		sumw+=rec.w;
	};
	ans+=sumw;
	q.push(lnk(sumw,maxh+1));
};
printf("%d\n%d\n",ans,q.top().h-1);

树链剖分

$O(\log n)$

void dfs1(const int k){
	size[k]=1;
	for(register int i=head[k];i!=0;i=next[i])
		if(deep[ver[i]]==0){
			deep[ver[i]]=deep[k]+1,
			fa[ver[i]]=k;
			//a[ver[i]]=edge[i];（边权转点权）
			dfs1(ver[i]);
			size[k]+=size[ver[i]];
			if(size[ver[i]]>size[son[k]])
				son[k]=ver[i];
		};
	return void();
};
void dfs2(const int k,const int tp){
	id[k]=++nmb,
	top[k]=tp,
	wt[nmb]=a[k];
	if(son[k]==0)
		return void();
	dfs2(son[k],tp);
	for(register int i=head[k];i!=0;i=next[i])
		if((ver[i]!=fa[k])&&(ver[i]!=son[k]))
			dfs2(ver[i],ver[i]);
	return void();
};
void build(const int k,const int l,const int r){
	const int m=(l+r)>>1;
	tree[k].l=l,
	tree[k].r=r;
	if(l==r){
		tree[k].w=wt[l]%p;
		return void();
	};
	build(k<<1,l,m);
	build(k<<1|1,m+1,r);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%p;
	return void();
};
inline void pushdown(const int k){
	tree[k<<1].f+=tree[k].f,
	tree[k<<1|1].f+=tree[k].f,
	tree[k<<1].w=(tree[k<<1].w+tree[k].f*(tree[k<<1].r-tree[k<<1].l+1))%p,
	tree[k<<1|1].w=(tree[k<<1|1].w+tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1))%p,
	tree[k].f=0;
	return void();
};
void ask_range(const int k,const int l,const int r){
	const int m=(tree[k].l+tree[k].r)>>1;
	if((tree[k].l>=l)&&(tree[k].r<=r)){
		ask_range_res=(ask_range_res+tree[k].w)%p;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(l<=m)
		ask_range(k<<1,l,r);
	if(r>m)
		ask_range(k<<1|1,l,r);
	return void();
};
void add_range(const int k,const int l,const int r,const int v){
	const int m=(tree[k].l+tree[k].r)>>1;
	if((tree[k].l>=l)&&(tree[k].r<=r)){
		tree[k].f+=v,
		tree[k].w=(tree[k].w+v*(tree[k].r-tree[k].l+1))%p;
		return void();
	};
	if(tree[k].f!=0)
		pushdown(k);
	if(l<=m)
		add_range(k<<1,l,r,v);
	if(r>m)
		add_range(k<<1|1,l,r,v);
	tree[k].w=(tree[k<<1].w+tree[k<<1|1].w)%p;
	return void();
};
void update_path(int l,int r,int v){//将树从x到y结点最短路径上所有节点的值都加上z
	v%=p;
	while(top[l]!=top[r]){
		if(deep[top[l]]<deep[top[r]])
			l^=r^=l^=r;
		add_range(1,id[top[l]],id[l],v);
		l=fa[top[l]];
	};
	if(deep[l]>deep[r])
		l^=r^=l^=r;
	add_range(1,id[l]/*+1*/,id[r],v);
	return void();
};
int query_path(int l,int r){//求树从x到y结点最短路径上所有节点的值之和
	int ans=0;
	while(top[l]!=top[r]){
		if(deep[top[l]]<deep[top[r]])
			l^=r^=l^=r;
		ask_range_res=0;
		ask_range(1,id[top[l]],id[l]);
		ans=(ans+ask_range_res)%p,
		l=fa[top[l]];
	};
	if(deep[l]>deep[r])
		l^=r^=l^=r;
	ask_range_res=0;
	ask_range(1,id[l]/*+1*/,id[r]);
	ans=(ans+ask_range_res)%p;
	return ans;
};
inline void update_subtree(const int k,const int v){//将以x为根节点的子树内所有节点值都加上z
	add_range(1,id[k],id[k]+size[k]-1,v);
	return void();
};
inline int query_subtree(const int k){//求以x为根节点的子树内所有节点值之和
	ask_range_res=0;
	ask_range(1,id[k],id[k]+size[k]-1);
	return ask_range_res;
};
deep[r]=fa[r]=1;
dfs1(r);
dfs2(r,r);
build(1,1,n);

LCA

void dfs1(const int k){
    size[k]=1;
    for(register int i=head[k];i!=0;i=next[i])
        if(deep[ver[i]]==0){
            fa[ver[i]]=k,
            deep[ver[i]]=deep[k]+1;
            dfs1(ver[i]);
            size[k]+=size[ver[i]];
            if(size[son[k]]<size[ver[i]])
                son[k]=ver[i];
        };
    return void();
};
void dfs2(const int k,const int last){
    top[k]=last;
    if(son[k]==0)
        return void();
    dfs2(son[k],last);
    for(register int i=head[k];i!=0;i=next[i])
        if((ver[i]!=son[k])&&(ver[i]!=fa[k]))
            dfs2(ver[i],ver[i]);
    return void();
};
int lca(int l,int r){
    while(top[l]!=top[r]){
        if(deep[top[l]]<deep[top[r]])
            l^=r^=l^=r;
        l=fa[top[l]];
    };
    if(deep[l]>deep[r])
        l^=r^=l^=r;
    return l;
};
deep[r]=fa[r]=1;
dfs1(r);
dfs2(r,r);

单调栈

最大子矩阵

a[n+1]=0;
for(register int i=1;i<=n;a[i++]=read());
for(register int i=1;i<=n+1;i++)
	if(a[i]<s[top]){
		width=0;
		while(a[i]<s[top])
			width+=w[top],
			ans=max(ans,s[top]*width),
			top--;
		s[++top]=a[i],
		w[top]=width+1;
	}
	else
		s[++top]=a[i],
		w[top]=1;
printf("%lld\n",ans);

单调队列

滑动窗口-区间最小

struct data{
	int val,pos;
}a[2000001];
deque<data>q;
for(register int i=1;i<=n;i++)
	a[i].val=read(),
	a[i].pos=i;
for(register int i=1;i<=n;i++){
	while((q.empty()==false)&&(q.back().val>=a[i].val))
		q.pop_back();
	q.push_back(a[i]);
	while((q.empty()==false)&&(q.front().pos<=i-m))
		q.pop_front();
	ans[i]=q.front().val;
};
for_each(ans,ans+n,f);

最大子序和

for(register int i=1;i<=n;i++)
	sum[i]=sum[i-1]+a[i];
for(register int i=1;i<=n;i++){
	if(i>=s){
		while((que.empty()==false)&&(sum[i-s]<sum[que.back()]))
			que.pop_back();
		que.push_back(i-s);
	};
	if((que.empty()==false)&&(que.front()<i-t))
		que.pop_front();
};

笛卡尔树

$O(n)$

for(register int i=1;i<=n;i++){
	tmp=top;
	while((tmp>0)&&(a[stk[tmp]]>a[i]))
		tmp--;
	if(tmp>0)
		rson[stk[tmp]]=i;
	if(tmp<top)
		lson[i]=stk[tmp+1];
	stk[++tmp]=i,
	top=tmp;
};

替罪羊树

const double alpha=0.75;
struct data{
	int l,r,val,size,sh,wn;//左右子树节点、该节点值、子树不同节点数、子树剩余节点数、该节点值相同个数
}tree[];
void unfold(const int& k){
	if(k==0)
		return void();
	unfold(tree[k].l);
	if(tree[k].wn>0)
		rt[++crt]=k;
	unfold(tree[k].r);
	return void();
};
inline void updat(const int k){
	tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+tree[k].wn,
	tree[k].sh=tree[tree[k].l].sh+tree[tree[k].r].sh+tree[k].wn;
	return void();
};
int rebuild(const int l,const int r){
	const int mid=(l+r)>>1;
	if(l==r)
		return 0;
	tree[rt[mid]].l=rebuild(l,mid),
	tree[rt[mid]].r=rebuild(mid+1,r);
	updat(rt[mid]);
	return rt[mid];
};
inline bool jdg(const int k){
	if(tree[k].wn==0)
		return false;
	if((double)tree[k].size*alpha<(double)max(tree[tree[k].l].size,tree[tree[k].r].size))
		return true;
	if((double)tree[k].size*alpha>(double)tree[k].sh)
		return true;
	return false;
};
inline void balnc(int& k){
	crt=0;
	unfold(k);
	k=rebuild(1,crt+1);
	return void();
};
inline void addnw(const int k,const int val){
	tree[k].val=val,
	tree[k].sh=tree[k].size=tree[k].wn=1;
	return void();
};
void insrt(int& k,const int val){
	if(k==0){
		k=++cnt;
		if(root==0)
			root=1;
		addnw(k,val);
		return void();
	};
	if(tree[k].val==val)
		tree[k].wn++;
	else
		if(val<tree[k].val)
			insrt(tree[k].l,val);
		else
			insrt(tree[k].r,val);
	updat(k);
	if(jdg(k)==true)
		balnc(k);
	return void();
};//插入节点val
void delt(int& k,const int val){
	tree[k].sh--;
	if(tree[k].val==val)
		tree[k].wn--;
	else
		if(val<tree[k].val)
			delt(tree[k].l,val);
		else
			delt(tree[k].r,val);
	updat(k);
	if(jdg(k)==true)
		balnc(k);
	return void();
};//删除节点val
int rkat(const int k,const int val){
	if(tree[k].l==tree[k].r)
		return tree[k].val;
	if(val<=tree[tree[k].l].sh)
		return rkat(tree[k].l,val);
	if(val<=tree[tree[k].l].sh+tree[k].wn)
		return tree[k].val;
	return rkat(tree[k].r,val-tree[tree[k].l].sh-tree[k].wn);
};//查询第val大
int rkdown(const int k,const int val){
	if(k==0)
		return 0;
	if((tree[k].wn>0)&&(tree[k].val==val))
		return tree[tree[k].l].sh;
	if(val<tree[k].val)
		return rkdown(tree[k].l,val);
	return tree[tree[k].l].sh+tree[k].wn+rkdown(tree[k].r,val);
};
int rkup(const int k,const int val){
	if(k==0)
		return 1;
	if((tree[k].wn>0)&&(tree[k].val==val))
		return tree[tree[k].l].sh+tree[k].wn+1;
	if(val<tree[k].val)
		return rkup(tree[k].l,val);
	return tree[tree[k].l].sh+tree[k].wn+rkup(tree[k].r,val);
};
inline int getrk(const int val){
	return rkdown(root,val)+1;
};//查询val的排名
inline int prev(const int val){
	return rkat(root,rkdown(root,val));
};//询问val的前驱
inline int nxt(const int val){
	return rkat(root,rkup(root,val));
};//询问val的后继

可重

long long int rkdown(const long long int k,const long long int val){
	if(k==0)
		return 0;
	if(tree[k].val==val)
		if(tree[k].wn==1)
			return tree[tree[k].l].sh;
		else
			if(tree[k].wn>1)
				return tree[tree[k].l].sh+1;
	if(val<tree[k].val)
		return rkdown(tree[k].l,val);
	return rkdown(tree[k].r,val)+tree[tree[k].l].sh+tree[k].wn;
};
long long int rkup(const long long int k,const long long int val){
	if(k==0)
		return 1;
	if(tree[k].val==val)
		if(tree[k].wn==1)
			return tree[tree[k].l].sh+2;
		else
			if(tree[k].wn>1)
				return tree[tree[k].l].sh+1;
	if(val<tree[k].val)
		return rkup(tree[k].l,val);
	return rkup(tree[k].r,val)+tree[k].wn+tree[tree[k].l].sh;
};
insrt(root,INF);
insrt(root,-INF);

pb_ds tree 平衡树

由于会出现重复元素，需要记录序数加以区分。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>t;

t.insert(make_pair(x,i));//插入x
t.erase(t.lower_bound(make_pair(x,0)));//删除x
printf("%d\n",t.order_of_key(make_pair(x,0))+1);//查询x的排名
printf("%d\n",*t.find_by_order(x-1));//查询排名为x的数
printf("%d\n",(*--t.lower_bound(make_pair(x,0))).first);//求x的前驱
printf("%d\n",(*t.upper_bound(make_pair(x,0x3f3f3f3f3f3f3f3f))).first);//求x的后继 

Trie

int tot=1,trie[N+1][26];
bool end[N+1];
void insert(const char* str){
	int len=strlen(str),p=1,ch=0;
	for(register int i=0;i<str;i++){
		ch=str[i]-'a';
		if(trie[p][ch]==0)
			trie[p][ch]=++tot;
		p=trie[p][ch];
	};
	end[p]=true;
	return void();
};
bool search(const char* str){
	int len=strlen(str),p=1,ch=0;
	for(register int i=0;i<len;i++){
		ch=str[i]-'a',
		p=trie[p][ch];
		if(p==0)
			return false;
	};
	return end[p];
};

Ԗ-Hash

string s;
int len;
unsigned long long hash[N+1];
getline(cin,s);
len=s.length();
for(register int i=1;i<=len;i++)
	hash[i]=(hash[i-1]*131+s[i])%1000000000007;
printf("%lld",hash[len]);

KMP模式匹配

$O(n+m)$

n=strlen(a),//模式串
m=strlen(b);//文本串
for(register int i=n;i>=1;i--)
	a[i]=a[i-1];
for(register int i=m;i>=1;i--)
	b[i]=b[i-1];
a[0]=b[0]=0;
for(register int i=2,j=0;i<=n;i++){
	while((j>0)&&(a[i]!=a[j+1]))
		j=next[j];
	if(a[i]==a[j+1])
		j++;
	next[i]=j;
};
for(register int i=1,j=0;i<=m;i++){
	while((j>0)&&((j==n)||(b[i]!=a[j+1])))
		j=next[j];
	if(b[i]==a[j+1])
		j++;
	f[i]=j;
	if(f[i]==n)
		printf("%d\n",i-n+1);
};

最小表示法

当字符串$S$中可以选定一个位置$i$满足$S_{i\cdots n}+S_{1\cdots i-1}=T$则称$S$与$T$循环同构 。
字符串$S$的最小表示 为与$S$循环同构的所有字符串中字典序最小的字符串。

int a[2N];
scanf("%d",&n);
for(register int t=1;t<=n;t++)
	a[t]=a[n+t]=read();
while((i<=n)&&(j<=n)){
	k=0;
	while((k<n)&&(a[i+k]==a[j+k]))
		k++;
	if(k==n)
		break;
	if(a[i+k]>a[j+k]){
		i+=k+1;
		if(i==j)
			i++;
	}
	else{
		j+=k+1;
		if(i==j)
			j++;
	};
};
for_each(a+min(i,j),a+n+1,f);
for_each(a+1,a+min(i,j),f);
putchar('\n');

线性DP

LIS

最长上升子序列。给定一个长度为$N$的数列$A$，求数值单调递增的子序列的长度最长是多少。$A$的任意子序列$B$可表示为$B={A_{k_1},A_{k_2},\cdots,A_{k_p}}$，其中$k_1<k_2<\cdots <k_p$。

$F_i$表示以$A_i$为结尾的“最长上升子序列”的长度。
$$
\displaylines{
F_i=\max_{0\leq j<i,A_j<A_i}NaN\\
F_0=0\\
\max_{1\leq i\leq N}
}
$$

LCS

最长公共子序列。给定两个长度分别为$N$和$M$的字符串$A$和$B$，求既是$A$的子序列又是$B$的子序列的字符串长度最长是多少。

$F_{i,j}$表示前缀子串$A_{1\sim i}$与$B_{1\sim j}$的“最长公共子序列”的长度。
$$
\displaylines{
F_{i,j}=\max
\begin{cases}
F_{i-1,j}\\
F_{i,j-1}\\
F_{i-1,j-1}+1 & :A_i=B_j
\end{cases}\\
F_{i,0}=F_{0,j}=0\\
F_{N,M}
}
$$

数字三角形

给定一个共有$N$行的三角矩阵$A$，其中第$i$行有$i$列。从左上角出发，每次可以向下方或右下方走一步，最终到达底部。求把经过的所有位置上的数加起来，和最大是多少。

$F_{i,j}$表示从左上角走到第$i$行第$j$列，和最大是多少
$$
\displaylines{
F_{i,j}=A_{i,j}+\max
\begin{cases}
F_{i-1,j}\\
F_{i-1,j-1} & :j>1
\end{cases}\\
F_{1,1}=A_{1,1}\\
\max_{1\leq j\leq N}{F_{N,j}}
}
$$

背包

0/1背包

给定$N$个物品，其中第$i$个物品的体积为$V_i$，价值为$W_i$。有一容积为$M$的背包，要求选择一些物品放入背包，使得物品总体积不超过$M$的前提下，物品的价值总和最大。

$F_{i,j}$表示从前$i$个物品 中选出了总体积为$j$的物品放入背包，物品的最大价值和。
$$
\displaylines{
\begin{aligned}
F_{i,j}=&\max
\begin{cases}
F_{i-1,j}\\
F_{i-1,j-V_i}+W_i & :j\geq V_i
\end{cases}\\
F_{i,j}=&-\infty,F_{0,0}=0\\
&\max_{0\leq j\leq M}{F_{N,j}}
\end{aligned}
}
$$

memset(f,0xc0,sizeof(f));
f[0][0]=0;
for(register int i=1;i<=n;i++){
    for(register int j=0;j<=m;j++)
        f[i][j]-f[i-1][j];
    for(register int j=v[i];j<=m;j++)
        f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
};

滚动数组

memset(f,0xc0,sizeof(f));
f[0][0]=0;
for(register int i=1;i<=n;i++){
    for(register int j=0;j<=m;j++)
        f[i&1][j]=f[(i-1)&1][j];
    for(register int j=v[i];j<=m;j++)
        f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-v[i]]+w[i]);
};
for(register int j=0;j<=m;j++)
    ans=max(ans,f[n&1][j]);

一维

memset(f,0xc0,sizeof(f));
f[0]=0;
for(register int i=1;i<=n;i++)
    for(register int j=m;j>=v[i];j--)
        f[j]=max(f[j],f[j-v[i]]+w[i]);
for(register int j=0;j<=m;j++)
    ans=max(ans,f[j]);

完全背包

给定$N$种物品，其中第$i$种物品的体积为$V_i$，价值为$W_i$，并且有无数个。有一容积为$M$的背包，要求选择若干个物品放入背包，使得物品总体积不超过$M$的前提下，物品的价值总和最大。

$F_{i,j}$表示从前$i$种物品中选出了总体积为$j$的物品放入背包，物品的最大价值和。
$$
\displaylines{
\begin{aligned}
F_{i,j}=&\max
\begin{cases}
F_{i-1,j}\\
F_{i,j-V_i}+W_i&:j\geq V_i
\end{cases}\\
F_{i,j}=&-\infty,F_{0,0}=0\\
&\max_{0\leq j\leq M}{F_{N,j}}
\end{aligned}
}
$$

memset(f,0xc0,sizeof(f));
f[0]=0;
for(register int i=1;i<=n;i++)
    for(register int j=v[i];j<=m;j++)
        f[j]=max(f[j],f[j-v[i]]+w[i]);
for(register int j=0;j<=m;j++)
    ans=max(ans,f[j]);

多重背包

给定$N$种物品，其中第$i$种物品的体积为$V_i$，价值为$W_i$，并且有$C_i$个。有一容积为$M$的背包，要求选择若干个物品放入背包，使得物品总体积不超过$M$的前提下，物品的价值总和最大。

直接拆分法

memset(f,0xc0,sizeof(f));
f[0]=0;
for(register int i=1;i<=n;i++)
    for(register int j=1;j<=c[i];j++)
        for(register int k=m;k>=v[i];k--)
            f[k]=max(f[k],f[k-v[i]]+w[i]);
for(register int i=0;i<=m;i++)
    ans=max(ans,f[i]);

二进制拆分法

求出满足$\displaystyle\sum_{i=1}^p2^i\leq C_i$的最大$p\in\mathbb Z$，设$\displaystyle R_i=C_i-\sum_{i=0}^p2^i$。

把数量为$C_i$的第$i$种物品拆成$p+2$个物品，体积分别为：$2^0V_i, \ 2^1V_i,\cdots, \ 2^pV_i,R_iV_i$。

这$p+2$个物品可以凑成$\forall k, \ k\in[0,C_iV_i], \ k\mid V_i$，并且不能凑成$\forall k, \ k>C_iV_i$。这等价于原问题中体积为$V_i$的物品可以使用$[0,C_i]$次。

分组背包

给定$N$组物品，其中第$i$组有$C_i$个物品。第$i$组的第$j$个物品的体积为$V_{i,j}$，价值为$W_{i,j}$。有一容积为$M$的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过$M$的前提下，物品的价值总和最大。

$F_{i,j}$表示从前$i$组中选出总体积为$j$的物品放入背包，物品的最大价值和。
$$
F_{i,j}=\max
\begin{cases}
\displaylines{
F_{i-1,j}\\
\displaystyle\max_{1\leq k\leq C_i}{F_{i-1,j-V_{i,k}}+W_{i,k}}
}
\end{cases}\
$$

memset(f,0xc0,sizeof(f));
f[0]=0;
for(register int i=1;i<=n;i++)
    for(register int j=m;j>=0;j--)
        for(register int k=1;k<=c[i];k++)
            if(j>=v[i][k])
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

二维费用背包

背包中的每种物品有两种费用。

$F_{i,v,u}$表示前$i$件物品付出两种代价分别为$v$和$u$时可获得的最大价值。
$$
\begin{aligned}
\displaylines{
F_{i,v,u}=&\max
\begin{cases}
F_{i-1,v,u}\\
F_{i-1,v-A_i,u-B_i}+W_i
\end{cases}\\
F_{i,v,u}=&-\infty \ F_{i,v,0}=0\\
&F_{V,U}
}
\end{aligned}
$$

二维偏序

$$
(a_j,b_j)\prec(a_i,b_i)\xlongequal{def}a_j\lesseqgtr a_i, \ b_j\lesseqgtr b_i
$$

GarsiaWachs

设序列$A_{0\cdots n-1}$，每次寻找最小满足$A_{k-1}\leq A_{k+1}$的$k$，把$A_k$与$A_{k-1}$合并，从$k$向前寻找第一个满足$A_j>A_k+A_{k-1}$的$j$，把合并后的值$A_k+A_{k-1}$插入$A_j$的后面。

int merge(void){
	int k=a.size()-2,tmp=0,pos=-1;
	for(register int i=0;i<a.size()-2;i++)
		if(a[i]<=a[i+2]){
			k=i;
			break;
		};
	tmp=a[k]+a[k+1];
	a.erase(a.begin()+k);
	a.erase(a.begin()+k);
	for(register int i=k-1;i>=0;i--)
		if(a[i]>tmp){
			pos=i;
			break;
		};
	a.insert(a.begin()+pos+1,tmp);
	return tmp;
};
for(register int i=1;i<=n;i++)
	a.push_back(read());
for(register int i=1;i<=n-1;i++)
	ans+=merge();

悬线法

最大子矩阵

for(register int i=1;i<=n;i++)
    for(register int j=1;j<=m;j++){
		cin>>tmp;
        switch(tmp.at(0)){
            case 'R':
                mp[i][j]=false;
                break;
            case 'F':
                mp[i][j]=true,
				top[i][j]=1,//向上到达最远的点的距离
        		l[i][j]=r[i][j]=j;//(i,j)左，右能到达的最远的点的纵坐标
                break;
            default:
                break;
        };
    };
for(register int i=1;i<=n;i++)
    for(register int j=2;j<=m;j++)
        if((mp[i][j]==true)&&(mp[i][j-1]==true))
            l[i][j]=l[i][j-1];
for(register int i=1;i<=n;i++)
    for(register int j=m-1;j>0;j--)
        if((mp[i][j]==true)&&(mp[i][j+1]==true))
            r[i][j]=r[i][j+1];
for(register int i=1;i<=n;i++)
    for(register int j=1;j<=m;j++){
        if((i>1)&&(mp[i][j]==true)&&(mp[i-1][j]==true))
            l[i][j]=max(l[i][j],l[i-1][j]),
            r[i][j]=min(r[i][j],r[i-1][j]),
            top[i][j]=top[i-1][j]+1;
		ans=max(ans,(r[i][j]-l[i][j]+1)*top[i][j]);
	};

状态压缩DP

TSP

从$1$出发，求经过所有点返回$1$所走的最短路程。

$f_{i,j}$表示点被经过的状态对应的二进制数为$i$，且目前处于点$j$时的最短路径。
$$
f_{i,j}=\min{f_{i\oplus 2^j,k}+w_{i,j}}
$$

memset(f,0x3f,sizeof(f));
f[1][0]=0;
for(register int i=0;i<n;i++)
	for(register int j=0;j<n;j++)
		mp[i][j]=read();
for(register int i=1;i<=((1<<n)-1);i+=2)
	for(register int j=0;j<n;j++)
		if(((i>>j)&1)==1)
			for(register int k=0;k<n;k++)
				if((((i>>k)&1)==1)&&(k!=j))
					f[i][j]=min(f[i][j],f[i^(1<<j)][k]+mp[k][j]);
for(register int i=0;i<n;i++)
	ans=min(ans,f[(1<<n)-1][i]+mp[i][0]);

摊还分析

摊还分析用来评价某个数据结构的一系列操作的平均代价，有时可能某个操作的代价特别高，但总体上来看也并非那么糟糕，可以形象的理解为把高代价的操作“分摊”到其他操作上去了，要求的就是均摊后的平均代价。

摊还分析有三种常用的技术：聚合分析，核算法，势能法。

例1：栈操作：
考虑一个空栈$S$，有三种操作：
1、PUSH(S,x) ：将对象$x$压入栈$S$中。
2、POP(S) ：将栈$S$的栈顶对象弹出，并返回该对象。对空栈调用POP 会产生一个错误。
3、MULTIPOP(S,k) ：循环调用POP(S) ，弹出栈顶的$k$个元素（$k<n$，$n$为栈的最大容量）。

其中，第三种操作的伪代码如下：

MULTIPOP(S,k)
    while not STACK-EMPTY(S) and k>0
        POP(S)
        k=k-1

那么，现在需要分析：执行n次栈操作最坏情况下的时间复杂度是多少？

例2：二进制计数器递增
考虑一个$k$位二进制计数器，其初值为$0$，用一个数组$A_{0\cdots k-1}$来表示，当计数器中保存的值是$x$时，$x$的最低位保存在$A_0$最高为保存在$A_{k-1}$，即：
$$
x=\sum_{i=0}^{k-1}{2^iA_i}
$$
只有一个操作INCREAMENT ，即计数器$+1$：

INCREMENT(A)
    i=0
    while i<k and A[i]==1
        A[i]=0
        i=i+1
    if i<k
        A[i]=1

那么，现在需要分析：执行$n$次该操作最坏情况下的时间复杂度是多少？

聚合分析

利用聚合分析，我们可以证明对于任意的$n$，一个包含$n$个操作的序列花费的总时间为$T(n)$。因此，在最坏情况下，每个操作的平均代价，或称为摊还代价为$\displaystyle \frac{T(n)}{n}$，即每个操作的时间复杂度为$O(1)$。

例1
单独看三个操作，前两个都是$O(1)$的，第三个是$O(n)$的。这样直观的看，最坏情况下，执行$n$次操作的代价是$O(n^2)$，但这实际上是一个松的上界。因为要想达到这个上界，就要尽量多执行第三个操作，但是栈为空以后，第三个操作就什么都不干了。

我们需要对这三个操作整体分析。显然，对于一个非空的栈，可以执行的POP 操作的个数（包括后两个操作的所有POP ）与执行了PUSH 操作的个数相当，即最多$n$次。

因此，$n$次操作最坏情况下执行的时间复杂度为$O(n)$，平均每次操作的代价是$O(1)$。

在聚合分析中，我们将每个操作的摊还代价设定为平均代价，故三种操作的摊还代价都是$O(1)$。

例2
和上一个例子类似，单独考虑每一个操作，如果原来$k$个$1$，操作一次会把$k$个位置全更改一遍，代价是$O(k)$，执行$n$次就是$O(nk)$，这是一个非常松的上界，不可能每次都遇到这种极端情况。

考虑连续的$n$次操作，我们可以得知，每次调用$A_0$都会翻转，每两次调用$A_1$翻转一次，每四次调用$A_2$翻转一次，每$2^i$次调用$A_i$翻转一次。
因此执行$n$次操作的总代价：
$$
\sum_{i=0}^{k-1}{\lfloor\frac{n}{2^i}\rfloor} < n\sum_{i=0}^{\infty}{\frac{1}{2^i}}=2n
$$
故$n$次操作代价是$O(n)$，每次操作代价是$O(1)$。

核算法

用核算法进行摊还分析时，我们对不同操作赋予不同费用，赋予某些操作的费用可能多于或少于其实际代价。我们将赋予一个操作的费用称为它的摊还代价 。当一个操作的摊还代价超出其实际代价时，我们将正差额存入数据结构中的特定对象，存入的正差额称为信用 。对于后续操作中摊还分析小于实际代价的情况，信用可以用来支付负差额。因此，我们可以将一个操作的摊还代价分解为其实际代价和信用（存入的或用掉的）。不同的操作可能有不同的摊还代价。这种方法不同于聚合分析中所有操作都赋予相同摊还代价的方式。

如果我们希望通过分析摊还代价来证明每个操作的平均代价的最坏情况很小，就应确保操作序列的总摊还代价给出了序列真实代价的上界。而且与聚合分析一样，这种关系必须对所有操作序列都成立。将第$i$个操作的摊还代价表示为$\hat{c_i}$，真实代价表示为$c_i$，则要求$\displaystyle \sum_{i=1}^n{\hat{c_i}}\geq\sum_{i=1}^n{c_i}$，数据结构中存储的信用恰好等于总摊还代价与总实际代价的差值，要求这一差值一直保持非负。比如在某个步骤，允许信用为负值（前面操作缴费不足，承诺在随后补齐账户欠费），那么当时的总摊还代价就小于总实际代价，对于到那个时刻为止的操作序列，总摊还代价就不再是总实际代价的上界了。因此，必须保证数据结构中的总信用永远为非负值。

例1
先考虑每个操作的实际代价（$s$是栈中元素个数）：
$$
\begin{array}{c|c}
\bf{PUSH}&1\
\bf{POP}&1\
\bf{MULTIPOP}&\min(k,s)\
\end{array}
$$
然后我们赋予三个操作摊还代价：
$$
\begin{array}{c|c}
\bf{PUSH}&2\
\bf{POP}&0\
\bf{MULTIPOP}&0\
\end{array}
$$
假定使用￥$1$来代表$1$个单位的代价，那么每次PUSH 时，除了支付￥$1$外，我们额外支付￥$1$作为可能发生的将来POP 的预付费（信用），在POP 时直接从信用里取，那么，任意时刻，每个栈里的元素都存在对应的预付费（信用）￥$1$，一定满足当前信用为非负值，即当前摊还代价是实际代价的一个上界。

因此，每次操作的摊还代价是$O(1)$，$n$次操作的摊还代价是$O(n)$。

例2
我们设定置位（$0$变$1$）的摊还代价为$2$，复位（$1$变$0$）的摊还代价为$0$。

与上面的例子的分析方法相同，每次操作至多有$1$个位发生置位，这时除了支付￥$1$的实际代价之外，再预付将来可能发生的复位的代价￥$1$，那么将来复位时就可以直接从信用中拿。

因此，每次操作的摊还代价是$O(1)$，$n$次操作的摊还代价是$O(n)$。

势能分析

势能法摊还分析并不将预付代价表示为数据结构中特定对象的信用，而是表示成“势能”，将势能释放即可用来支付未来操作的代价。我们将势能与整个数据结构而不是特定的对象相关联。

势能法工作方式如下。我们将对一个初始数据结构$D_0$执行$n$个操作。对$\forall i\in[1,n],i\in\mathbb{Z}$，令$c_i$为第$i$个操作的实际代价，令$D_i$为在数据结构$D_{i-1}$上执行第$i$个操作得到的结果数据结构。势能函数$\Phi$将每个数据结构$D_i$映射到$\Phi(D_i)\in\mathbb R$，此值即为关联到数据结构$D_i$的势能，第$i$个操作的摊还代价$\hat{c_i}$用势函数$\Phi$定义为：
$$
\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})
$$

因此，每个操作的摊还代价等于操作的实际代价加上此操作引起的势能变化。

累加即可得n步操作的总摊还代价：
$$
\sum_{i=1}^n{\hat{c_i}}=\sum_{i=1}^n{c_i}+\Phi(D_i)-\Phi(D_0)
$$

如果能定义一个势函数$\Phi$，使得对于$\forall n,\Phi(D_n)\geq\Phi(D_0)$，则总摊还代价$\displaystyle \sum_{i=1}^n{\hat{c_i}}$给出了总实际代价$\displaystyle \sum_{i=1}^n{c_i}$的一个上界。

因此问题的关键在于定义一个合适的势函数$\Phi$。

例1
我们定义势函数为当前栈中的元素个数，那么$\Phi(D_0)=0$，且对于$\forall i,\Phi(D_i)\geq 0=\Phi(D_0)$，那么任意时刻摊还代价都是实际代价的一个上界。

下面分析每个操作的摊还代价。

假设第$i$个操作是PUSH ，且当时栈中包含$s$个对象，那么$\Phi(D_i)-\Phi(D_{i=1})=(s+1)-s=1$，PUSH 操作的摊还代价是：
$$
\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})=1+1=2
$$

假设第i个操作是MULTIPOP(S,k) ，将$k’=\min(k,s)$个对象弹出栈，对象的实际代价为$k’$，势差为$\Phi(D_i)-\Phi(D_{i-1})=-k’$，那么该操作的弹簧代价为：
$$
\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})=k’-k’=0
$$

类似地，普通的POP 操作的弹簧代价也为$0$。

因此，每次操作的摊还代价是$O(1)$，$n$次操作的摊还代价是$O(n)$。

例2
我们定义第$i$次操作后，势函数为当前计数器中$1$的个数$b_i$。

假设第$i$次操作把$t_i$个位复位（$1$变回$0$），则实际代价至多为$t_i+1$，如果$b_i\neq 0$，则所有$k$位都复位了，因此$b_{i-1}=t_i=k$，若干$b_i>0$，则$b_i=b_{i-1}-t_i+1$，无论哪种情况，都满足$b_i\leq b_{i-1}-t_i+1$，势差为：
$$
\Phi(D_i)-\Phi(D_{i-1})\leq(b_{i-1}-t_i+1)-b_{i-1}=1-t_i
$$

因此，摊还代价为：
$$
\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_i-1)\leq(t_i+1)-(1-t_i)=2
$$

因此，每次操作的摊还代价是$O(1)$，$n$次操作的摊还代价是$O(n)$。

另外，即使计数器不是从$0$开始也可以使用势能法分析。

初始时有$b_0$个$1$，$n$次操作以后有$b_n$个$1$，把摊还代价的定义式移项，可得$\displaystyle \sum_{i=1}^n{c_i}=\sum_{i=1}^n{\hat{c_i}}-\Phi(D_n)+\Phi(D_0)=\sum_{i=1}^n{2-b_n+b_0}=2n-b_n+b_0$，由于$b_0\leq k$，因此只要$k=O(n)$，总实际代价就是$O(n)$，即至少执行$O(k)$次即可。

因此，不管计数器初值是什么，$n$次操作的总实际代价都是$O(n)$。

自动机

一个确定有限状态自动机（DFA） 是由以下五部分组成的五元组$(Q,\Sigma,\delta,s,F)$：
1、字符集（$\mathbb{\Sigma}$），该自动机只能输入这些字符。
2、状态集合（$Q$）。
3、起始状态（$s$），$s\in Q$。
4、接受状态集合（$F$），$F\subseteq Q$。
5、转移函数（$\delta$），$\delta$是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。$Q\times\Sigma\rightarrow Q$，即$\delta(q,\sigma)=q’,\ q,q’\in Q,\sigma\in\Sigma$。

KMP自动机

基于字符串$s$的KMP自动机接受且仅接受以$s$为后缀的字符串，$F={\left|s\right|}$。
$$
\delta(i,c)=
\begin{cases}
\displaylines{
i+1 & :s_{i+1}=c\\
0 & :s_1\neq c, \ i=0\\
\delta(\pi(i),c) & :s_{i+1}\neq c, \ i>0
}
\end{cases}
$$

主定理

符号
$\Theta$	$=$
$O$	$\leq$
$o$	$<$
$\Omega$	$\geq$
$\omega$	$>$

将一个规模为$n$的问题，通过分治得到$a$个规模为$\displaystyle\frac{n}{b}$的子问题，每次递归带来的额外计算为$f(n)$，那么：
$$
\begin{aligned}
\displaylines{
\hat c=&\log_ba\\
T(n)=&aT\left(\frac{n}{b}\right)+f(n)\\
T(n)=&
\begin{cases}
\Theta\left(n^{\hat c}\right)&:f(n)=O\left(n^c\right), \ c<\hat c\\
\begin{cases}
\Theta\left(n^{\hat c}\log^{k+1}n\right)&:\exist k>-1\\
\Theta\left(n^{\hat c}\log\log n\right)&:k=-1\\
\Theta\left(n^{\hat c}\right)&:\exist k<-1\\
\end{cases}&:f(n)=\Theta\left(n^{\hat c}\log^kn\right)\\
\Theta(f(n))&:f(n)=\Omega(n^c), \ c>\hat c
\end{cases}
}
\end{aligned}
$$

---

1、当$f(n)=O(n^c), \ c<\hat c$时：

$$
T(n)=\Theta(n^{\hat c})
$$

例如：

$$
\begin{aligned}
\displaylines{
&T(n)=8T\left(\frac{n}{2}\right)+1000n^2\\
&\qquad\qquad\Downarrow\\
&a=8, \ b=2, \ f(n)=1000n^2\\
&\qquad\qquad\Downarrow\\
&c=2\rightarrow f(n)=O(n^c)\\
\therefore&c=2\\
\because&\hat c=\log_ba=\log_28=3>c\\
\therefore&T(n)=\Theta\left(n^{\log_ba}\right)=\Theta(n^3)
}
\end{aligned}
$$

---

2、当$\exist k\geq 0, \ f(n)=\Theta\left(n^{\hat c}\log^kn\right)$时：

$$
T(n)=\Theta\left(n^{\hat c}\log^{k+1}n\right)
$$

例如：

$$
\begin{aligned}
\displaylines{
&T(n)=2T\left(\frac{n}{2}\right)+10n\\
&\qquad\qquad\Downarrow\\
&a=2, \ b=2, \ f(n)=10n\\
&\hat c=\log_ba=\log_22=1\\
&\qquad\qquad\Downarrow\\
&k=0\rightarrow f(n)=O\left(n^{\hat c}\log^kn\right)\\
\therefore&T(n)=\Theta\left(n^{\hat c}\log^{k+1}n\right)=\Theta\left(n^1\log^1n\right)=\Theta(n\log n)
}
\end{aligned}
$$

扩展：

当$\exist k>-1, \ f(n)=\Theta\left(n^{\hat c}\log^kn\right)$时：

$$
T(n)=\Theta\left(n^{\hat c}\log^{k+1}n\right)
$$

当$k=-1, \ f(n)=\Theta\left(n^{\hat c}\log^kn\right)$时：

$$
T(n)=\Theta\left(n^{\hat c}\log\log n\right)
$$

当$\exist k<-1, \ f(n)=\Theta\left(n^{\hat c}\log^kn\right)$

$$
T(n)=\Theta\left(n^{\hat c}\right)
$$

---

3、当$f(n)=\Omega\left(n^c\right), \ c>\hat c$时：

$$
T(n)=\Theta\left(f(n)\right)
$$

例如：

$$
\begin{aligned}
\displaylines{
&T(n)=2T\left(\frac{n}{2}\right)+n^2\\
&\qquad\qquad\Downarrow\\
&a=2, \ b=2, \ f(n)=n^2\\
&\qquad\qquad\Downarrow\\
&c=2\rightarrow f(n)=\Omega\left(n^c\right)\\
\because&\hat c=\log_ba=\log_22=1<c\\
\therefore&T(n)=\Theta\left(n\right)=\Theta\left(n^2\right)
}
\end{aligned}
$$

---

例题

NOIP2016TGT14

假设某算法的时间表示为地推关系式
$$
\begin{aligned}
\displaylines{
T(n)=&2T\left(\frac{n}{4}\right)+\sqrt n\\
T(1)=&1
}
\end{aligned}
$$
则算法的时间复杂度为（C）。
A.$O(n)$B.$O\left(\sqrt n\right)$C.$O\left(\sqrt n\log n\right)$D.$O\left(n^2\right)$

$$
\begin{aligned}
\displaylines{
&a=2, \ b=4, \ f(n)=\sqrt n=n^{\frac{1}{2}}\\
&\hat c=\log_b a=\log_42=\frac{1}{2}\\
&k=0\rightarrow f(n)=O\left(n^{\hat c}\log^kn\right)\\
\therefore&T(n)=\Theta\left(n^{\hat c}\log^{k+1}n\right)=\Theta\left(n^{\frac{1}{2}}\log^1n\right)=\Theta\left(\sqrt n\log n\right)\\
}
\end{aligned}
$$

NOIP2015TGT10

设某算法的计算时间表示为递推关系式
$$
\begin{aligned}
\displaylines{
T(n)=&T(n-1)+n, \ n\in\mathbb N^+\\
T(0)=&1
}
\end{aligned}
$$
则该算法的时间复杂度为（D）。
A.$O(\log n)$B.$O(n\log n)$C.$O(n)$D.$O(n^2)$

$$
\begin{aligned}
\displaylines{
&T(n)\\
=&T(n-1)+n\\
=&T(n-2)+(n-1)+n\\
&\qquad\qquad\vdots\\
=&T(0)+\sum_{i=1}^ni\\
=&1+\frac{(n+1)n}{2}\\
=&O(n^2)
}
\end{aligned}
$$

NOIP2013TGT7

斐波那契数列的定义如下：
$$
\begin{aligned}
\displaylines{
F_1=&1\\
F_2=&1\\
F_n=&F_{n-1}+F_{n-1}, \ n\geq 3
}
\end{aligned}
$$
如果用下面的函数计算斐波那契数列的第$n$项，则其时间复杂度为（D）。

>int F(int n)
>{
if (n <= 2)
	return 1;
else
	return F(n - 1) + F(n - 2);
>}

设计算$f(i)$的次数为$g(i)$。

$$
\begin{aligned}
\displaylines{
\because&f(n)=&f(n-1)+f(n-1)\\
\therefore&g(n)=&g(n-1)+g(n-2)\\
\therefore&g(1)=&f(1)=1,\\
&g(2)=&f(2)=1\\
\because&f(n)=&f(n-1)+f(n+1),\\
&g(n)=&g(n-1)+g(n-2)\\
\therefore&g(n)=f(n)\\
&T(n)=g(n)=f(n)=O(f(n))
}
\end{aligned}
$$

Markdown

常用

\LaTeX\frac{x}{y}\dfrac{x}{y}\sqrt[a]{b}\lim\log\ln\lg\sin\cos\tan\csc\\\sec\cot\gcd\arcsin\arccos\arctan\arg\det\sinh\dim\\\cosh\tanh\exp\ker\Pr\sup\coth\deg\hom\\\det\liminf\limsup\max\min\operatorname a\overset{\underset{def}{}}{=}{}^2_1\!a^3_4\mod a\pmod a\bmod a

$$
\displaylines{
\LaTeX\frac{x}{y}\dfrac{x}{y}\sqrt[a]{b}\lim\log\ln\lg\sin\cos\tan\csc\\
\sec\cot\gcd\arcsin\arccos\arctan\arg\det\sinh\dim\\
\cosh\tanh\exp\ker\Pr\sup\coth\deg\hom\\
\det\liminf\limsup\max\min\operatorname a\overset{\underset{def}{}}{=}{}^2_1!a^3_4\mod a\pmod a\bmod a
}
$$

数学模式重音符号

\hat a\check a\tilde a\grave a\dot a\ddot a\bar a\vec a\widehat a\acute a\\\breve a\widetilde a\overline a\underline a\widetilde a\widehat a\underbrace a_b\overbrace a^b\overleftarrow a\overrightarrow a\boxed a

$$
\displaylines{
\hat a\check a\tilde a\grave a\dot a\ddot a\bar a\vec a\widehat a\acute a\
\breve a\widetilde a\overline a\underline a\widetilde a\widehat a\underbrace a_b\overbrace a^b\overleftarrow a\overrightarrow a\boxed a
}
$$

希腊字母

\Alpha\alpha\Beta\beta\Gamma\gamma\Delta\delta\Epsilon\epsilon\varepsilon\Zeta\zeta\Eta\eta\Theta\theta\vartheta\Iota\iota\Kappa\kappa\\\Lambda\lambda\Mu\mu\Nu\nu\Xi\xi Oo\Pi\pi\varpi\Rho\rho\varrho\Sigma\sigma\varsigma\Tau\tau\Upsilon\upsilon\\\Phi\phi\varphi\Chi\chi\Psi\psi\Omega\omega

$$
\displaylines{
\Alpha\alpha\Beta\beta\Gamma\gamma\Delta\delta\Epsilon\epsilon\varepsilon\Zeta\zeta\Eta\eta\Theta\theta\vartheta\Iota\iota\Kappa\kappa\\
\Lambda\lambda\Mu\mu\Nu\nu\Xi\xi Oo\Pi\pi\varpi\Rho\rho\varrho\Sigma\sigma\varsigma\Tau\tau\Upsilon\upsilon\\
\Phi\phi\varphi\Chi\chi\Psi\psi\Omega\omega
}
$$

二元关系符

<>=\leq\geq\equiv\ll\gg\doteq\prec\\\succ\sim\preceq\succeq\simeq\subset\supset\approx\subseteq\supseteq\\\cong\sqsubset\sqsupset\Join\sqsubseteq\sqsupseteq\bowtie\in\ni\propto\\\vdash\dashv\models\mid\parallel\perp\smile\frown\asymp:\\\lessdot\gtrdot\doteqdot\leqslant\geqslant\risingdotseq\eqslantless\eqslantgtr\fallingdotseq\leqq\\\geqq\eqcirc\lesssim\gtrsim\triangleq\lessapprox\gtrapprox\bumpeq\lessgtr\gtrless\\\Bumpeq\lesseqgtr\gtreqless\thicksim\lesseqqgtr\gtreqqless\thickapprox\preccurlyeq\succcurlyeq\approxeq\\\curlyeqprec\curlyeqsucc\backsim\precsim\succsim\backsimeq\precapprox\succapprox\vDash\subseteqq\\\supseteqq\Vdash\shortparallel\Supset\Vvdash\blacktriangleleft\sqsupset\backepsilon\vartriangleright\because\\\varpropto\blacktriangleright\Subset\between\trianglerighteq\smallfrown\pitchfork\vartriangleleft\shortmid\smallsmile\\\trianglelefteq\therefore\sqsubset

‘\not’+
$$
\displaylines{
<>=\leq\geq\equiv\ll\gg\doteq\prec\\
\succ\sim\preceq\succeq\simeq\subset\supset\approx\subseteq\supseteq\\
\cong\sqsubset\sqsupset\Join\sqsubseteq\sqsupseteq\bowtie\in\ni\propto\\
\vdash\dashv\models\mid\parallel\perp\smile\frown\asymp:\\
\lessdot\gtrdot\doteqdot\leqslant\geqslant\risingdotseq\eqslantless\eqslantgtr\fallingdotseq\leqq\\
\geqq\eqcirc\lesssim\gtrsim\triangleq\lessapprox\gtrapprox\bumpeq\lessgtr\gtrless\\
\Bumpeq\lesseqgtr\gtreqless\thicksim\lesseqqgtr\gtreqqless\thickapprox\preccurlyeq\succcurlyeq\approxeq\\
\curlyeqprec\curlyeqsucc\backsim\precsim\succsim\backsimeq\precapprox\succapprox\vDash\subseteqq\\
\supseteqq\Vdash\shortparallel\Supset\Vvdash\blacktriangleleft\sqsupset\backepsilon\vartriangleright\because\\
\varpropto\blacktriangleright\Subset\between\trianglerighteq\smallfrown\pitchfork\vartriangleleft\shortmid\smallsmile\\
\trianglelefteq\therefore\sqsubset
}
$$
AMS否定关系符和箭头

\nless\ngtr\varsubsetneqq\lneq\gneq\varsupsetneqq\nleq\ngeq\nsubseteqq\nleqslant\\\ngeqslant\nsupseteqq\lneqq\gneqq\nmid\lvertneqq\gvertneqq\nparallel\nleqq\ngeqq\\\nshortmid\lnsim\gnsim\nshortparallel\lnapprox\gnapprox\nsim\nprec\nsucc\ncong\\\npreceq\nsucceq\nvdash\precneqq\succneqq\nvDash\precnsim\succnsim\nVdash\precnapprox\\\succnapprox\nVDash\subsetneq\supsetneq\ntriangleleft\varsubsetneq\varsupsetneq\ntriangleright\nsubseteq\nsupseteq\\\ntrianglelefteq\subsetneqq\nsupseteq\ntrianglerighteq\nleftarrow\nrightarrow\nleftrightarrow\nLeftarrow\nRightarrow\nLeftrightarrow

$$
\displaylines{
\nless\ngtr\varsubsetneqq\lneq\gneq\varsupsetneqq\nleq\ngeq\nsubseteqq\nleqslant\\
\ngeqslant\nsupseteqq\lneqq\gneqq\nmid\lvertneqq\gvertneqq\nparallel\nleqq\ngeqq\\
\nshortmid\lnsim\gnsim\nshortparallel\lnapprox\gnapprox\nsim\nprec\nsucc\ncong\\
\npreceq\nsucceq\nvdash\precneqq\succneqq\nvDash\precnsim\succnsim\nVdash\precnapprox\\
\succnapprox\nVDash\subsetneq\supsetneq\ntriangleleft\varsubsetneq\varsupsetneq\ntriangleright\nsubseteq\nsupseteq\\
\ntrianglelefteq\subsetneqq\nsupseteq\ntrianglerighteq\nleftarrow\nrightarrow\nleftrightarrow\nLeftarrow\nRightarrow\nLeftrightarrow
}
$$

二元运算符

+-\pm\mp\triangleleft\cdot\div\triangleright\times\setminus\star\cup\\\cap\ast\sqcup\sqcap\circ\vee\wedge\bullet\oplus\ominus\\\diamond\odot\oslash\uplus\otimes\bigcirc\amalg\bigtriangleup\bigtriangledown\dagger\\\lhd\rhd\ddagger\unlhd\unrhd\wr\dotplus\centerdot\ltimes\rtimes\\\divideontimes\doublecup\doublecap\smallsetminus\veebar\barwedge\doublebarwedge\boxplus\boxminus\circleddash\\\boxtimes\boxdot\circledcirc\intercal\circledast\rightthreetimes\curlyvee\curlywedge\leftthreetimes

$$
\displaylines{
+-\pm\mp\triangleleft\cdot\div\triangleright\times\setminus\star\cup\\
\cap\ast\sqcup\sqcap\circ\vee\wedge\bullet\oplus\ominus\\
\diamond\odot\oslash\uplus\otimes\bigcirc\amalg\bigtriangleup\bigtriangledown\dagger\\
\lhd\rhd\ddagger\unlhd\unrhd\wr\dotplus\centerdot\ltimes\rtimes\\
\divideontimes\doublecup\doublecap\smallsetminus\veebar\barwedge\doublebarwedge\boxplus\boxminus\circleddash\\
\boxtimes\boxdot\circledcirc\intercal\circledast\rightthreetimes\curlyvee\curlywedge\leftthreetimes
}
$$

“大”运算符

\sum\bigcup\bigvee\prod\bigcap\bigwedge\coprod\bigsqcup\biguplus\int\\\oint\iint\oiint\iiint\oiiint\bigodot\bigoplus\bigotimes

$$
\displaylines{
\sum\bigcup\bigvee\prod\bigcap\bigwedge\coprod\bigsqcup\biguplus\int\\
\oint\iint\oiint\iiint\oiiint\bigodot\bigoplus\bigotimes
}
$$

箭头

\leftarrow\longleftarrow\rightarrow\longrightarrow\leftrightarrow\longleftrightarrow\Leftarrow\Longleftarrow\Rightarrow\Longrightarrow\\\Leftrightarrow\longleftrightarrow\mapsto\longmapsto\hookleftarrow\hookrightarrow\leftharpoonup\rightharpoonup\leftharpoondown\rightharpoondown\\\rightleftharpoons\iff\uparrow\downarrow\updownarrow\Uparrow\Downarrow\Updownarrow\nearrow\searrow\\\swarrow\nwarrow\leadsto\dashleftarrow\dashrightarrow\leftleftarrows\rightrightarrows\leftrightarrows\rightleftarrows\Lleftarrow\\\Rrightarrow\twoheadleftarrow\twoheadrightarrow\leftarrowtail\rightarrowtail\leftrightharpoons\rightleftharpoons\Lsh\Rsh\looparrowleft\\\looparrowright\curvearrowleft\curvearrowright\circlearrowleft\circlearrowright\multimap\upuparrows\downdownarrows\upharpoonleft\upharpoonright\\\downharpoonright\rightsquigarrow\leftrightsquigarrow\xleftarrow[b] a\xrightarrow[b] a\xLeftarrow a\xRightarrow x\xleftrightarrow a\xLeftrightarrow a

‘\n’+
$$
\displaylines{
\leftarrow\longleftarrow\rightarrow\longrightarrow\leftrightarrow\longleftrightarrow\Leftarrow\Longleftarrow\Rightarrow\Longrightarrow\\
\Leftrightarrow\longleftrightarrow\mapsto\longmapsto\hookleftarrow\hookrightarrow\leftharpoonup\rightharpoonup\leftharpoondown\rightharpoondown\\
\rightleftharpoons\iff\uparrow\downarrow\updownarrow\Uparrow\Downarrow\Updownarrow\nearrow\searrow\\
\swarrow\nwarrow\leadsto\dashleftarrow\dashrightarrow\leftleftarrows\rightrightarrows\leftrightarrows\rightleftarrows\Lleftarrow\\
\Rrightarrow\twoheadleftarrow\twoheadrightarrow\leftarrowtail\rightarrowtail\leftrightharpoons\rightleftharpoons\Lsh\Rsh\looparrowleft\\
\looparrowright\curvearrowleft\curvearrowright\circlearrowleft\circlearrowright\multimap\upuparrows\downdownarrows\upharpoonleft\upharpoonright\\
\downharpoonright\rightsquigarrow\leftrightsquigarrow\xleftarrow[b] a\xrightarrow[b] a\xLeftarrow a\xRightarrow x\xleftrightarrow a\xLeftrightarrow a
}
$$

定界符

()\uparrow\lbrack\rbrack\downarrow\lbrace\rbrace\updownarrow\langle\\\rangle\vert\lfloor\rfloor\lceil/\backslash\Updownarrow\Uparrow\Downarrow\\\Vert\rceil\ulcorner\urcorner\llcorner\lrcorner\lvert\rvert\lVert\rVert\tbinom{a}{b}\left(\right)\left[\right]

$$
\displaylines{
()\uparrow\lbrack\rbrack\downarrow\lbrace\rbrace\updownarrow\langle\\
\rangle\vert\lfloor\rfloor\lceil/\backslash\Updownarrow\Uparrow\Downarrow\\
\Vert\rceil\ulcorner\urcorner\llcorner\lrcorner\lvert\rvert\lVert\rVert\tbinom{a}{b}\left(\right)\left[\right]
}
$$

大定界符

\lgroup a\rgroup a\lmoustache a\rmoustache a

$$
\lgroup a\rgroup a\lmoustache a\rmoustache a
$$

其他符号

\dots\cdots\vdots\ddots\hbar\imath\jmath\ell\Re\Im\\\aleph\wp\forall\exists\mho\partial'\prime\emptyset\infty\\\nabla\triangle\Box\Diamond\bot\top\angle\surd\diamondsuit\heartsuit\\\clubsuit\spadesuit\neg\flat\natural\sharp\hbar\hslash\Bbbk\square\\\blacksquare\circledS\vartriangle\blacktriangle\complement\triangledown\blacktriangledown\Game\lozenge\blacklozenge\\\bigstar\angle\measuredangle\diagup\diagdown\backprime\nexists\Finv\varnothing\eth\\\sphericalangle\mho

$$
\displaylines{
\dots\cdots\vdots\ddots\hbar\imath\jmath\ell\Re\Im\\
\aleph\wp\forall\exists\mho\partial’\prime\emptyset\infty\\
\nabla\triangle\Box\Diamond\bot\top\angle\surd\diamondsuit\heartsuit\\
\clubsuit\spadesuit\neg\flat\natural\sharp\hbar\hslash\Bbbk\square\\
\blacksquare\circledS\vartriangle\blacktriangle\complement\triangledown\blacktriangledown\Game\lozenge\blacklozenge\\
\bigstar\angle\measuredangle\diagup\diagdown\backprime\nexists\Finv\varnothing\eth\\
\sphericalangle\mho
}
$$

非数学符号

\dag\copyright\ddag\pounds\%

$$
\dag\copyright\ddag\pounds%
$$

希腊和希伯来字母

\digamma\varkappa\beth\gimel\daleth

$$
\digamma\varkappa\beth\gimel\daleth
$$

数字字母

ABCDE abcde 1234\\
\mathrm{ABCDE abcde 1234}\\
\mathit{ABCDE abcde 1234}\\
\mathnormal{ABCDE abcde 1234}\\
\mathcal{ABCDE abcde 1234}\\
\mathscr{ABCDE abcde 1234}\\
\mathfrak{ABCDE abcde 1234}\\
\mathbb{ABCDE abcde 1234}\\
\mathbf{ABCDE abcde 1234}\\
\mathtt{ABCDE abcde 1234}\\
\mathsf{ABCDE abcde 1234}\\
\text{ABCDE abcde 1234}\\
\scriptstyle\text{ABCDE abcde 1234}

$$
\displaylines{
ABCDE abcde 1234\\
\mathrm{ABCDE abcde 1234}\\
\mathit{ABCDE abcde 1234}\\
\mathnormal{ABCDE abcde 1234}\\
\mathcal{ABCDE abcde 1234}\\
\mathscr{ABCDE abcde 1234}\\
\mathfrak{ABCDE abcde 1234}\\
\mathbb{ABCDE abcde 1234}\\
\mathbf{ABCDE abcde 1234}\\
\mathtt{ABCDE abcde 1234}\\
\mathsf{ABCDE abcde 1234}\\
\text{ABCDE abcde 1234}\\
\scriptstyle\text{ABCDE abcde 1234}
}
$$

约去符 删除线

\cancel a\bcancel a\xcancel a

$$
\cancel a\bcancel a\xcancel a
$$

矩阵

\begin{matrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{matrix}
\begin{pmatrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{pmatrix}
\begin{bmatrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{bmatrix}
\begin{Bmatrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{Bmatrix}\\
\begin{vmatrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{vmatrix}
\begin{Vmatrix}
    0&1&1\\
    1&1&0\\
    1&0&1\\
\end{Vmatrix}
\begin{array}{c|lcr}
    \downarrow &a&b&c\\
    \hline
    R_1&c&b&a\\
    R_2&b&c&c\\
\end{array}
\begin{cases}
    a_1x+b_1y+c_1z=d_1\\
    a_2x+b_2y+c_2z=d_2\\
    a_3x+b_3y+c_3z=d_3\\
\end{cases}\\
\begin{aligned}
    a_1x+b_1y+c_1z=d_1\\
    a_2x+b_2y+c_2z=d_2\\
    a_3x+b_3y+c_3z=d_3\\
\end{aligned}

$$
\displaylines{
\begin{matrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{matrix}
\begin{pmatrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{pmatrix}
\begin{bmatrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{bmatrix}
\begin{Bmatrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{Bmatrix}\\
\begin{vmatrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{vmatrix}
\begin{Vmatrix}
0&1&1\\
1&1&0\\
1&0&1\\
\end{Vmatrix}
\begin{array}{c|lcr}
\downarrow &a&b&c\\
\hline
R_1&c&b&a\\
R_2&b&c&c\\
\end{array}
\begin{cases}
a_1x+b_1y+c_1z=d_1\\
a_2x+b_2y+c_2z=d_2\\
a_3x+b_3y+c_3z=d_3\\
\end{cases}\\
\begin{aligned}
a_1x+b_1y+c_1z=d_1\\
a_2x+b_2y+c_2z=d_2\\
a_3x+b_3y+c_3z=d_3\\
\end{aligned}
}
$$

读入优化

long long int read(void){
	long long int ans=0;
	char ch=getchar(),last=' ';
	while((ch<'0')||(ch>'9'))
		last=ch,
		ch=getchar();
	while((ch>='0')&&(ch<='9'))
		ans=(ans<<3)+(ans<<1)+ch-'0',
		ch=getchar();
	if(last=='-')
		ans=-ans;
	return ans;
};

Fread

const int n=21;
char buf[1<<n],*inf=buf;
long long int read(void){
	long long int ans=0;
	char last=' ';
	while((*inf<'0')||(*inf>'9'))
		last=*inf,
		inf++;
	while((*inf>='0')&&(*inf<='9'))
		ans=ans*10+*inf-'0',
		inf++;
	if(last=='-')
		ans=-ans;
	return ans;
};
freopen("*.in","r",stdin);
fread(buf,1,1<<n,stdin);

pb_ds

#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

hash

#include<ext/pb_ds/hash_policy.hpp>
cc_hash_table<string,int>;
gp_hash_table<string,int>;

heap

#include<ext/pb_ds/priority_queue.hpp>
priority_queue<int,greater<int>,pairing_heap_tag/binary_heap_tag/binomial_heap_tag/rc_binomial_heap_tag/thin_heap_tag/无>;
	push();
	top();
	size();
	empty();
	clear();
	pop();
	join(priority_queue &other);//合并两个堆,other会被清空
	split(Pred prd,priority_queue &other);//分离出两个堆
	modify(point_iterator it,const key);//修改一个节点的值

rb-tree

#include<ext/pb_ds/tree_policy.hpp>
tree<int,null_type/
null_mapped_type,rb_tree_tag/splay_tree_tag,tree_order_statistics_node_update>//关键字类型 无映射 从小到大排序 红黑树 结点更新
	insert();
	erase();
	lower_bound();//前驱
	upper_bound();//后继
	join(b);//b并入a 前提是两棵树的key的取值范围不相交
	split(v,b);//key 小于等于 v 的元素属于a，其余的属于b
	//需填写tree_order_statistics_node_update 
	order_of_key();//求k在树中是第几大
	find_by_order();//求树中的第k大

trie

#include<ext/pb_ds/trie_policy.hpp>
trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>;
	insert();
	erase();
	join(trie& b);

pair

pair<::iterator,::iterator>range=.prefix_range(.length());
for(::iterator it=range.first;it!=range.second;it++)
	cout<<*it<<endl;

位运算

inline int abs(const int n){
    return (n^(n>>31))-(n>>31);
};
inline int max(const int a,const int b){
    return b&((a-b)>>31)|a&(~(a-b)>>31);
};
inline int min(const int a,const int b){
    return a&((a-b)>>31)|b&(~(a-b)>>31);
};
inline int ave(const int x,const int y){
	return (x&y)+((x^y>>1));
};

模拟退火

$$
\begin{aligned}
\Delta E=&E_{t+1}-E_t\geq 0\
P(\Delta E)=&
\begin{cases}
1&:E_{t+1}<E_t\
e^{\frac{-\Delta E}{T}}&:E_{t+1}\geq E_t
\end{cases}
\end{aligned}
$$

#include <cstdlib>
const double T0=3000,Tk=1e-13,D=0.996,lim=0.85;
srand((unsigned)time(NULL));
void sa(void){
	t=T0,
	ansx=tmpx,
	ansy=tmpy;
	while(t>=Tk){
		dx=tmpx+((rand()*2)-RAND_MAX)*t,
		dy=tmpy+((rand()*2)-RAND_MAX)*t,
		dw=calc(dx,dy),
		d=dw-answ;
		if(d>0)
			tmpx=ansx=dx,
			tmpy=ansy=dy,
			answ=dw;
		else
			if(exp(d/t)*(double)RAND_MAX>(double)rand())
				ansx=dx,
				ansy=dy;
		t*=D;
	};
	return void();
};

卡时

#include <ctime>
const double lim=0.95;
time_t begin,end;
begin=clock();
while(true){
	end=clock();
	if((double)(end-begin)/CLOCKS_PER_SEC>=lim)
		break;
	sa();
};

时间复杂度

时间复杂度	$1s$内稳过的数据范围	$1s$内的极限范围（不保险）
$O(1)$	$\infty$	$\infty$	数学、贪心
$O(\log n)$	$\infty$	$\infty$	矩阵乘法
$O(n)$	$\leq 5\times 10^7$	$\leq 10^8$	数学、贪心
$O(n\log n)$	$\leq 5\times 10^5$	$\leq 10^6$	二分答案、二分查找、快速排序、归并算法
$O(n\log^2n)$	$\leq 10^5$	$\leq 3\times 10^5$	三分
$O(n\sqrt n\log n)$	$\leq 6\times 10^4$	$\leq 10^5$	莫队
$O(n\sqrt n)$	$\leq 10^4$	$\leq 6\times 10^4$	莫队、根号算法的筛
$O(n^2)$	$\leq 5\times 10^3$	$\leq 10^4$	动态规划、图论
$O(n^2\log\log n)$	$\leq 5\times 10^2$	$\leq 10^4$	二分套二分、三分、树链剖分、LCT
$O(n^3)$	$\leq 3\times 10^2$	$\leq 5\times 10^2$	搜索、Floyd
$O(n^4)$	$\leq 50$	$\leq 150$
$O(2^n)$	$\leq 25$	$\leq 27$	状态压缩DP、搜索
$O(n!)$	$\leq 11$	$\leq 11$（稳过）
$O(n^n)$	$\leq 8$	$\leq 8$（稳过）
$O(\infty)$	N/A	N/A	猴子排序

一般情况下，$256M$内存的话，int数组最多可以开到$6\times 10^7$，$1s$可以跑$10^8$次，一般常数下$5\times 10^7$左右。

对拍

@echo off
color 0A
set i=0
:loop
	set /a i=%i%+1
	cls
	echo Test #%i%:
	rand.exe
	b.exe
	a.exe
	fc res1.out res2.out
	if not errorlevel 1 goto loop
	color 0C & pause

rand

inline int rnd(void){
	return (rand()<<15)|rand();
};

shuffle

#include <algorithm>
#include <chrono>
shuffle(a+1,a+n+1,default_random_engine(chrono::system_clock::now().time_since_epoch().count()));

__int128

__int128 read(void){
	__int128 tans=0;
	char ch=getchar(),last=' ';
	while((ch<'0')||(ch>'9'))
		ch=getchar();
	while((ch>='0')&&(ch<='9'))
		tans=tans*10+ch-'0',
		ch=getchar();
	if(last=='-')
    	tans=-tans;
	return tans;
};
void print(__int128 k){
	if(k<0){
    	putchar('-');
        k=-k;
    };
	if(k>9)
		print(k/10);
	putchar(k%10+'0');
	return void();
};

priority_queue

priority_queue<int>//大根堆 

priority_queue<int,vector<int>,greater<int> >q;//小根堆
priority_queue<int,vector<int>,less<int> >q;//大根堆 

struct data{
	int x;
	inline data(int a){
		x=a;
	};
	inline bool operator<(const data &a)const{
		return x<a.x;
	};
};
priority_queue<data>q;//大根堆

struct data{
	inline bool operator()(const int a,const int b)const{
		return a<b;
	};
};
priority_queue<int,vector<int>,data>q;//大根堆