ACM模板_axiomofchoice

语法

c++

这些定义其实是用来打cf的。语言标准:c++11

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define vector basic_string
#define fi first
#define se second
#ifndef qwq
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#endif
//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=200010; const double err=1e-11; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf; typedef long double llf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;} template<typename T> T sqr(const T &x){return x*x;} typedef pair<int,int> pii; template<typename A,typename B> ostream &operator<<(ostream &o,const pair<A,B> &x){return o<<'('<<x.fi<<','<<x.se<<')';}
const int mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
//#define int ll
signed main(){
	
	return 0;
}

放在本地的内容(比如可以放进 bits/stdc++.h

#define qwq [&]{cerr<<"qwq"<<endl;}()
#define orz(x) [&]{cerr<<#x": "<<x<<endl;}()
#define orzarr(a,n) [&]{cerr<<#a": "; repeat(__,0,n)cerr<<(a)[__]<<" "; cerr<<endl;}()
#define orzeach(a) [&]{cerr<<#a": "; for(auto __:a)cerr<<__<<" "; cerr<<endl;}()

如果没有万能头

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>

删减版(看得清楚点qwq)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2;
typedef double lf; const lf err=1e-11;
typedef pair<int,int> pii;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define qwq (cerr<<"qwq"<<endl)
#define orz(x) (cerr<<#x": "<<x<<endl)
#define orzarr(a,n) {cerr<<#a": "; repeat(__,0,n)cerr<<(a)[__]<<" "; cerr<<endl;}
#define orzeach(a) {cerr<<#a": "; for(auto __:a)cerr<<__<<" "; cerr<<endl;}
#define fi first
#define se second
inline ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;}
inline lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;}
mt19937 rnd(time(0));
const int N=100010;
const int mod=(1?1000000007:998244353);
//#define int ll
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	return 0;
}

其他定义

#define lll __int128
#define inline __inline __attribute__((always_inline))

平板电视红黑树

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> t; //红黑树
t.insert({x,i+1}); //----------------- 插入x,用独特的正整数i+1标注(因为erase太辣鸡)
t.erase(t.lower_bound({x,0})); //----- 删除x(删除单个元素)
t.order_of_key({x,0})+1; //----------- x的排名(小于x的元素个数+1)
t.find_by_order(x-1)->first; //------- 排名为x的元素(第x小的数)
prev(t.lower_bound({x,0}))->first; //- x的前驱(小于x且最大)
t.lower_bound({x+1,0})->first; //----- x的后继(大于x且最小)
t.join(t2); //------------------------ 将t2并入t,t2清空,前提是取值范围不相交(所以没卵用)
t.split(v,t2); //--------------------- 小于等于v的元素属于t,其余的属于t2

平板电视优先队列

#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag> h; //大根堆
h.push(x); h.top(); h.pop();
h.join(h2); //将h2并入h,h2清空

rope

#include <ext/rope>
using namespace __gnu_cxx;
rope<int> r; //块状链表
r.push_back(n);
r.insert(pos,n); //插入一个元素
r.erase(pos,len); //区间删除
r.copy(pos,len,x); //区间赋值
r.substr(pos,len); //这是啥
r[pos] //只能访问不能修改
rope<int> *his[N]; his[i]=new rope<int>(*his[i-1]); //据说O(1)拷贝,一行可持久化

随机数

#include<random>
mt19937 rnd(time(0));
//巨佬定义:mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<rnd()<<endl; //范围是unsigned int

STL汇总

将第k+1小的数置于k这个位置:nth_element(begin,begin+k,end);
返回是否存在:binary_search(begin,end,key,[less])
返回限制最小值地址:upper_bound(begin,end,key,[less])
返回严格限制最小值地址:lower_bound(begin,end,key,[less])
填充:fill(begin,end,element);
递增填充(赋值为t,t+1,t+2,...):iota(begin,end,t);
复制(注意会复制到b里):copy(a_begin,a_end,b_begin);
翻转:reverse(begin,end);
单次归并排序(合并有序列表a,b至c):merge(a_begin,a_end,b_begin,b_end,c_begin,[less]);
归并排序(原地保存):inplace_merge(begin,begin+k,end);
vector去重(之前要排序):a.erase(unique(a.begin(),a.end()),a.end());
vector释放额外内存:a.shrink_to_fit();
并集(结果存c):set_union(a_begin,a_end,b_begin,b_end,c_begin);
O(n)建堆:priority_queue<int>(begin,end)
set,map查找,没找到返回end():a.find(key)
set,map限制最小值:a.lower_bound(key)
set,map合并:a.insert(b.begin(),b.end()); //O(nlogn)
complex<lf> c; complex<lf> c(1,2);//复数
c.real(),c.imag() //实部、虚部
bitset<32> b; //声明一个32位的bitset
b[n]; b[n]=1; //访问和修改
b.reset(); b.set(); //全部置0或置1
b.none(); //返回是否为空
b.count(); //返回1的个数
b.flip(); b.flip(n); //全反、反转第n位

手写hash

struct myhash{
	ll f(ll x)const{
		x+=0x9e3779b97f4a7c15;
		x=(x^(x>>30))*0xbf58476d1ce4e5b9;
		x=(x^(x>>27))*0x94d049bb133111eb;
		return x^(x>>31);
	}
	ll operator()(int x)const{
		static int t=chrono::steady_clock::now().time_since_epoch().count();
		return f(x+t);
	}
};

面向对象

struct vi:vector<int>{ //继承
	mutable int x; //强制可修改,比如在set中可以直接修改
	explicit vi(int){} //禁止隐式转换的构造函数
};

吸氧气

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")

进制转换

itoa(n,str,base) //将n存入字符数组中(只能int)(不一定能用,cf就不行)
strtol(str,0,base),strtoll //返回字符数组的base进制数
stol(s,0,base),stoll //返回字符串的base进制数
sscanf,sprintf //十进制
to_string(n) //十进制

cmath

lround(x) //四舍五入到long
llround(x) //四舍五入到long long
fmod(x) //浮点取模
ilogb(x) //相当于(int)floor(log2(x))
tgamma(x) //计算Γ(x)
atan2(x,y) //计算坐标(x,y)的极角
hypot(x,y) //计算sqrt(x^2+y^2)

scanf字符串正则化

scanf("%ns",str); //读入n个字符
scanf("%[a-z]",str); //遇到非小写字母停止
scanf("%[^0-9]",str); //遇到数字停止,^是非
scanf("%*[a-z]"); //也是遇到非小写字母停止,只不过不读入字符串

双关键字比较

参数包(直接从t神模板抄过来的,貌似没卵用)

void debug_out(){cerr<<endl;}
template<typename Head,typename... Tail>
void debug_out(Head H,Tail... T){
	cerr<<" "<<H;
	debug_out(T...);
}
#define debug(...) cerr<<"["#__VA_ARGS__"]:",debug_out(__VA_ARGS__)

神奇特性

java

import java.util.*;
import java.math.BigDecimal;
import java.math.BigInteger;
public class Main{
static Scanner sc;
public static void main(String[] args){
	sc=new Scanner(System.in);
}
}

数据类型

int     //4字节有符号
long    //8字节有符号
double
boolean
char    //还能表示Unicode字符
String

数组

int[] arr=new int[100]; //数组
int[] arr=new int[]{1,2,3}; //有初始值、不指定长度的声明
int[] arr={1,2,3}; //有初始值、不指定长度的声明
arr.length //获取数组长度
int[][] arr=new int[10][10]; //二维数组
Array.sort(arr,l,r); //对arr[l..(r-1)]排序(import java.util.Arrays;)

输出

System.out.print(x);
System.out.println();
System.out.println(x); //自动换行
System.out.printf("%.2f\n",d); //格式化:%d %f %s

输入

import java.util.Scanner;
Scanner sc=new Scanner(System.in); //初始化
String s=sc.nextline(); //读一行字符串
int n=sc.nextInt(); //读整数
double d=sc.nextDouble(); //读实数
sc.hasNext() //是否读完

String

不可变性:内部是常量
比较:s1.equals(s2)
是否包含子串s2:s1.contains(s2)
查找子串:s1.indexOf(s2)
反向查找子串:s1.lastIndexOf(s2)
获取子串:s1.substring(2,4) //首末坐标[2,4)
提取字符:s1.charAt(3) //就像c++的s1[3]
s1.equalsIgnoreCase(s2)
s1.startsWith(s2) //boolean
s1.endsWith(s2) //boolean

Math

//不用import就能用下列函数
Math.{sqrt,sin,atan,abs,max,min,pow,exp,log,PI,E}

Random

import java.util.Random;
Random rnd=new Random(); //已经把时间戳作为了种子
rnd.nextInt();
rnd.nextInt(n); //[0,n)

class

class node{
	int l,r;
} //不用分号
//之后在class Main里定义static node name

BigInteger

import java.math.BigInteger;
BigInteger n=new BigInteger("0");
BigInteger[] arr=new BigInteger[10];
n.intValue() //转换为int
n.longValue() //转换
n.doubleValue() //转换
n.add(n2) //加法
n.subtract(n2) //减法
n.multiply(n2) //乘法
n.divide(n2) //除法
n.mod(n2) //取模
BigInteger.valueOf(I) //int转换为BigInteger
n.compareTo(n2) //n>n2返回1,n<n2返回-1,n==n2返回0
n.abs()
n.pow(I)
n.toString(I) //返回I进制字符串
//运算时n2一定要转换成BigInteger

BigDecimal

import java.math.BigDecimal;
n.divide(n2,2,BigDecimal.ROUND_HALF_UP) //保留两位(四舍五入)
//貌似没有sqrt等操作,都得自己实现qwq

暴力算法

离散化

void disc(int a[],int n){
	vector<int> b(a,a+n);
	sort(b.begin(),b.end());
	b.erase(unique(b.begin(),b.end()),b.end());
	repeat(i,0,n)
		a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin(); //从0开始编号
}
void disc(int a[],int n,int d){ //把距离>d的拉近到d
	vector<int> b(a,a+n);
	sort(b.begin(),b.end());
	b.erase(unique(b.begin(),b.end()),b.end());
	vector<int> c(b.size()); c[0]=0; //从0开始编号
	repeat(i,1,b.size())
		c[i]=c[i-1]+min(d,b[i]-b[i-1]);
	repeat(i,0,n)
		a[i]=c[lower_bound(b.begin(),b.end(),a[i])-b.begin()];
}

01分数规划

int n,k; lf a[N],b[N],c[N];
bool check(lf mid){
	repeat(i,0,n)c[i]=a[i]-mid*b[i];
	nth_element(c,c+k,c+n,greater<lf>());
	lf sum=0; repeat(i,0,k)sum+=c[i];
	return sum>=0;
}
lf solve(){
	lf l=0,r=1;
	while(r-l>1e-9){
		lf mid=(l+r)/2;
		if(check(mid))l=mid; else r=mid;
	}
	return l;
}

分治

逆序数×二维偏序

void merge(int l,int r){ //归并排序 
	//对[l,r-1]的数排序
	if(r-l<=1)return;
	int mid=l+(r-l)/2;
	merge(l,mid);
	merge(mid,r);
	int p=l,q=mid,s=l;
	while(s<r){
		if(p>=mid || (q<r && a[p]>a[q])){
			t[s++]=a[q++];
			ans+=mid-p; //统计逆序数
		}
		else
			t[s++]=a[p++];
	}
	for(int i=l;i<r;++i)a[i]=t[i];
}

最大空矩阵 | 悬线法

int n,m,a[N][N],l[N][N],r[N][N],u[N][N];
int getlm(){
	int ans=0;
	repeat(i,0,n)
	repeat(k,0,m)
		l[i][k]=r[i][k]=u[i][k]=(a[i][k]==0);
	repeat(i,0,n){
		repeat(k,1,m)
		if(a[i][k]==0)
			l[i][k]=l[i][k-1]+1; //可以向左延伸几格
		repeat_back(k,0,m-1)
		if(a[i][k]==0)
			r[i][k]=r[i][k+1]+1; //可以向右延伸几格
		repeat(k,0,m)
		if(a[i][k]==0){
			if(i!=0 && a[i-1][k]==0){
				u[i][k]=u[i-1][k]+1; //可以向上延伸几格
				l[i][k]=min(l[i][k],l[i-1][k]);
				r[i][k]=min(r[i][k],r[i-1][k]); //如果向上延伸u格,lr对应的修改
			}
			ans=max(ans,(l[i][k]+r[i][k]-1)*u[i][k]);
		}
	}
	return ans;
}

搜索

舞蹈链

精确覆盖

int n,m;
vector<int> rec; //dance后存所有选中的行的编号
struct DLX{
	#define rep(i,i0,a) for(int i=a[i0];i!=i0;i=a[i])
	int u[N],d[N],l[N],r[N],x[N],y[N]; //x[]行,y[]列,N=10010
	int sz[N],h[N]; //一列几个元素,行首元素
	int top;
	void init(){
		top=m;
		repeat(i,0,m+1){
			sz[i]=0;
			u[i]=d[i]=i;
			l[i]=i-1;
			r[i]=i+1;
		}
		l[0]=m;
		r[m]=0;
		repeat(i,0,n+1)h[i]=-1;
		rec.clear();
	}
	void add(int x0,int y0){ //添加(x0,y0)
		top++;
		sz[y0]++;
		x[top]=x0;
		y[top]=y0;
		u[top]=u[y0];
		d[top]=y0;
		u[d[top]]=d[u[top]]=top;
		if(h[x0]<0)
			h[x0]=l[top]=r[top]=top;
		else{
			l[top]=h[x0];
			r[top]=r[h[x0]];
			l[r[h[x0]]]=top;
			r[h[x0]]=top;
		}
	}
	void remove(int c){ //删除列c中出现1的所有行
		l[r[c]]=l[c];
		r[l[c]]=r[c];
		rep(i,c,d)
		rep(j,i,r){
			u[d[j]]=u[j];
			d[u[j]]=d[j];
			sz[y[j]]--;
		}
	}
	void resume(int c){ //重置列c中出现1的所有行
		rep(i,c,d)
		rep(j,i,r){
			u[d[j]]=d[u[j]]=j;
			sz[y[j]]++;
		}
		l[r[c]]=r[l[c]]=c;
	}
	bool dance(int dep=1){ //返回是否可行
		if(r[0]==0)return 1;
		int c=r[0];
		rep(i,0,r)
		if(sz[c]>sz[i])
			c=i; //选取出现1元素次数最少的一列进行删除(依次删除这一列有1的行)
		remove(c);
		rep(i,c,d){
			rep(j,i,r)
				remove(y[j]);
			if(dance(dep+1)){rec.push_back(x[i]);return 1;}
			rep(j,i,l)
				resume(y[j]);
		}
		resume(c);
		return 0;
	}
}dlx;

重复覆盖

struct DLX{
	#define rep(i,d,s) for(node* i=s->d;i!=s;i=i->d)
	struct node{
		node *l,*r,*u,*d;
		int x,y;
	};
	static const int M=2e5;
	node pool[M],*h[M],*R[M],*pl;
	int sz[M],vis[M],ans,clk;
	void init(int n,int m){ //行和列
		clk=0;
		ans=inf;
		pl=pool;
		++m;
		repeat(i,0,max(n,m)+1){
			R[i]=0;
			sz[i]=0;
			vis[i]=-1;
		}
		repeat(i,0,m)
		h[i]=new(pl++)node;
		repeat(i,0,m){
			h[i]->l=h[(i+m-1)%m];
			h[i]->r=h[(i+1)%m];
			h[i]->u=h[i]->d=h[i];
			h[i]->y=i;
		}
	}
	void link(int x,int y){
		sz[y]++;
		auto p=new(pl++)node;
		p->x=x; p->y=y;
		p->u=h[y]->u; p->d=h[y];
		p->d->u=p->u->d=p;
		if(!R[x])R[x]=p->l=p->r=p;
		else{
			p->l=R[x]; p->r=R[x]->r;
			p->l->r=p->r->l=p;
		}
	}
	void remove(node* p){
		rep(i,d,p){
			i->l->r=i->r;
			i->r->l=i->l;
		}
	}
	void resume(node* p){
		rep(i,u,p)
			i->l->r=i->r->l=i;
	}
	int eval(){
		++clk;
		int ret=0;
		rep(i,r,h[0])
		if(vis[i->y]!=clk){
			++ret;
			vis[i->y]=clk;
			rep(j,d,i)
			rep(k,r,j)
			vis[k->y]=clk;
		}
		return ret;
	}
	void dfs(int d){
		if(h[0]->r==h[0]){ans=min(ans,d); return;}
		if(eval()+d>=ans)return;
		node* c;
		int m=inf;
		rep(i,r,h[0])
		if(sz[i->y]<m){m=sz[i->y]; c=i;}
		rep(i,d,c){
			remove(i);
			rep(j,r,i)remove(j);
			dfs(d+1);
			rep(j,l,i)resume(j);
			resume(i);
		}
	}
	int solve(){ //返回最优解 
		ans=inf;
		dfs(0);
		return ans;
	}
}dlx;

启发式算法

A-star

模拟退火

由于退火退不出太令人绝望了(其实是太菜了),建议少用

动态规划

多重背包

int n,V; ll dp[N];
void push(int val,int v,int c){ //处理物品(价值=val,体积=v,个数=c)
	for(int b=1;c;c-=b,b=min(b*2,c)){
		ll dv=b*v,dval=b*val;
		repeat_back(j,dv,V+1)
			dp[j]=max(dp[j],dp[j-dv]+dval);
	}
}
//初始化fill(dp,dp+V+1,0),结果是dp[V]
int n,V; ll dp[N];
void push(int val,int v,int c){ //处理物品(价值=val,体积=v,个数=c)
	static deque< pair<int,ll> > q; //单调队列,fi是位置,se是价值
	if(v==0){
		repeat(i,0,V+1)dp[i]+=val*c;
		return;
	}
	c=min(c,V/v);
	repeat(d,0,v){
		q.clear();
		repeat(j,0,(V-d)/v+1){
			ll t=dp[d+j*v]-j*val;
			while(!q.empty() && t>=q.back().se)
				q.pop_back();
			q.push_back({j,t});
			while(q.front().fi<j-c)
				q.pop_front();
			dp[d+j*v]=max(dp[d+j*v],q.front().se+j*val);
		}
	}
}
//初始化fill(dp,dp+V+1,0),结果是dp[V]

最长不下降子序列

const int inf=1e9;
repeat(i,0,n+1)dp[i]=inf; //初始化为inf
repeat(i,0,n)
	*lower_bound(dp,dp+n,a[i])=a[i];
return lower_bound(dp,dp+n,inf)-dp;

数位dp

ll dp[20][*],bit[20];
ll dfs(int pos,ll *,bool lim=1,bool lz=1){
	if(pos==-1)return *; //返回该状态是否符合要求(0或1)
	ll &x=dp[pos][*];
	if(!lim && x!=-1)return x;
	ll ans=0;
	int maxi=lim?bit[pos]:9;
	repeat(i,0,maxi+1){
		...//状态转移
		if(lz && i==0)...//可能要用lz,其他地方都不用
		ans+=dfs(pos-1,*,
			lim && i==maxi,
			lz && i==0);
	}
	if(!lim)x=ans; //不限制的时候才做存储
	return ans;
}
ll solve(ll n){
	int len=0;
	while(n)bit[len++]=n%10,n/=10;
	return dfs(len-1,*);
}
signed main(){
	mst(dp,-1); //在很多时候dp值可以反复使用
	ll t=read();
	while(t--){
		ll l=read(),r=read();
		printf("%lld\n",solve(r)-solve(l-1));
	}
	return 0;
}

换根dp

void dfs1(int x,int fa=-1){
	for(auto p:a[x])
	if(p!=fa){
		dfs1(p,x);
		dp[x]+=op(dp[p]);
	}
}
void dfs2(int x,int fa=-1){
	ans[x]=dp[x];
	for(auto p:a[x])
	if(p!=fa){
		dp[x]-=op(dp[p]);
		dp[p]+=op(dp[x]);
		dfs2(p,x);
		dp[p]-=op(dp[x]);
		dp[x]+=op(dp[p]);
	}
}

斜率优化

四边形优化

repeat(i,0,n)dp[i][i]=0,m[i][i]=i;
repeat(len,2,n+1)
for(int l=0,r=len-1;r<n;l++,r++){
	dp[l][r]=inf;
	repeat(k,m[l][r-1],min(m[l+1][r]+1,r))
	if(dp[l][r]>dp[l][k]+dp[k+1][r]+w(l,r)){
		dp[l][r]=dp[l][k]+dp[k+1][r]+w(l,r);
		m[l][r]=k;
	}
}

计算几何

struct of 向量

struct vec{
	lf x,y;
	vec(lf x=0,lf y=0):x(x),y(y){}
	vec operator-(const vec &b){return vec(x-b.x,y-b.y);}
	vec operator+(const vec &b){return vec(x+b.x,y+b.y);}
	vec operator*(lf k){return vec(k*x,k*y);}
	lf len(){return hypot(x,y);}
	lf sqr(){return x*x+y*y;}
	/*截取*/vec trunc(lf k=1){return *this*(k/len());}
	/*逆时针旋转*/vec rotate(double th){lf c=cos(th),s=sin(th); return vec(x*c-y*s,x*s+y*c);}
}a[N];
lf cross(vec a,vec b){return a.x*b.y-a.y*b.x;};
lf cross(vec a,vec b,vec c){return cross(a-b,b-c);}
lf dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
bool cmp_xy(const vec &a,const vec &b){return make_pair(a.x,a.y)<make_pair(b.x,b.y);}
bool cmp_atan(const vec &a,const vec &b){return atan2(a.x,a.y)<atan2(b.x,b.y);}
/*输出*/ostream &operator<<(ostream &o,const vec &v){return o<<'('<<v.x<<','<<v.y<<')';}

平面几何基本操作

判断两条线段是否相交

bool judge(vec a,vec b,vec c,vec d){ //线段ab和线段cd
	#define SJ(x) max(a.x,b.x)<min(c.x,d.x)\
	|| max(c.x,d.x)<min(a.x,b.x)
	if(SJ(x) || SJ(y))return 0;
	#define SJ2(a,b,c,d) cross(a-b,a-c)*cross(a-b,a-d)<=0
	return SJ2(a,b,c,d) && SJ2(c,d,a,b);
}

others of 平面几何基本操作

点是否在线段上

bool onseg(vec p,vec a,vec b){
	return (a.x-p.x)*(b.x-p.x)<err
	&& (a.y-p.y)*(b.y-p.y)<err
	&& fabs(cross(a-b,a-p))<err;
}

多边形面积

lf area(vec a[],int n){
	lf ans=0;
	repeat(i,0,n)
		ans+=cross(a[i],a[(i+1)%n]);
	return fabs(ans/2);
}

多边形的面积质心

vec centre(vec a[],int n){
	lf S=0;
	vec v=vec();
	repeat(i,0,n){
		vec &v1=a[i],&v2=a[(i+1)%n];
		lf s=cross(v1,v2);
		S+=s;
		v=v+(v1+v2)*s;
	}
	return v*(1/(3*S));
}

二维凸包

//struct vec{构造函数,减法,小于};
lf cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
lf cross(vec a,vec b,vec c){return cross(a-b,b-c);}
vector<vec> st;
void push(vec &v,int b){
	while(st.size()>b
	&& cross(*++st.rbegin(),st.back(),v)<=0) //会得到逆时针的凸包
		st.pop_back();
	st.push_back(v);
}
void convex(vec a[],int n){
	st.clear();
	sort(a,a+n);
	repeat(i,0,n)push(a[i],1);
	int b=st.size();
	repeat_back(i,1,n-1)push(a[i],b);
	//repeat_back自动变成上凸包
}

旋转卡壳

lf calipers(vec a[],int n){
	convex(a,n); //凸包算法
	repeat(i,0,st.size())a[i]=st[i]; n=st.size();
	lf ans=0;
	int p=1;
	a[n]=a[0];
	repeat(i,0,n){
		while(cross(a[p],a[i],a[i+1])<cross(a[p+1],a[i],a[i+1])) //必须逆时针凸包 
			p=(p+1)%n;
		ans=max(ans,(a[p]-a[i]).len());
		ans=max(ans,(a[p+1]-a[i]).len()); //这里求了直径
	}
	return ans;
}

最大空矩形 | 扫描法

struct vec{
	int x,y; //可能是lf
	vec(int x,int y):x(x),y(y){}
};
vector<vec> a; //存放点
int l,w;
int ans=0;
void work(int i){
	int u=w,d=0;
	repeat(k,i+1,a.size())
	if(a[k].y>d && a[k].y<u){
		ans=max(ans,(a[k].x-a[i].x)*(u-d)); //更新ans
		if(a[k].y==a[i].y)return; //可行性剪枝
		(a[k].y>a[i].y?u:d)=a[k].y; //更新u和d
		if((l-a[i].x)*(u-d)<=ans)return; //最优性剪枝
	}
	ans=max(ans,(l-a[i].x)*(u-d)); //撞墙更新ans
}
int query(){
	a.push_back(vec(0,0));
	a.push_back(vec(l,w)); //加两个点方便处理
	//小矩形的左边靠着顶点的情况
	sort(a.begin(),a.end(),[](vec a,vec b){return a.x<b.x;});
	repeat(i,0,a.size())
		work(i);
	//小矩形的右边靠着顶点的情况
	repeat(i,0,a.size())a[i].x=l-a[i].x; //水平翻折
	sort(a.begin(),a.end(),[](vec a,vec b){return a.x<b.x;});
	repeat(i,0,a.size())
		work(i);
	//小矩形左右边都不靠顶点的情况
	sort(a.begin(),a.end(),[](vec a,vec b){return a.y<b.y;});
	repeat(i,0,(int)a.size()-1)
		ans=max(ans,(a[i+1].y-a[i].y)*l);
	return ans;
}

平面最近点对 | 分治

lf ans;
bool cmp_y(vec a,vec b){return a.y<b.y;}
void rec(int l,int r){ //左闭右开区间
	#define upd(x,y) {ans=min(ans,(x-y).len());}
	if(r-l<4){
		repeat(i,l,r)
		repeat(j,i+1,r)
			upd(a[i],a[j]);
		sort(a+l,a+r,cmp_y); //按y排序
		return;
	}
	int m=(l+r)/2;
	lf midx=a[m].x;
	rec(l,m),rec(m,r);
	static vec b[N];
	merge(a+l,a+m,a+m,a+r,b+l,cmp_y); //逐渐按y排序
	copy(b+l,b+r,a+l);
	int t=0;
	repeat(i,l,r)
	if(fabs(a[i].x-midx)<ans){
		repeat_back(j,0,t){
			if(a[i].y-b[i].y>ans)break;
			upd(a[i],b[j]);
		}
		b[t++]=a[i];
	}
}
lf nearest(){
	ans=1e20;
	sort(a,a+n); //按x排序
	rec(0,n);
	return ans;
}

最小圆覆盖 | 随机增量法

struct cir{ //圆(结构体)
	vec v; lf r;
	bool out(vec a){ //点a在圆外
		return (v-a).len()>r+err;
	}
	cir(vec a){ //点圆
		v=a;
		r=0;
	}
	cir(vec a,vec b){ //确定直径的圆
		v=(a+b)*0.5;
		r=(v-a).len();
	}
	cir(vec a,vec b,vec c){ //三个点的外接圆
		b=b-a,c=c-a;
		vec s=vec(b.sqr(),c.sqr())*0.5;
		lf d=1/cross(b,c);
		v=a+vec(s.x*c.y-s.y*b.y,s.y*b.x-s.x*c.x)*d;
		r=(v-a).len();
	}
};
cir RIA(vec *a,int n){ //RIA=随机增量法
	repeat_back(i,2,n)swap(a[rand()%i],a[i]); //random_shuffle(a,a+n);
	cir c=cir(a[0]);
	repeat(i,1,n)
	if(c.out(a[i])){
		c=cir(a[i]);
		repeat(j,0,i)
		if(c.out(a[j])){
			c=cir(a[i],a[j]);
			repeat(k,0,j)
			if(c.out(a[k]))
				c=cir(a[i],a[j],a[k]);
		}
	}
	return c;
}

struct of 三维向量

struct vec{
	lf x,y,z;
	vec(lf x=0,lf y=0):x(x),y(y){};
	vec operator-(vec b){return vec(x-b.x,y-b.y,z-b.z);}
	vec operator+(vec b){return vec(x+b.x,y+b.y,z+b.z);}
	vec operator*(lf k){return vec(k*x,k*y,k*z);}
	bool operator<(vec b)const{return make_tuple(x,y,z)<make_pair(b.x,b.y,b.z);}
	lf len(){return sqrt(x*x+y*y+z*z);}
}a[N];
vec cross(vec a,vec b){
	return vec(
		a.y*b.z-a.z*b.y,
		a.z*b.x-a.x*b.z,
		a.x*b.y-a.y*b.x);
}
lf dot(vec a,vec b){return a.x*b.x+a.y*b.y+a.z*b.z;}

三维凸包

const lf err=1e-9;
struct vec{
	lf x,y,z;
	vec(lf x=0,lf y=0,lf z=0):x(x),y(y),z(z){};
	vec operator-(vec b){return vec(x-b.x,y-b.y,z-b.z);}
	lf len(){return sqrt(x*x+y*y+z*z);}
	void shake(){ //微小扰动
		x+=(rand()*1.0/RAND_MAX-0.5)*err;
		y+=(rand()*1.0/RAND_MAX-0.5)*err;
		z+=(rand()*1.0/RAND_MAX-0.5)*err;
	}
}a[N];
vec cross(vec a,vec b){
	return vec(
		a.y*b.z-a.z*b.y,
		a.z*b.x-a.x*b.z,
		a.x*b.y-a.y*b.x);
}
lf dot(vec a,vec b){return a.x*b.x+a.y*b.y+a.z*b.z;}
struct face{
	int p[3];
	vec normal(){ //法向量
		return cross(a[p[1]]-a[p[0]],a[p[2]]-a[p[0]]);
	}
	lf area(){return normal().len()/2.0;}
};
vector<face> f;
bool see(face f,vec v){
	return dot(v-a[f.p[0]],f.normal())>0;
}
void convex(vec a[],int n){
	static vector<face> c;
	static bool vis[N][N];
	repeat(i,0,n)a[i].shake(); //防止四点共面
	f.clear();
	f.push_back((face){0,1,2});
	f.push_back((face){0,2,1});
	repeat(i,3,n){
		c.clear();
		repeat(j,0,f.size()){
			bool t=see(f[j],a[i]);
			if(!t) //加入背面
				c.push_back(f[j]);
			repeat(k,0,3){
				int x=f[j].p[k],y=f[j].p[(k+1)%3];
				vis[x][y]=t;
			}
		}
		repeat(j,0,f.size())
		repeat(k,0,3){
			int x=f[j].p[k],y=f[j].p[(k+1)%3];
			if(vis[x][y] && !vis[y][x]) //加入新面
				c.push_back((face){x,y,i});
		}
		f.swap(c);
	}
}

计算几何杂项

正幂反演

others of 计算几何杂项

曼哈顿、切比雪夫距离

Pick定理

四面体体积公式

四元数与旋转

数据结构

st表

普通st表

struct ST{
	#define logN 21
	#define U(x,y) max(x,y)
	ll a[N][logN];
	void init(int n){
		repeat(i,0,n)
			a[i][0]=in[i];
		repeat(k,1,logN)
		repeat(i,0,n-(1<<k)+1)
			a[i][k]=U(a[i][k-1],a[i+(1<<(k-1))][k-1]);
	}
	ll query(int l,int r){
		int s=31-__builtin_clz(r-l+1);
		return U(a[l][s],a[r-(1<<s)+1][s]);
	}
}st;

二维st表

struct ST{ //注意logN=log(N)+2
	#define logN 9
	#define U(x,y) max(x,y)
	int f[N][N][logN][logN],log[N];
	ST(){
		log[1]=0;
		repeat(i,2,N)
			log[i]=log[i/2]+1;
	}
	void build(){
		repeat(k,0,logN)
		repeat(l,0,logN)
		repeat(i,0,n-(1<<k)+1)
		repeat(j,0,m-(1<<l)+1){
			int &t=f[i][j][k][l];
			if(k==0 && l==0)t=a[i][j];
			else if(k)
				t=U(f[i][j][k-1][l],f[i+(1<<(k-1))][j][k-1][l]);
			else
				t=U(f[i][j][k][l-1],f[i][j+(1<<(l-1))][k][l-1]);
		}
	}
	int query(int x0,int y0,int x1,int y1){
		int k=log[x1-x0+1],l=log[y1-y0+1];
		return U(U(U(
			f[x0][y0][k][l],
			f[x1-(1<<k)+1][y0][k][l]),
			f[x0][y1-(1<<l)+1][k][l]),
			f[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);
	}
}st;

补充:猫树

struct cat{
	#define U(a,b) max(a,b) //查询操作
	#define a0 0 //查询操作的零元
	#define logN 21
	vector<ll> a[logN];
	vector<ll> v;
	void init(){
		repeat(i,0,logN)a[i].clear();
		v.clear();
	}
	void push(ll in){
		v.push_back(in);
		int n=v.size()-1;
		repeat(s,1,logN){
			int len=1<<s; int l=n/len*len;
			if(n%len==len/2-1){
				repeat(i,0,len)a[s].push_back(a0);
				repeat_back(i,0,len/2)a[s][l+i]=U(a[s][l+i+1],v[l+i]);
			}
			if(n%len>=len/2)
				a[s][n]=(U(a[s][n-1],v[n]));
		}
	}
	ll query(int l,int r){ //区间查询
		if(l==r)return v[l];
		int s=32-__builtin_clz(l^r);
		return U(a[s][l],a[s][r]);
	}
}tr;

单调队列

struct MQ{ //查询就用mq.q.front().first
	deque<pii> q; //first:保存的最小值; second:时间戳
	int T;
	void init(){
		q.clear();
		T=0;
	}
	void push(int n){
		T++;
		while(!q.empty() && q.back().first>=n) //min
			q.pop_back();
		q.push_back({n,T});
		while(!q.empty() && q.front().second<=T-k)
			q.pop_front();
	}
}mq;

树状数组

普通树状数组

#define lb(x) (x&(-x))
struct BIT{
	ll t[N]; //一倍内存吧
	void init(){
		mst(t,0);
	}
	void add(ll x,ll k){ //位置x加上k
		//x++;
		for(;x<N;x+=lb(x))
			t[x]+=k;
	}
	ll sum(ll x){ //求[1,x]的和 //[0,x]
		//x++;
		ll ans=0;
		for(;x!=0;x-=lb(x))
			ans+=t[x];
		return ans;
	}
}bit;

超级树状数组

struct SPBIT{
	BIT a,a1; 
	void init(){a.init();a1.init();}
	void add(ll x,ll y,ll k){
		a.add(x,k);
		a.add(y+1,-k);
		a1.add(x,k*(x-1));
		a1.add(y+1,-k*y);
	}
	ll sum(ll x,ll y){
		return y*a.sum(y)-(x-1)*a.sum(x-1)-(a1.sum(y)-a1.sum(x-1));
	}
}spbit;

二维超级树状数组

int n,m;
#define lb(x) (x&(-x))
struct BIT{
	ll t[N][N]; //一倍内存吧
	void init(){
		mst(t,0);
	}
	void add(int x,int y,ll k){ //位置(x,y)加上k
		//x++,y++; //如果要从0开始编号
		for(int i=x;i<=n;i+=lb(i))
		for(int j=y;j<=m;j+=lb(j))
			t[i][j]+=k;
	}
	ll sum(int x,int y){ //求(1..x,1..y)的和
		//x++,y++; //如果要从0开始编号
		ll ans=0;
		for(int i=x;i!=0;i-=lb(i))
		for(int j=y;j!=0;j-=lb(j))
			ans+=t[i][j];
		return ans;
	}
};
struct SPBIT{
	BIT a,ax,ay,axy;
	void add(int x,int y,int k){
		a.add(x,y,k);
		ax.add(x,y,k*x);
		ay.add(x,y,k*y);
		axy.add(x,y,k*x*y);
	}
	ll sum(int x,int y){
		return a.sum(x,y)*(x*y+x+y+1)
			-ax.sum(x,y)*(y+1)
			-ay.sum(x,y)*(x+1)
			+axy.sum(x,y);
	}
	void add(int x0,int y0,int x1,int y1,int k){ //区间修改
		add(x0,y0,k);
		add(x0,y1+1,-k);
		add(x1+1,y0,-k);
		add(x1+1,y1+1,k);
	}
	ll sum(int x0,int y0,int x1,int y1){ //区间查询
		return sum(x1,y1)
			-sum(x0-1,y1)
			-sum(x1,y0-1)
			+sum(x0-1,y0-1);
	}
}spbit;

线段树

数组版

struct seg{ //init(1,L,R) update(1,L,R,?,?,?) query(1,L,R,?,?)
	#define U(x,y) (x+y) //查询运算
	#define a0 0 //查询运算的零元
	#define z0 0 //修改运算的零元
	#define toz(n,x) z[n]+=x //加载到懒标记
	#define toa() a[n]+=z[n]*(r-l+1),z[n]=z0 //懒标记加载到数据(z别忘了清空)
	#define lc n*2
	#define rc n*2+1
	#define LC lc,l,(l+r)/2
	#define RC rc,(l+r)/2+1,r
	ll a[N*4],z[N*4]; //四倍内存(其实是大于N的最小的2的整数次幂的两倍)
	void up(int n){
		a[n]=U(a[lc],a[rc]);
	}
	void init(int n,int l,int r){
		z[n]=z0;
		if(l==r){
			a[n]=in[l];
			return;
		}
		init(RC);
		init(LC);
		up(n);
	}
	void down(int n,int l,int r){
		if(l<r){
			toz(lc,z[n]);
			toz(rc,z[n]);
		}
		toa();
	}
	void update(int n,int l,int r,int x,int y,ll k){
		x=max(x,l); y=min(y,r); if(x>y){down(n,l,r); return;}
		if(x==l && y==r){
			toz(n,k);
			down(n,l,r);
			return;
		}
		down(n,l,r);
		update(LC,x,y,k);
		update(RC,x,y,k);
		up(n);
	}
	ll query(int n,int l,int r,int x,int y){
		x=max(x,l); y=min(y,r); if(x>y)return a0;
		down(n,l,r);
		if(x==l && y==r)
			return a[n];
		return U(query(LC,x,y),query(RC,x,y));
	}
}tr;

指针版

struct seg{ //初始化init()修改查询tr->sth()
	#define U(x,y) (x+y) //查询运算
	#define a0 0 //查询运算的零元
	void toz(ll x){z+=x,state=1;} //加载到懒标记
	void toa(){a+=z*(r-l+1),z=0,state=0;} //懒标记加载到数据(z别忘了清空)
	ll a,z; bool state; //数据,懒标记,是否偷了懒
	int l,r;
	seg *lc,*rc;
	void init(int,int);
	void up(){
		a=U(lc->a,rc->a);
	}
	void down(){
		if(!state)return;
		if(l<r){
			lc->toz(z);
			rc->toz(z);
		}
		toa();
	}
	void update(int x,int y,ll k){
		x=max(x,l); y=min(y,r); if(x>y){down();return;}
		if(x==l && y==r){
			toz(k);
			down();
			return;
		}
		down();
		lc->update(x,y,k);
		rc->update(x,y,k);
		up();
	}
	ll query(int x,int y){
		x=max(x,l); y=min(y,r); if(x>y)return a0;
		down();
		if(x==l && y==r)
			return a;
		return U(lc->query(x,y),rc->query(x,y));
	}
}tr[N*2],*pl;
void seg::init(int _l,int _r){
	l=_l,r=_r;
	state=0;
	if(l==r){
		a=in[l];
		return;
	}
	int m=(l+r)>>1;
	lc=++pl; lc->init(l,m);
	rc=++pl; rc->init(m+1,r);
	up();
}
void init(int l,int r){
	pl=tr;
	tr->init(l,r);
}

补充:zkw线段树

struct seg{
	#define U(a,b) max(a,b) //查询操作
	ll a0=0; //查询操作的零元
	int n; ll a[1024*1024*4*2]; //内存等于2^k且大于等于两倍inn
	void init(int inn){ //建树
		for(n=1;n<inn;n<<=1); repeat(i,inn,n)in[i]=a0;
		repeat(i,0,n)a[n+i]=in[i];
		repeat_back(i,1,n)up(i);
	}
	void up(int x){
		a[x]=U(a[x<<1],a[(x<<1)^1]);
	}
	void update(int x,ll k){ //位置x加上k
		a[x+=n]+=k; //也可以赋值等操作
		while(x>>=1)up(x);
	}
	ll query(int l,int r){ //区间查询
		ll ans=a0;
		for(l+=n-1,r+=n+1;l^r^1;l>>=1,r>>=1){
			if(~l & 1)ans=U(ans,a[l^1]); //l^1其实是l+1
			if(r & 1)ans=U(ans,a[r^1]); //r^1其实是r-1
		}
		return ans;
	}
}tr;

补充:李超线段树

int funx; //这是y()的参数
struct func{
	lf k,b; int id;
	lf y()const{return k*funx+b;} //funx点处的高度
	bool operator<(const func &b)const{
		return make_pair(y(),-id)<make_pair(b.y(),-b.id);
	}
};
struct seg{ //初始化init()更新update()查询query(),func::y()是高度
	func a;
	int l,r;
	seg *ch[2];
	void init(int,int);
	void push(func d){
		funx=(l+r)/2;
		if(a<d)swap(a,d); //这个小于要用funx
		if(l==r)return;
		ch[d.k>a.k]->push(d);
	}
	void update(int x,int y,const func &d){ //更新[x,y]区间
		x=max(x,l); y=min(y,r); if(x>y)return;
		if(x==l && y==r)push(d);
		else{
			ch[0]->update(x,y,d);
			ch[1]->update(x,y,d);
		}
	}
	const func &query(int x){ //询问
		funx=x;
		if(l==r)return a;
		const func &b=ch[(l+r)/2<x]->query(x);
		return max(a,b); //这个max要用funx
	}
}tr[N*2],*pl;
void seg::init(int _l,int _r){
	l=_l,r=_r; a={0,-inf,-1}; //可能随题意改变
	if(l==r)return;
	int m=(l+r)/2;
	(ch[0]=++pl)->init(l,m);
	(ch[1]=++pl)->init(m+1,r);
}
void init(int l,int r){
	pl=tr;
	tr->init(l,r);
}
void add(int x0,int y0,int x1,int y1){ //线段处理并更新
	if(x0>x1)swap(x0,x1),swap(y0,y1);
	lf k,b;
	if(x0==x1)k=0,b=max(y0,y1);
	else{
		k=lf(y1-y0)/(x1-x0);
		b=y0-k*x0;
	}
	id++;
	tr->update(x0,x1,{k,b,id});
}

并查集

普通并查集

struct DSU{ //合并:d[x]=d[y],查找:d[x]==d[y]
	int a[N];
	void init(int n){iota(a,a+n+1,0);}
	int fa(int x){
		return a[x]==x?x:a[x]=fa(a[x]);
	}
	int &operator[](int x){
		return a[fa(x)];
	}
}d;
struct DSU{
	int a[10010],sz[10010];
	void init(int n){
		iota(a,a+n+1,0);
		fill(sz,sz+n+1,1);
	}
	int fa(int x){
		return a[x]==x?x:a[x]=fa(a[x]);
	}
	bool query(int x,int y){ //查找
		return fa(x)==fa(y);
	}
	void join(int x,int y){ //合并
		x=fa(x),y=fa(y);
		if(x==y)return;
		if(sz[x]>sz[y])swap(x,y);
		a[x]=y;
		sz[y]+=sz[x];
	}
}d;

种类并查集

struct DSU{
	int a[50010],r[50010];
	void init(int n){
		repeat(i,0,n+1)a[i]=i,r[i]=0;
	}
	int plus(int a,int b){ //关系a+关系b,类似向量相加
		if(a==b)return -a;
		return a+b;
	}
	int inv(int a){ //关系a的逆
		return -a;
	}
	int fa(int x){ //返回根节点 
		if(a[x]==x)return x;
		int f=a[x],ff=fa(f);
		r[x]=plus(r[x],r[f]);
		return a[x]=ff;
	}
	bool query(int x,int y){ //是否存在关系
		return fa(x)==fa(y);
	}
	int getr(int x,int y){ //查找关系
		return plus(r[x],inv(r[y]));
	}
	void join(int x,int y,int r2){ //按r2关系合并
		r2=plus(plus(inv(r[x]),r2),r[y]);
		x=fa(x),y=fa(y);
		a[x]=y,r[x]=r2;
	}
}d;

左偏树

struct leftist{ //编号从1开始,因为空的左右儿子会指向0
	#define lc LC[x]
	#define rc RC[x]
	vector<int> val,dis,exist,dsu,LC,RC;
	void init(){add(0);dis[0]=-1;}
	void add(int v){
		int t=val.size();
		val.pb(v);
		dis.pb(0);
		exist.pb(1);
		dsu.pb(t);
		LC.pb(0);
		RC.pb(0);
	}
	int top(int x){
		return dsu[x]==x?x:dsu[x]=top(dsu[x]);
	}
	void join(int x,int y){
		if(exist[x] && exist[y] && top(x)!=top(y))
			merge(top(x),top(y));
	}
	int merge(int x,int y){
		if(!x || !y)return x+y;
		if(val[x]<val[y]) //大根堆
			swap(x,y);
		rc=merge(rc,y);
		if(dis[lc]<dis[rc])
			swap(lc,rc);
		dsu[lc]=dsu[rc]=dsu[x]=x;
		dis[x]=dis[rc]+1;
		return x;
	}
	void pop(int x){
		x=top(x);
		exist[x]=0;
		dsu[lc]=lc;
		dsu[rc]=rc;
		dsu[x]=merge(lc,rc); //指向x的dsu也能正确指向top
	}
	#undef lc
	#undef rc
}lt;
//添加元素lt.add(v),位置是lt.val.size()-1
//是否未被pop:lt.exist(x)
//合并:lt.join(x,y)
//堆顶:lt.val[lt.top(x)]
//弹出:lt.pop(x)

珂朵莉树×老司机树

struct ODT{
	struct node{
		int l,r;
		mutable int v; //强制可修改
		bool operator<(const node &b)const{return l<b.l;}
	};
	set<node> a;
	void init(){ //初始化
		a.clear();
		a.insert({-inf,inf,0});
	}
	set<node>::iterator split(int x){ //分裂区间
		auto it=--a.upper_bound({x,0,0});
		if(it->l==x)return it;
		int l=it->l,r=it->r,v=it->v;
		a.erase(it);
		a.insert({l,x-1,v});
		return a.insert({x,r,v}).first;
	}
	void assign(int l,int r,int v){ //区间赋值
		auto y=split(r+1),x=split(l);
		a.erase(x,y);
		a.insert({l,r,v});
	}
	int sum(int l,int r){ //操作示例:区间求和
		auto y=split(r+1),x=split(l);
		int ans=0;
		for(auto i=x;i!=y;i++){
			ans+=(i->r-i->l+1)*i->v;
		}
		return ans;
	}
}odt;

K-D tree

struct node{
	int x,y,v;
}s[N];
bool cmp1(int a,int b){return s[a].x<s[b].x;}
bool cmp2(int a,int b){return s[a].y<s[b].y;}
struct kdtree{
	int rt,cur; //rt根节点
	int d[N],sz[N],lc[N],rc[N]; //d=1竖着砍,sz子树大小
	int L[N],R[N],D[N],U[N]; //该子树的界线
	int sum[N]; //维护的二维区间信息(二维区间和)
	int g[N],gt;
	void up(int x){ //更新信息
		sz[x]=sz[lc[x]]+sz[rc[x]]+1;
		sum[x]=sum[lc[x]]+sum[rc[x]]+s[x].v;
		L[x]=R[x]=s[x].x;
		D[x]=U[x]=s[x].y;
		if(lc[x]){
			L[x]=min(L[x],L[lc[x]]);
			R[x]=max(R[x],R[lc[x]]);
			D[x]=min(D[x],D[lc[x]]);
			U[x]=max(U[x],U[lc[x]]);
		}
		if(rc[x]){
			L[x]=min(L[x],L[rc[x]]);
			R[x]=max(R[x],R[rc[x]]);
			D[x]=min(D[x],D[rc[x]]);
			U[x]=max(U[x],U[rc[x]]);
		}
	}
	int build(int l,int r){ //以序列g[l..r]为模板重建树,返回根节点
		if(l>r)return 0;
		int mid=(l+r)>>1;
		lf ax=0,ay=0,sx=0,sy=0;
		for(int i=l;i<=r;i++)ax+=s[g[i]].x,ay+=s[g[i]].y;
		ax/=(r-l+1);
		ay/=(r-l+1);
		for(int i=l;i<=r;i++){
			sx+=(ax-s[g[i]].x)*(ax-s[g[i]].x);
			sy+=(ay-s[g[i]].y)*(ay-s[g[i]].y);
		}
		if(sx>sy)
			nth_element(g+l,g+mid,g+r+1,cmp1),d[g[mid]]=1;
		else
			nth_element(g+l,g+mid,g+r+1,cmp2),d[g[mid]]=2;
		lc[g[mid]]=build(l,mid-1);
		rc[g[mid]]=build(mid+1,r);
		up(g[mid]);
		return g[mid];
	}
	void pia(int x){ //将树还原成序列g
		if(!x)return;
		pia(lc[x]);
		g[++gt]=x;
		pia(rc[x]);
	}
	void ins(int &x,int v){
		if(!x){
			x=v;
			up(x);
			return;
		}
		#define ch(f) (f?rc:lc)
		if(d[x]==1)
			ins(ch(s[v].x>s[x].x)[x],v);
		else
			ins(ch(s[v].y>s[x].y)[x],v);
		up(x);
		if(0.725*sz[x]<=max(sz[lc[x]],sz[rc[x]])){
			gt=0;
			pia(x);
			x=build(1,gt);
		}
	}
	void insert(int x,int y,int v){ //在(x,y)处插入元素
		cur++;
		s[cur]={x,y,v};
		ins(rt,cur);
	}
	int x1,x2,y1,y2;
	int qry(int x){
		if(!x || x2<L[x] || x1>R[x] || y2<D[x] || y1>U[x])return 0;
		if(x1<=L[x] && R[x]<=x2 && y1<=D[x] && U[x]<=y2)return sum[x];
		int ret=0;
		if(x1<=s[x].x && s[x].x<=x2 && y1<=s[x].y && s[x].y<=y2)
			ret+=s[x].v;
		return qry(lc[x])+qry(rc[x])+ret;
	}
	int query(int _x1,int _x2,int _y1,int _y2){ //查询[x1,x2]×[y1,y2]的区间和
		x1=_x1; x2=_x2; y1=_y1; y2=_y2;
		return qry(rt);
	}
	void init(){
		rt=cur=0;
	}
}tr;

莫队

普通莫队

struct node{
	int l,r,id;
	bool operator<(const node &b)const{
		if(l/unit!=b.l/unit)return l<b.l; //按块排序
		if((l/unit)&1) //奇偶化排序
			return r<b.r;
		return r>b.r;
	}
};
vector<node> query; //查询区间
int unit,n,bkt[N],a[N],final_ans[N]; //bkt是桶
ll ans;
void update(int x,int d){
	int &b=bkt[a[x]];
	ans-=C(b,2); //操作示例
	b+=d;
	ans+=C(b,2); //操作示例
}
void solve(){ //final_ans[]即最终答案
	fill(bkt,bkt+n+1,0);
	unit=int(ceil(sqrt(n)));
	sort(query.begin(),query.end());
	int l=1,r=0; ans=0; //如果原数组a编号从1开始
	for(auto i:query){
		while(l<i.l)update(l++,-1);
		while(l>i.l)update(--l,1);
		while(r<i.r)update(++r,1);
		while(r>i.r)update(r--,-1);
		final_ans[i.id]=ans;
	}
}
//repeat(i,0,m)query.push_back({read(),read(),i}); //输入查询区间

带修莫队

二叉搜索树

struct TR{
	TR *ch[2],*fa; //ch[0]左儿子,ch[1]右儿子,fa父亲,根的父亲是inf
    int v,dep; //v是结点索引,dep深度,根的深度是1
	TR(TR *fa,int v,int dep):fa(fa),v(v),dep(dep){
		mst(ch,0);
	}
	void insert(int v2){ //tr->insert(v2)插入结点
		auto &c=ch[v2>v];
		if(c==0)c=new TR(this,v2,dep+1);
		else c->insert(v2);
	}
}*tr=new TR(0,inf,0);
//inf是无效节点,用tr->ch[0]来访问根节点

一些建议

双头优先队列可以用multiset

支持插入、查询中位数可以用双堆

priority_queue<ll> h1; //大根堆
priority_queue< ll,vector<ll>,greater<ll> > h2; //小根堆
void insert(ll x){
	#define maintain(h1,h2,b) {h1.push(x); if(h1.size()>h2.size()+b)h2.push(h1.top()),h1.pop();}
	if(h1.empty() || h1.top()>x)maintain(h1,h2,1)
	else maintain(h2,h1,0);
}
//h1.size()+h2.size()为奇数时h1.top()为中位数,偶数看题目定义

双关键字堆可以用两个multiset模拟

struct HEAP{
	multiset<pii> a[2];
	void init(){a[0].clear();a[1].clear();}
	pii rev(pii x){return {x.second,x.first};}
	void push(pii x){
		a[0].insert(x);
		a[1].insert(rev(x));
	}
	pii top(int p){
		pii t=*--a[p].end();
		return p?rev(t):t;
	}
	void pop(int p){
		auto t=--a[p].end();
		a[p^1].erase(a[p^1].lower_bound(rev(*t)));
		a[p].erase(t);
	}
};

高维前缀和

//<1>
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
	b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
//<2>
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
	a[i][j]+=a[i][j-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
	a[i][j]+=a[i-1][j];

一个01串,支持把某位置的1改成0,查询某位置之后第一个1的位置,可以用并查集(删除 d[x]=d[x+1],查询 d[x]

图论

图论的一些概念







图论基础

前向星

struct edge{int to,w,nxt;}; //指向,权值,下一条边
vector<edge> a;
int head[N];
void addedge(int x,int y,int w){
	a.push_back((edge){y,w,head[x]});
	head[x]=a.size()-1;
}
void init(int n){ //初始化
	a.clear();
	fill(head,head+n,-1);
}
//for(int i=head[x];i!=-1;i=a[i].nxt) //遍历x出发的边(x,a[i].to)

拓扑排序

queue<int> q; int ideg[N]; vector<int> ans;
void toposort(){
	repeat(x,0,n)for(auto p:a[x])ideg[p]++;
	repeat(i,0,n)if(ideg[i]==0)q.push(i);
	while(!q.empty()){
		int x=q.front(); q.pop(); ans.push_back(x);
		for(auto p:a[x])if(--ideg[p]==0)q.push(p);
	}
}

欧拉路径 欧拉回路

dfs树 bfs树

最短路径

Dijkstra

struct node{
	int to; ll dis;
	bool operator<(const node &b)const{
		return dis>b.dis;
	}
};
int n;
bool vis[N];
vector<node> a[N];
void dij(int s,ll dis[]){ //s是起点,dis是结果
	fill(vis,vis+n+1,0);
	fill(dis,dis+n+1,inf); dis[s]=0; //last[s]=-1;
	static priority_queue<node> q; q.push({s,0});
	while(!q.empty()){
		int x=q.top().to; q.pop();
		if(vis[x])continue; vis[x]=1;
		for(auto i:a[x]){
			int p=i.to;
			if(dis[p]>dis[x]+i.dis){
				dis[p]=dis[x]+i.dis;
				q.push({p,dis[p]});
				//last[p]=x; //last可以记录最短路(倒着)
			}
		}
	}
}

Floyd

repeat(k,0,n)
repeat(i,0,n)
repeat(j,0,n)
	f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
//bitset<N> g<N>;
repeat(i,0,n)
repeat(j,0,n)
if(g[j][i])
	g[j]|=g[i];

SPFA

int cnt[N]; bool vis[N]; ll h[N]; //h意思和dis差不多,但是Johnson里需要区分
int n;
struct node{int to; ll dis;};
vector<node> a[N];
bool spfa(int s){ //返回是否有负环(s为起点)
	repeat(i,0,n+1)
		cnt[i]=vis[i]=0,h[i]=inf;
	h[s]=0; //last[s]=-1;
	static deque<int> q; q.assign(1,s);
	while(!q.empty()){
		int x=q.front(); q.pop_front();
		vis[x]=0;
		for(auto i:a[x]){
			int p=i.to;
			if(h[p]>h[x]+i.dis){
				h[p]=h[x]+i.dis;
				//last[p]=x; //last可以记录最短路(倒着)
				if(vis[p])continue;
				vis[p]=1;
				q.push_back(p); //可以SLF优化
				if(++cnt[p]>n)return 1;
			}
		}
	}
	return 0;
}
bool negcycle(){ //返回是否有负环
	a[n].clear();
	repeat(i,0,n)
		a[n].push_back({i,0}); //加超级源点
	return spfa(n);
}

Johnson

ll dis[N][N];
bool jn(){ //返回是否成功
	if(negcycle())return 0;
	repeat(x,0,n)
	for(auto &i:a[x])
		i.dis+=h[x]-h[i.to];
	repeat(x,0,n)dij(x,dis[x]);
	repeat(x,0,n)
	repeat(p,0,n)
	if(dis[x][p]!=inf)
		dis[x][p]+=h[p]-h[x];
	return 1;
}

最小环

//无边权无向图最小环
int dis[N],fa[N],n,ans;
vector<int> a[N];
queue<int> q;
void bfs(int s){ //求经过s的最小环(不一定是简单环)
	fill(dis,dis+n,-1); dis[s]=0;
	q.push(s); fa[s]=-1;
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto p:a[x])
		if(p!=fa[x]){
			if(dis[p]==-1){
				dis[p]=dis[x]+1;
				fa[p]=x;
				q.push(p);
			}
			else ans=min(ans,dis[x]+dis[p]+1);
		}
	}
}
int mincycle(){
	ans=inf;
	repeat(i,0,n)bfs(i); //只要遍历最小环可能经过的点即可
	return ans;
}

最小生成树

Kruskal

DSU d;
struct edge{int u,v,dis;}e[200010];
ll kru(){
	ll ans=0,cnt=0;
	sort(e,e+m);
	repeat(i,0,m){
		int x=d[e[i].u],y=d[e[i].v];
		if(x==y)continue;
		d.join(x,y);
		ans+=e[i].dis;
		cnt++;
		if(cnt==n-1)break;
	}
	if(cnt!=n-1)return -1;
	else return ans;
}

Boruvka

DSU d;
struct edge{int u,v,dis;}e[200010];
ll bor(){
	ll ans=0;
	d.init(n);
	e[m].dis=inf;
	vector<int> b; //记录每个联通块的增广路(名词迷惑行为)
	bool f=1;
	while(f){
		b.assign(n,m);
		repeat(i,0,m){
			int x=d[e[i].u],y=d[e[i].v];
			if(x==y)continue;
			if(e[i].dis<e[b[x]].dis)
				b[x]=i;
			if(e[i].dis<e[b[y]].dis)
				b[y]=i;
		}
		f=0;
		for(auto i:b)
		if(i!=m){
			int x=d[e[i].u],y=d[e[i].v];
			if(x==y)continue;
			ans+=e[i].dis;
			d.join(x,y);
			f=1;
		}
	}
	return ans;
}

最小树形图 | 朱刘算法

int n;
struct edge{int x,y,w;};
vector<edge> eset; //会在solve中被修改
ll solve(int rt){ //返回最小的边权和,返回-1表示没有树形图
	static int fa[N],id[N],top[N],minw[N];
	ll ans=0;
	while(1){
		int cnt=0;
		repeat(i,1,n+1)
			id[i]=top[i]=0,minw[i]=inf;
		for(auto &i:eset) //记录权最小的父亲
		if(i.x!=i.y && i.w<minw[i.y]){
			fa[i.y]=i.x;
			minw[i.y]=i.w;
		}
		minw[rt]=0;
		repeat(i,1,n+1){ //标记所有环
			if(minw[i]==inf)return -1;
			ans+=minw[i];
			for(int x=i;x!=rt && !id[x];x=fa[x])
			if(top[x]==i){
				id[x]=++cnt;
				for(int y=fa[x];y!=x;y=fa[y])
					id[y]=cnt;
				break;
			}
			else top[x]=i;
		}
		if(cnt==0)return ans; //无环退出
		repeat(i,1,n+1)
		if(!id[i])
			id[i]=++cnt;
		for(auto &i:eset){ //缩点
			i.w-=minw[i.y];
			i.x=id[i.x],i.y=id[i.y];
		}
		n=cnt;
		rt=id[rt];
	}
}

树论的一些概念

树的直径

树的重心

最近公共祖先

欧拉序列+st表解法

int n,m;
vector<int> a;
vector<int> e[500010];
bool vis[500010];
int pos[500010],dep[500010];
#define mininarr(a,x,y) (a[x]<a[y]?x:y)
struct RMQ{
	#define logN 21
	int f[N][logN],log[N];
	RMQ(){
		log[1]=0;
		repeat(i,2,N)
			log[i]=log[i/2]+1;
	}
	void build(){
		int n=a.size();
		repeat(i,0,n)
			f[i][0]=a[i];
		repeat(k,1,logN)
		repeat(i,0,n-(1<<k)+1)
			f[i][k]=mininarr(dep,f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
	int query(int l,int r){
		if(l>r)swap(l,r);//!!
		int s=log[r-l+1];
		return mininarr(dep,f[l][s],f[r-(1<<s)+1][s]);
	}
}rmq;
void dfs(int x,int d){
	if(vis[x])return;
	vis[x]=1;
	dep[x]=d;
	a.push_back(x);
	pos[x]=a.size()-1; //记录位置
	repeat(i,0,e[x].size()){
		int p=e[x][i];
		if(vis[p])continue;
		dfs(p,d+1);
		a.push_back(x);
	}
}
int lca(int x,int y){
	return rmq.query(pos[x],pos[y]);
}
//初始化:dfs(s,1); rmq.build();

树链剖分解法

vector<int> e[N];
int dep[N],son[N],sz[N],top[N],fa[N]; //son重儿子,top链顶
void dfs1(int x){ //标注dep,sz,son,fa
	sz[x]=1;
	son[x]=-1;
	dep[x]=dep[fa[x]]+1;
	for(auto p:e[x]){
		if(p==fa[x])continue;
		fa[p]=x; dfs1(p);
		sz[x]+=sz[p];
		if(son[x]==-1 || sz[son[x]]<sz[p])
			son[x]=p;
	}
}
void dfs2(int x,int tv){ //标注top
	top[x]=tv;
	if(son[x]!=-1)dfs2(son[x],tv);
	for(auto p:e[x]){
		if(p==fa[x] || p==son[x])continue;
		dfs2(p,p);
	}
}
void init(int s){ //s是根
	fa[s]=s;
	dfs1(s);
	dfs2(s,s);
}
int lca(int x,int y){
	while(top[x]!=top[y])
		if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
		else y=fa[top[y]];
	return dep[x]<dep[y]?x:y;
}

一些关于lca的问题

int length(int x,int y){ //路径长度
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}

联通性相关

强联通分量scc+缩点

stack<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],co[N],w[N]; //co:染色结果
vector<int> sz; //第i个分量的点数
int dcnt; //时间戳
void dfs(int x){ //Tarjan求强联通分量
	if(vis[x])return; vis[x]=1;
	stk.push(x); instk[x]=1;
	dfn[x]=low[x]=++dcnt;
	for(auto p:a[x]){
		dfs(p);
		if(instk[p])
			low[x]=min(low[x],low[p]);
	}
	if(low[x]==dfn[x]){
		int t; sz.push_back(0); //记录
		do{
			t=stk.top();
			stk.pop();
			instk[t]=0;
			sz.back()+=w[t]; //记录
			co[t]=sz.size()-1; //染色
		}while(t!=x);
	}
}
void shrink(){ //缩点
	set<pii> eset;
	fill(vis,vis+n,0);
	//fill(instk,instk+n,0);
	sz.clear();
	eset.clear();
	dcnt=0;
	repeat(i,0,n)
	if(!vis[i])
		dfs(i);
	repeat(i,0,n)
	for(auto p:a[i])
	if(co[i]!=co[p])
		eset.insert({co[i],co[p]});
	n=sz.size();
	repeat(i,0,n){
		a[i].clear();
		w[i]=sz[i];
	}
	for(auto i:eset){
		a[i.fi].push_back(i.se);
		//a[i.se].push_back(i.fi);
	}
}

割点

bool vis[N],cut[N]; //cut即结果,cut[i]表示i是否为割点
int dfn[N],low[N];
int dcnt; //时间戳
void dfs(int x,bool isroot=1){
	if(vis[x])return; vis[x]=1;
	dfn[x]=low[x]=++dcnt;
	int ch=0; cut[x]=0;
	for(auto p:a[x]){
		if(!vis[p]){
			dfs(p,0);
			low[x]=min(low[x],low[p]);
			if(!isroot && low[p]>=dfn[x])
				cut[x]=1;
			ch++;
		}
		low[x]=min(low[x],dfn[p]);
	}
	if(isroot && ch>=2) //根节点判断方法
		cut[x]=1;
}

2-sat问题

可行解

struct twosat{ //暴力版
	int n;
	vector<int> g[N*2];
	bool mark[N*2]; //mark即结果,表示是否选择了这个点
	int s[N],c;
	bool dfs(int x){
		if(mark[x^1])return 0;
		if(mark[x])return 1;
		mark[s[c++]=x]=1;
		for(auto p:g[x])
		if(!dfs(p))
			return 0;
		return 1;
	}
	void init(int _n){
		n=_n;
		for(int i=0;i<n*2;i++){
			g[i].clear();
			mark[i]=0;
		}
	}
	void add(int x,int y){ //这个函数随题意变化
		g[x].push_back(y^1); //选了x就必须选y^1
		g[y].push_back(x^1); //选了y就必须选x^1
	}
	bool solve(){ //返回是否存在解
		for(int i=0;i<n*2;i+=2)
		if(!mark[i] && !mark[i^1]){
			c=0;
			if(!dfs(i)){
				while(c>0)mark[s[--c]]=0;
				if(!dfs(i^1))return 0;
			}
		}
		return 1;
	}
}ts;

图上的NP问题

最大团+极大团计数

int g[N][N],f[N][N],v[N],Max[N],n,ans; //g[][]是邻接矩阵,n是顶点数
//vector<int> rec,maxrec; //maxrec是最大团
bool dfs(int x,int cur){
	if(cur==0)
		return x>ans;
	repeat(i,0,cur){
		int u=f[x][i],k=0;
		if(Max[u]+x<=ans)return 0;
		repeat(j,i+1,cur)
		if(g[u][f[x][j]])
			f[x+1][k++]=f[x][j];
		//rec.push_back(u);
		if(dfs(x+1,k))return 1;
		//rec.pop_back();
	}
	return 0;
}
void solve(){
	ans=0; //maxrec.clear();
	repeat_back(i,0,n){
		int k=0;
		repeat(j,i+1,n)
		if(g[i][j])
			f[1][k++]=j;
		//rec.clear(); rec.push_back(i);
		if(dfs(1,k)){
			ans++;
			//maxrec=rec;
		}
		Max[i]=ans;
	}
}
int g[N][N],n;
//vector<int> rec; //存当前极大团
int ans,some[N][N],none[N][N]; //some是未搜索的点,none是废除的点
void dfs(int d,int sn,int nn){
	if(sn==0 && nn==0)
		ans++; //此时rec是其中一个极大图
	//if(ans>1000)return; //题目要求_(:зゝ∠)_
	int u=some[d][0];
	for(int i=0;i<sn;++i){
		int v=some[d][i];
		if(g[u][v])continue;
		int tsn=0,tnn=0; 
		for(int j=0;j<sn;++j)
		if(g[v][some[d][j]])
			some[d+1][tsn++]=some[d][j];
		for(int j=0;j<nn;++j)
		if(g[v][none[d][j]])
			none[d+1][tnn++]=none[d][j];
		//rec.push_back(v);
		dfs(d+1,tsn,tnn);
		//rec.pop_back(); 
		some[d][i]=0;
		none[d][nn++]=v;
	}
}
void solve(){ //运行后ans即极大团数
	ans=0;
	for(int i=0;i<n;++i)
		some[0][i]=i+1;
	dfs(0,n,0);
}

最小染色数

int n,m;
int g[N]; //二进制邻接矩阵
bool ind[1<<N]; //是否为(极大)独立集
int dis[1<<N];
vector<int> a; //存独立集
#define np (1<<n)
int bfs(){ //重复覆盖简略版
	fill(dis,dis+np,inf); dis[0]=0;
	auto q=queue<int>(); q.push(0);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto i:a){
			int p=x|i;
			if(p==np-1)return dis[x]+1;
			if(dis[p]>dis[x]+1){
				dis[p]=dis[x]+1;
				q.push(p);
			}
		}
	}
	return 0;
}
int solve(){ //返回最小染色数
	mst(g,0);
	for(auto i:eset){
		int x=i.fi,y=i.se;
		g[x]|=1<<y;
		g[y]|=1<<x;
	}
	//求所有独立集
	ind[0]=1;
	repeat(i,1,np){
		int w=63-__builtin_clzll(ll(i)); //最高位
		if((g[w]&i)==0 && ind[i^(1<<w)])
			ind[i]=1;
	}
	//删除所有不是极大独立集的独立集
	repeat(i,1,np)
	if(ind[i]){
		for(int j=1;j<np;j<<=1)
		if((i&j)==0 && ind[i|j]){
			ind[i]=0;
			break;
		}
		if(ind[i])
			a.push_back(i); //记录极大独立集
	}
	return bfs();
}

弦图+区间图

vector<int> e[N];
int n,rec[N]; //rec[1..n]是结果
int h[N],nxt[N],pre[N],vis[N],lab[N];
void del(int x){
	int w=lab[x];
	if(h[w]==x)h[w]=nxt[x];
	pre[nxt[x]]=pre[x];
	nxt[pre[x]]=nxt[x];
}
void mcs(){
	fill(h,h+n+1,0);
	fill(vis,vis+n+1,0);
	fill(lab,lab+n+1,0);
	iota(nxt,nxt+n+1,1);
	iota(pre,pre+n+1,-1);
	nxt[n]=0;
	h[0]=1;
	int w=0;
	repeat_back(i,1,n+1){
		int x=h[w];
		rec[i]=x;
		del(x);
		vis[x]=1;
		for(auto p:e[x])
		if(!vis[p]){
			del(p);
			lab[p]++;
			nxt[p]=h[lab[p]];
			pre[h[lab[p]]]=p;
			h[lab[p]]=p;
			pre[p]=0;
		}
		w++;
		while(h[w]==0)w--;
	}
}
bool judge(){ //返回是否是完美消除序列(先要跑一遍MCS)
	static int s[N],rnk[N];
	repeat(i,1,n+1){
		rnk[rec[i]]=i;
		sort(e[i].begin(),e[i].end()); //方便二分查找,内存足够直接unmap
	}
	repeat(i,1,n+1){
		int top=0,x=rec[i];
		for(auto p:e[x])
		if(rnk[x]<rnk[p]){
			s[++top]=p;
			if(rnk[s[top]]<rnk[s[1]])
				swap(s[1],s[top]);
		}
		repeat(j,2,top+1)
		if(!binary_search(e[s[1]].begin(),e[s[1]].end(),s[j]))
			return 0;
	}
	return 1;
}
int color(){ //返回最大团点数/最小染色数
	return *max_element(lab+1,lab+n+1)+1;
	/* //以下求最大团
	static int rnk[N];
	repeat(i,1,n+1)rnk[rec[i]]=i;
	int x=max_element(lab+1,lab+n+1)-lab;
	rec2.push_back(x);
	for(auto p:e[x])
	if(rnk[x]<rnk[p])
		rec2.push_back(x);
	*/
}
int maxindset(){ //返回最大独立集点数/最小团覆盖数
	int ans=0;
	fill(vis,vis+n+1,0);
	repeat(i,1,n+1){
		int x=rec[i];
		if(!vis[x]){
			ans++; //rec2.push_back(x); //记录最大独立集
			for(auto p:e[x])
				vis[p]=1;
		}
	}
	return ans;
}
int cliquecnt(){ //返回极大团数 
	static int s[N],fst[N],rnk[N],cnt[N];
	int ans=0;
	repeat(i,1,n+1)rnk[rec[i]]=i;
	repeat(i,1,n+1){
		int top=0,x=rec[i];
		for(auto p:e[x])
		if(rnk[x]<rnk[p]){
			s[++top]=p;
			if(rnk[s[top]]<rnk[s[1]])
				swap(s[1],s[top]);
		}
		fst[x]=s[1]; cnt[x]=top;
	}
	fill(vis,vis+n+1,0);
	repeat(i,1,n+1){
		int x=rec[i];
		if(!vis[x])ans++;
		if(cnt[x]>0 && cnt[x]>=cnt[fst[x]]+1)
			vis[fst[x]]=1;
	}
	return ans;
}

仙人掌 | 圆方树

二分图

二分图的一些概念




最大匹配 | 匈牙利 or 网络流

int n,m; //n个左顶点,m个右顶点
vector<int> a[N]; //左顶点x与右顶点a[x][0..sz]有连接
int dcnt,mch[N],dfn[N]; //mch[p]表示与右顶点p连接的左顶点,dfn[p]==dcnt意味着右顶点p已访问
bool dfs(int x){
	repeat(i,0,a[x].size()){
		int p=a[x][i];
		if(dfn[p]!=dcnt){
			dfn[p]=dcnt;
			if(mch[p]==-1 || dfs(mch[p])){
				mch[p]=x;
				return 1;
			}
		}
	}
	return 0;
}
int hungarian(){ //返回最大匹配数
	int ans=0;
	repeat(i,0,m)mch[i]=dfn[i]=-1; //初始化
	repeat(i,0,n){
		dcnt=i;
		if(dfs(i))ans++;
	}
	return ans;
}
void ae(int x,int y){
	addedge(x,y,1);
	addedge(y,x,0);
}
cin>>n1>>n2>>m; //左顶点数,右顶点数,之间的边数
n=n1+n2+2; //网络顶点数
s=0,t=n1+n2+1; //源点和汇点
init();
repeat(i,1,n1+1)ae(s,i); //构造源点与左顶点的边
repeat(i,n1+1,n1+n2+1)ae(i,t); //构造右顶点与汇点的边
repeat(i,0,m){
	int x,y; cin>>x>>y; x--,y--;
	ae(x+1,n1+y+1); //构造左顶点与右顶点的边
}
cout<<dinic()<<endl;

最大权匹配 | KM

int e[N][N],n,m; //邻接矩阵,左顶点数,右顶点数
int lx[N],ly[N]; //顶标
int mch[N]; //右顶点i连接的左顶点编号
bool fx[N],fy[N]; //是否在增广路上
bool dfs(int i){
	fx[i]=1;
	repeat(j,0,n)
	if(lx[i]+ly[j]==e[i][j] && !fy[j]){
		fy[j]=1;
		if(mch[j]==-1 || dfs(mch[j])){
			mch[j]=i;
			return 1;
		}
	}
	return 0;
}
void update(){
	int fl=inf;
	repeat(i,0,n)if(fx[i])
	repeat(j,0,m)if(!fy[j])
		fl=min(fl,lx[i]+ly[j]-e[i][j]);
	repeat(i,0,n)if(fx[i])lx[i]-=fl;
	repeat(j,0,m)if(fy[j])ly[j]+=fl;
}
int solve(){ //返回匹配数
	repeat(i,0,n){
		mch[i]=-1;
		lx[i]=ly[i]=0;
		repeat(j,0,m)
			lx[i]=max(lx[i],e[i][j]);
	}
	repeat(i,0,n)
	while(1){
		repeat(j,0,m)
			fx[j]=fy[j]=0;
		if(dfs(i))break;
		else update();
	}
	int ans=0;
	repeat(i,0,m)
	if(mch[i]!=-1)
		ans+=e[mch[i]][i];
	return ans;
}

稳定婚姻 | 延迟认可

struct node{
	int s[N]; //s的值给定
		//对男生来说是女生编号排序
		//对女生来说是男生的分数
	int now; //选择的伴侣编号
}a[N],b[N]; //男生,女生
int tr[N]; //男生尝试表白了几次
queue<int> q; //单身狗(男)排队
bool match(int x,int y){ //配对,返回是否成功
	int x0=b[y].now;
	if(x0!=-1){
		if(b[y].s[x]<b[y].s[x0])
			return 0; //分数不够,竞争失败
		q.push(x0);
	}
	a[x].now=y;
	b[y].now=x;
	return 1;
}
void stable_marriage(){ //运行后a[].now,b[].now即结果
	q=queue<int>();
	repeat(i,0,n){
		b[i].now=-1;
		q.push(i);
		tr[i]=0;
	}
	while(!q.empty()){
		int x=q.front(); q.pop();
		int y=a[x].s[tr[x]++]; //下一个最中意女生
		if(!match(x,y))
			q.push(x); //下次努力
	}
}

网络流

网络流的一些概念





最大流 | Dinic or ISAP

struct edge{int to,w,nxt;}; //指向,限流,下一条边
vector<edge> a;
int head[N],cur[N];
void addedge(int x,int y,int w){
	a.push_back((edge){y,w,head[x]});
	head[x]=a.size()-1;
}
int n,m,s,t; //点数,边数,源点,汇点
queue<int> q;
bool inque[N]; //在队里的不需要入队
int dep[N]; //深度
bool bfs(){ //记录深度
	fill(dep,dep+n,inf); dep[s]=0;
	copy(head,head+n,cur); //当前弧初始化
	q=queue<int>(); q.push(s);
	while(!q.empty()){
		int x=q.front(); q.pop();
		inque[x]=0;
		for(int i=head[x];i!=-1;i=a[i].nxt){
			int p=a[i].to;
			if(dep[p]>dep[x]+1 && a[i].w){
				dep[p]=dep[x]+1;
				if(inque[p]==0){
					inque[p]=1;
					q.push(p);
				}
			}
		}
	}
	return dep[t]!=inf;
}
int dfs(int x,int flow){
	int now,ans=0;
	if(x==t)return flow;
	for(int i=cur[x];i!=-1;i=a[i].nxt){ //当前弧开始(可以不重复访问废边)
		cur[x]=i; //记录当前弧
		int p=a[i].to;
		if(a[i].w && dep[p]==dep[x]+1)
		if((now=dfs(p,min(flow,a[i].w)))){
			a[i].w-=now;
			a[i^1].w+=now;
			ans+=now,flow-=now; //流量更新
			if(flow==0)break;
		}
	}
	return ans;
}
void init(int n){ //初始化
	a.clear();
	fill(head,head+n,-1);
	fill(inque,inque+n,0);
}
int solve(){ //返回最大流
	int ans=0;
	while(bfs())
		ans+=dfs(s,inf);
	return ans;
}
#define add(x,y,w) addedge(x,y,w),addedge(y,x,0)
//赋值n,再init(n),再添边和s,t赋值,最后solve()
struct FLOW{ //ISAP最大流
	struct edge{int to,w,nxt;}; //指向,限流,下一条边
	vector<edge> a; int head[N]; //前向星 
	int cur[N]; //当前弧 
	int n,s,t; //点数,源点,汇点
	queue<int> q;
	int dep[N],gap[N]; //gap[x]为等于x的dep[i]的个数
	void ae(int x,int y,int w){
		a.push_back((edge){y,w,head[x]});
		head[x]=a.size()-1;
	}
	bool bfs(){ //记录dep和gap
		fill(dep,dep+n,-1); dep[t]=0;
		fill(gap,gap+n,0); gap[0]=1;
		q.push(t);
		while(!q.empty()){
			int x=q.front(); q.pop();
			for(int i=head[x];i!=-1;i=a[i].nxt){
				int p=a[i].to;
				if(dep[p]!=-1)continue;
				dep[p]=dep[x]+1;
				q.push(p);
				gap[dep[p]]++;
			}
		}
		return dep[s]!=-1;
	}
	int dfs(int x,int fl){ //多路增广
		int now,ans=0;
		if(x==t)return fl;
		for(int i=cur[x];i!=-1;i=a[i].nxt){ //当前弧开始(可以不重复访问废边)
			cur[x]=i; //记录当前弧
			int p=a[i].to;
			if(a[i].w && dep[p]+1==dep[x])
			if((now=dfs(p,min(fl,a[i].w)))){
				a[i].w-=now;
				a[i^1].w+=now;
				ans+=now,fl-=now; //流量更新
				if(fl==0)return ans;
			}
		}
		gap[dep[x]]--;
		if(gap[dep[x]]==0)dep[s]=n;
		dep[x]++;
		gap[dep[x]]++;
		return ans;
	}
	void init(int _n){ //初始化
		n=_n+1;
		a.clear();
		fill(head,head+n,-1);
	}
	int solve(int _s,int _t){ //返回最大流
		s=_s,t=_t;
		int ans=0;
		if(bfs())
		while(dep[s]<n){
			copy(head,head+n,cur); //当前弧初始化
			ans+=dfs(s,inf);
		}
		return ans;
	}
}flow;
#define add(x,y,w) flow.ae(x,y,w),flow.ae(y,x,0)
//先flow.init(n),再add添边,最后flow.solve(s,t)

最小费用最大流 | MCMF

struct FLOW{ //MCMF费用流
	struct edge{int to,w,cost,nxt;}; //指向,限流,费用,下一条边
	vector<edge> a; int head[N]; //前向星 
	int n,s,t,totcost; //点数,源点,汇点,总费用
	deque<int> q;
	bool inque[N]; //在队里的不需要入队
	int dis[N]; //费用
	struct{int to,e;}pre[N]; //路径的前一个点,这条边的位置
	void ae(int x,int y,int w,int cost){
		a.push_back((edge){y,w,cost,head[x]});
		head[x]=a.size()-1;
	}
	bool spfa(){ //已死的算法
		fill(dis,dis+n,inf); dis[s]=0;
		q.assign(1,s);
		while(!q.empty()){
			int x=q.front(); q.pop_front();
			inque[x]=0;
			for(int i=head[x];i!=-1;i=a[i].nxt){
				int p=a[i].to;
				if(dis[p]>dis[x]+a[i].cost && a[i].w){
					dis[p]=dis[x]+a[i].cost;
					pre[p]={x,i};
					if(inque[p]==0){
						inque[p]=1;
						if(!q.empty()
						&& dis[q.front()]<=dis[p])
							q.push_back(p);
						else q.push_front(p);
						//松弛,或者直接q.push_back(p);
					}
				}
			}
		}
		return dis[t]!=inf;
	}
	void init(int _n){ //初始化
		n=_n+1;
		a.clear();
		fill(head,head+n,-1);
		fill(inque,inque+n,0);
	}
	int solve(int _s,int _t){ //返回最大流,费用存totcost里 
		s=_s,t=_t;
		int ans=0;
		totcost=0;
		while(spfa()){
			int fl=inf;
			for(int i=t;i!=s;i=pre[i].to)
				fl=min(fl,a[pre[i].e].w);
			for(int i=t;i!=s;i=pre[i].to){
				a[pre[i].e].w-=fl;
				a[pre[i].e^1].w+=fl;
			}
			totcost+=dis[t]*fl;
			ans+=fl;
		}
		return ans;
	}
}flow;
#define add(x,y,w,cost) flow.ae(x,y,w,cost),flow.ae(y,x,0,-cost)
//先flow.init(n),再add添边,最后flow.solve(s,t)

图论杂项

矩阵树定理

无向图矩阵树定理

void matrix::addedge(int x,int y){
	a[x][y]--,a[y][x]--;
	a[x][x]++,a[y][y]++;
}
lf matrix::treecount(){
	//for(auto i:eset)addedge(i.fi,i.se); //加边
	n--,m=n; //a[n-1][n-1]的余子式(选任一节点均可)
	return get_det();
}

有向图矩阵树定理

void matrix::addedge(int x,int y){
	a[x][y]--;
	a[x][x]++; //叶向树形图改成a[y][y]++;
}
ll matrix::treecount(){
	//for(auto i:eset)addedge(i.fi,i.se); //加边
	repeat(i,s,n) //s是根节点
	repeat(j,0,n)
		a[i][j]=a[i+1][j];
	repeat(i,0,n)
	repeat(j,s,n)
		a[i][j]=a[i][j+1];
	n--,m=n; //a[s][s]的余子式
	return get_det();
}

BSET定理

Prufer序列

LGV引理

others of 图论杂项

Havel-Hakimi定理

无向图三元环计数

字符串

字符串hash

const int hashxor=rnd()%1000000000; //如果不是cf可以不用hashxor
struct Hash{
	vector<ll> a[2],p[2];
	const ll b=257,m[2]={1000000007,998244353};
	Hash(){repeat(i,0,2)a[i]={0},p[i]={1};}
	void push(const string &s){
		repeat(i,0,2)
		for(auto c:s){
			a[i]+=(a[i].back()*b+(c^hashxor))%m[i];
			p[i]+=p[i].back()*b%m[i];
		}
	}
	pair<ll,ll> get(int l,int r){
		#define q(i) (a[i][r+1]-a[i][l]*p[i][r-l+1]%m[i]+m[i])%m[i]
		return {q(0),q(1)};
	}
	int size(){return a[0].size()-1;}
	pair<ll,ll> prefix(int len){return get(0,len-1);}
	pair<ll,ll> suffix(int len){return get(size()-len,size()-1);}
}h;

线型自动机

前缀数组×kmp自动机

int p[N];
void kmp(const string &s){ //求s的前缀函数
	p[0]=0; int k=0;
	repeat(i,1,s.length()){
		while(k>0 && s[i]!=s[k])k=p[k-1];
		if(s[i]==s[k])k++;
		p[i]=k;
	}
}
void solve(string s1,string s2){ //模拟s1.find(s2)
	kmp(s2+'#'+s1);
	repeat(i,s2.size()+1,s.size())
	if(p[i]==(int)s2.size())
		ans.push_back(i-2*s2.size()); //编号从0开始的左端点
}
struct KMP{ //kmp自动机
	string s; int k;
	vector<int> p;
	int get(char c){
		while(k>0 && c!=s[k])k=p[k-1];
		if(c==s[k])k++;
		return k;
	}
	KMP(const string &_s){
		p.push_back(k=0);
		s=_s+'#'; repeat(i,1,s.size())p+=get(s[i]);
	}
	int size(){return s.size()-1;}
};
void solve(string s1,string s2){ //模拟s1.find(s2)
	KMP kmp(s2);
	repeat(i,0,s1.size())
	if(kmp.get(s1[i])==kmp.size())
		ans.push_back(i+1-kmp.size()); //编号从0开始的左端点
	kmp.k=0; //清空(如果下次还要用的话)
}

z函数×exkmp

int z[N];
void exkmp(const string &s){ //求s的z函数
	fill(z,z+s.size(),0); int l=0,r=0;
	repeat(i,1,s.size()){
		if(i<=r)z[i]=min(r-i+1,z[i-l]);
		while(i+z[i]<(int)s.size() && s[z[i]]==s[i+z[i]])z[i]++;
		if(i+z[i]-1>r)l=i,r=i+z[i]-1;
	}
}

马拉车×Manacher

int len[N*2]; char s[N*2]; //两倍内存
int manacher(char s1[]){ //s1可以是s 
	int n=strlen(s1)*2+1;
	repeat_back(i,0,n)s[i+1]=(i%2==0?'*':s1[i/2]);
	n++; s[0]='#'; s[n++]=0;
	len[0]=0;
	int mx=0,id=0,ans=0;
	repeat(i,1,n-1){
		if(i<mx)len[i]=min(mx-i,len[2*id-i]);
		else len[i]=1;
		while(s[i-len[i]]==s[i+len[i]])len[i]++;
		if(len[i]+i>mx)mx=len[i]+i,id=i;
		ans=max(ans,len[i]-1); //最长回文串长度
	}
	return ans;
}

最小表示法

int minstr(const string &s){
	int k=0,i=0,j=1,n=s.size();
	while(max(k,max(i,j))<n){
		if(s[(i+k)%n]==s[(j+k)%n])k++;
		else{
			s[(i+k)%n]>s[(j+k)%n]?i+=k+1:j+=k+1;
			if(i==j)i++;
			k=0;
		}
	}
	return min(i,j);
}

树型自动机

字典树

struct trie{
	int a[N][26],cnt[N],t;
	void init(){
		t=0; add();
	}
	int add(){
		mst(a[t],0);
		cnt[t]=0;
		return t++;
	}
	void insert(const char s[]){
		int k=0;
		for(int i=0;s[i];i++){
			int c=s[i]-'a'; //小写字母
			if(!a[k][c])a[k][c]=add();
			k=a[k][c];
			//son[k]++; //如果要记录子树大小
		}
		cnt[k]++;
	}
	int query(const char s[]){
		int k=0;
		for(int i=0;s[i];i++){
			int c=s[i]-'a'; //小写字母
			if(!a[k][c])return 0;
			k=a[k][c];
		}
		return cnt[k];
	}
}t;

AC自动机

struct AC{
	static const int sigma=26;
	int a[N][sigma],cnt[N],fail[N],t;
	void init(){
		t=0; add();
	}
	int add(){
		mst(a[t],0);
		cnt[t]=0;
		fail[t]=0;
		return t++;
	}
	void insert(const char s[]){
		int k=0;
		for(int i=0;s[i];i++){
			int c=s[i]-'a'; //小写字母
			if(!a[k][c])a[k][c]=add();
			k=a[k][c];
		}
		cnt[k]++;
	}
	queue<int> q;
	void build(){
		repeat(i,0,sigma)
		if(a[0][i])
			q.push(a[0][i]);
		while(q.size()){
			int k=q.front();
			q.pop();
			repeat(i,0,sigma)
			if(a[k][i])
				fail[a[k][i]]=a[fail[k]][i],q.push(a[k][i]);
			else
				a[k][i]=a[fail[k]][i];
		}
	}
	int query(const char s[]){
		int k=0,ans=0;
		for(int i=0;s[i];i++){
			int c=s[i]-'a'; //小写字母
			k=a[k][c];
			for(int j=k;j && cnt[j]!=-1;j=fail[j]){
				ans+=cnt[j];
				cnt[j]=-1;
			}
		}
		return ans;
	}
}tr;

杂项

位运算

位运算巨佬操作

位运算函数

__builtin_ctz(x),__builtin_ctzll(x) //返回x后导0的个数,x是0则返回32 or 64
__builtin_clz(x),__builtin_clzll(x) //返回x前导0的个数,x是0则返回32 or 64
__builtin_popcount(x),__builtin_popcountll(x) //返回x中1的个数
__builtin_parity(x),__builtin_parityll(x) //返回x中1的个数是否为奇数

枚举二进制子集

for(int s=m;s;s=(s-1)&m){
	work(s);
}
int s=(1<<k)-1;
while(s<(1<<n)){
	work(s);
	int x=s&-s,y=s+x;
	s=((s&~y)/x>>1)|y; //这里有一个位反~
}

浮点数

浮点数误差分析

const lf err=1e-11;
if(fabs(x)<err)x=fabs(x); //输出浮点数的预处理

浮点数常量

float 1e38, 有效数字6
double 1e308, 有效数字15
long double 1e4932, 有效数字18

常数优化

估计函数用时

- 整数加减:1(个时间单位,下同)
- 整数位运算:1
- 整数乘法:2
- 整数除法:21
- 浮点加减:3
- 浮点除法:35
- 浮点开根:60

快读快写

ll read(){
	ll x=0,tag=1; char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')tag=-1;
	for(; isdigit(c);c=getchar())x=x*10+c-48;
	return x*tag;
}
void write(ll x){ //可能不比printf快
	if(x<0)x=-x,putchar('-');
	if(x>=10)write(x/10);
	putchar(x%10^48);
}
char getc(){ //代替getchar,用了这个就不能用其他读入函数如scanf
    static char now[1<<16],*S,*T;
    if(T==S){T=(S=now)+fread(now,1,1<<16,stdin); if(T==S)return EOF;}
	return *S++;
}

STL手写内存分配器

static char space[10000000],*sp=space;
template<typename T>
struct allc:allocator<T>{
	allc(){}
	template<typename U>
	allc(const allc<U> &a){}
	template<typename U>
	allc<T>& operator=(const allc<U> &a){return *this;}
	template<typename U>
	struct rebind{typedef allc<U> other;};
	T* allocate(size_t n){
		T *res=(T*)sp;
		sp+=n*sizeof(T);
		return res;
	}
	void deallocate(T* p,size_t n){}
};
vector< int,allc<int> > a;

其他优化

//(都是听说的)
1ll*a 比 (ll)a 快
取模:x%mod 优化为 x<mod?x:x%mod
减少浮点除法:a/b+c/d 优化为 (a*d+b*c)/(b*d)
精度足够时用ll代替浮点类型
三目运算符替代if语句
多路并行运算,如 (a+b)+(c+d) 比 ((a+b)+c)+d 快
加上register和inline,以及强制内联__inline __attribute__((always_inline))
多重for循环时,修改for的顺序保证内存连续访问
多使用局部变量

在TLE边缘试探

while(clock()<0.9*CLOCKS_PER_SEC){
	//反复更新最优解
}

对拍

#include <stdio.h>
#include <stdlib.h>
int main(){
	//For Windows
	//对拍时不开文件输入输出
	//当然,这段程序也可以改写成批处理的形式
	while(1){
		system("gen > test.in"); //数据生成器将生成数据写入输入文件
		system("test1.exe < test.in > a.out"); //获取程序1输出
		system("test2.exe < test.in > b.out"); //获取程序2输出
		if(system("fc a.out b.out")){
			//该行语句比对输入输出
			//fc返回0时表示输出一致,否则表示有不同处
			system("pause"); //方便查看不同处
			return 0;
			//该输入数据已经存放在test.in文件中,可以直接利用进行调试
		}
	}
}

战术分析

我真的真的真的太南了

ll t; 1<<t返回int,必须是1ll<<t
int x; x<<y的y会先对32取模
operator<的比较内容一定要写完整
试一试输入^Z能否结束
无向图输入要给两个值赋值g[x][y]=g[x][y]=1
多组输入时,图记得初始化
建模的转换函数的宏定义一定要加括号,或者写成函数
图论用forward_list吧,贼好用,deque可以用list替代(近期研究发现,list等要手写内存池才能巨快qwq)
多用相空间角度思考问题
内存比我想象的要大一些(有时候1e7可以塞下)
在64位编译器(我的编译器)中set每个元素需要额外32字节内存

数学

数论

基本操作

模乘 模幂 模逆 扩欧

ll mul(ll a,ll b,ll m=mod){return a*b%m;} //模乘
ll qpow(ll a,ll b,ll m=mod){ //快速幂
	ll ans=1;
	for(;b;a=mul(a,a,m),b>>=1)
		if(b&1)ans=mul(ans,a,m);
	return ans;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ //扩欧,ax+by=gcd(a,b),d存gcd
	if(!b)d=a,x=1,y=0;
	else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}
ll gcdinv(ll v,ll m=mod){ //扩欧版逆元
	ll d,x,y;
	exgcd(v,m,d,x,y);
	return (x%m+m)%m;
}
ll getinv(ll v,ll m=mod){ //快速幂版逆元,m必须是质数!!
	return qpow(v,m-2,m);
}
ll qpows(ll a,ll b,ll m=mod){
	if(b>=0)return qpow(a,b,m);
	else return getinv(qpow(a,-b,m),m);
}

防爆模乘

//int128版本
ll mul(ll a,ll b,ll m=mod){return (__int128)a*b%m;}
//llf版本(欲防爆,先自爆)(注意在测试的时候不知道为什么有锅)
ll mul(ll a,ll b,ll m=mod){return (a*b-ll((llf)a/m*b)*m+m)%m;}
//每位运算一次版本,注意这是真·龟速乘,O(logn)
ll mul(ll a,ll b,ll m=mod){
	ll ans=0;
	while(b){
		if(b&1)ans=(ans+a)%m;
		a=(a+a)%m;
		b>>=1;
	}
	return ans;
}
//把b分成两部分版本,要保证m小于1<<42(约等于4e12),a,b<m
ll mul(ll a,ll b,ll m=mod){
	a%=m,b%=m;
	ll l=a*(b>>21)%m*(1ll<<21)%m;
	ll r=a*(b&(1ll<<21)-1)%m;
	return (l+r)%m;
}

最大公约数

__gcd(a,b) //内置gcd,推荐
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} //不推荐233,比内置gcd慢
ll gcd(ll a,ll b){ //卡常gcd来了!!
	#define tz __builtin_ctzll
	if(!a || !b)return a|b;
	int t=tz(a|b);
	a>>=tz(a);
	while(b){
		b>>=tz(b);
		if(a>b)swap(a,b);
		b-=a;
	}
	return a<<t;
	#undef tz
}
lf fgcd(lf a,lf b){return fabs(b)<1e-5?a:fgcd(b,fmod(a,b));}

高级模操作

同余方程组 | CRT+extra

//CRT,m[i]两两互质
ll crt(ll a[],ll m[],int n){ //ans%m[i]==a[i]
	repeat(i,0,n)a[i]%=m[i];
	ll M=1,ans=0;
	repeat(i,0,n)
		M*=m[i];
	repeat(i,0,n){
		ll k=M/m[i],t=gcdinv(k%m[i],m[i]); //扩欧!!
		ans=(ans+a[i]*k*t)%M; //两个乘号可能都要mul
	}
	return (ans+M)%M;
}
//exCRT,m[i]不需要两两互质,基于扩欧exgcd和龟速乘mul
ll excrt(ll a[],ll m[],int n){ //ans%m[i]==a[i]
	repeat(i,0,n)a[i]%=m[i]; //根据情况做适当修改
	ll M=m[0],ans=a[0],g,x,y; //M是m[0..i]的最小公倍数
	repeat(i,1,n){
		ll c=((a[i]-ans)%m[i]+m[i])%m[i];
		exgcd(M,m[i],g,x,y); //Ax=c(mod B)
		if(c%g)return -1;
		ans+=mul(x,c/g,m[i]/g)*M; //龟速乘
		M*=m[i]/g;
		ans=(ans%M+M)%M;
	}
	return (ans+M)%M;
}

离散对数 | BSGS+extra

//BSGS,a和mod互质
ll bsgs(ll a,ll b,ll mod){ //a^ans%mod==b
	a%=mod,b%=mod;
	static unordered_map<ll,ll> m; m.clear();
	ll t=(ll)sqrt(mod)+1,p=1;
	repeat(i,0,t){
		m[mul(b,p,mod)]=i; //p==a^i
		p=mul(p,a,mod);
	}
	a=p; p=1;
	repeat(i,0,t+1){
		if(m.count(p)){ //p==a^i
			ll ans=t*i-m[p];
			if(ans>0)return ans;
		}
		p=mul(p,a,mod);
	}
	return -1;
}
//exBSGS,a和mod不需要互质,基于BSGS
ll exbsgs(ll a,ll b,ll mod){ //a^ans%mod==b
	a%=mod,b%=mod;
	if(b==1)return 0;
	ll ans=0,c=1,g;
	while((g=__gcd(a,mod))!=1){
		if(b%g!=0)return -1;
		b/=g,mod/=g;
		c=mul(c,a/g,mod);
		ans++;
		if(b==c)return ans;
	}
	ll t=bsgs(a,mul(b,getinv(c,mod),mod),mod); //必须扩欧逆元!!
	if(t==-1)return -1;
	return t+ans;
}

阶与原根

ll getG(ll n){ //求n最小的原根
	static vector<ll> a; a.clear();
	ll t=0,k=n-1;
	repeat(i,2,sqrt(k+1)+1)
	if(k%i==0){
		a.push_back(i); //a存放(n-1)的质因数
		while(k%i==0)k/=i;
	}
	if(k!=1)a.push_back(k);
	repeat(i,2,n){ //枚举答案
		bool f=1;
		for(auto j:a)
		if(qpow(i,(n-1)/j,n)==1){
			f=0;
			break;
		}
		if(f)return i;
	}
}

N次剩余

//只求一个
ll residue(ll a,ll b,ll mod){ //ans^a%mod==b
	ll g=getG(mod),c=bsgs(qpow(g,a,mod),b,mod);
	if(c==-1)return -1;
	return qpow(g,c,mod);
}
//求所有N次剩余
vector<ll> ans;
void allresidue(ll a,ll b,ll mod){ //ans^a%mod==b
	ll g=getG(mod),c=bsgs(qpow(g,a,mod),b,mod);
	ans.clear();
	if(b==0){ans.push_back(0);return;}
	if(c==-1)return;
	ll now=qpow(g,c,mod);
	ll step=(mod-1)/__gcd(a,mod-1);
	ll ps=qpow(g,step,mod);
	for(ll i=c%step;i<mod-1;i+=step,now=mul(now,ps,mod))
		ans.push_back(now);
	sort(ans.begin(),ans.end());
}

数论函数的生成

单个欧拉函数

int euler_phi(int n){
	int ans=n;
	repeat(i,2,sqrt(n)+2)
	if(n%i==0){
		while(n%i==0)n/=i;
		ans=ans/i*(i-1);
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}

线性递推乘法逆元

求1..(n-1)的逆元,\(O(n)\)

void get_inv(int n,int m=mod){
	inv[1]=1;
	repeat(i,2,n)
		inv[i]=m-m/i*inv[m%i]%m;
}

求a[1..n]的逆元,离线,\(O(n)\)

void get_inv(int a[],int n){ //求a[1..n]的逆元,存在inv[1..n]中
	static int pre[N];
	pre[0]=1;
	repeat(i,1,n+1)
		pre[i]=(ll)pre[i-1]*a[i]%mod;
	int inv_pre=qpow(pre[n],mod-2);
	repeat_back(i,1,n+1){
		inv[i]=(ll)pre[i-1]*inv_pre%mod;
		inv_pre=(ll)inv_pre*a[i]%mod;
	}
}

线性筛

筛素数
//a[i]表示第i+1个质数,vis[i]==0表示i是素数
void get_prime(){
	int cnt=0; vis[1]=1;
	repeat(i,2,n+1){
		if(!vis[i]) //是个质数
			a[cnt++]=i; //记录质数
		repeat(j,0,cnt){
			if(i*a[j]>n)break;
			vis[i*a[j]]=1;
			if(i%a[j]==0)break; //此时a[j]是i的最小质因数
		}
	}
}
筛欧拉函数
void get_phi(){
	int cnt=0; /*vis[1]=1;*/ phi[1]=1;
	repeat(i,2,n+1){
		if(!vis[i])
			a[cnt++]=i,phi[i]=i-1;
		repeat(j,0,cnt){
			if(i*a[j]>n)break;
			vis[i*a[j]]=1;
			if(i%a[j]==0){
				phi[i*a[j]]=phi[i]*a[j];
				break;
			}
			phi[i*a[j]]=phi[i]*(a[j]-1);
		}
	}
}
void get_phi(){
	phi[1]=1; //其他的值初始化为0
	repeat(i,2,n+1)
	if(!phi[i])
	for(int j=i;j<=n;j+=i){
		if(!phi[j])phi[j]=j;
		phi[j]=phi[j]/i*(i-1);
	}
}
筛莫比乌斯函数
void get_mu(int n){
	int cnt=0; /*vis[1]=1;*/ mu[1]=1;
	repeat(i,2,n+1){
		if(!vis[i])
			a[cnt++]=i,mu[i]=-1;
		repeat(j,0,cnt){
			if(i*a[j]>n)break;
			vis[i*a[j]]=1;
			if(i%a[j]==0){
				mu[i*a[j]]=0;
				break;
			}
			mu[i*a[j]]=-mu[i];
		}
	}
}

杜教筛

struct DU{
	static const int N=2000010;
	map<ll,ll> mp_mu;
	int sum_mu[N],a[N],mu[N];
	bool vis[N];
	ll S_mu(ll x){ //求mu的前缀和
		if(x<N)return sum_mu[x];
		if(mp_mu[x])return mp_mu[x];
		ll ret=1;
		for(ll i=2,j;i<=x;i=j+1){
			j=x/(x/i);
			ret-=S_mu(x/i)*(j-i+1);
		}
		return mp_mu[x]=ret;
	}
	void init(){
		int cnt=0; /*vis[1]=1;*/ mu[1]=1;
		repeat(i,2,N){
			if(!vis[i])
				a[cnt++]=i,mu[i]=-1;
			repeat(j,0,cnt){
				if(i*a[j]>=N)break;
				vis[i*a[j]]=1;
				if(i%a[j]==0){
					mu[i*a[j]]=0;
					break;
				}
				mu[i*a[j]]=-mu[i];
			}
		}
		repeat(i,1,N)
			sum_mu[i]=sum_mu[i-1]+mu[i];
	}
}du;

素数约数相关

唯一分解

void fac(int a[],ll n){
	repeat(i,2,(int)sqrt(n)+2)
	while(n%i==0)
		a[i]++,n/=i;
	if(n>1)a[n]++;
}
struct fac{
	#define facN 1010
	ll a[facN]; set<ll> s;
	fac(){mst(a,0); s.clear();}
	void lcm(ll n){ //self=lcm(self,n)
		repeat(i,2,facN)
		if(n%i==0){
			int cnt=0;
			while(n%i==0)
				cnt++,n/=i;
			a[i]=max(a[i],cnt); //改成a[i]+=cnt就变成了乘法
		}
		if(n>1)s.insert(n);
	}
	ll value(){ //求自己的模意义下的值
		ll ans=1;
		repeat(i,2,facN)
		if(a[i])
			ans=ans*qpow(i,a[i],mod)%mod;
		for(auto i:s)
			ans=ans*i%mod;
		return ans;
	}
}f;

素数判定 | 朴素 or Miller-Rabin

bool isprime(int n){
	if(n<=3)return n>=2;
	if(n%2==0 || n%3==0)return 0;
	repeat(i,1,int(sqrt(n)+1.5)/6+1)
		if(n%(i*6-1)==0 || n%(i*6+1)==0)return 0;
	return 1;
}
bool isprime(ll n){
	if(n<4)return n>1;
	ll a=n-1,b=0;
	while(a%2==0)a/=2,++b;
	repeat(i,0,10){
		ll x=rnd()%(n-2)+2,v=qpow(x,a,n);
		if(v==1 || v==n-1)continue;
		repeat(j,0,b+1){
			v=mul(v,v,n); //mul要防爆
			if(v==n-1)break;
		}
		if(v!=n-1)return 0;
	}
	return 1;
}

大数分解 | Pollard-rho

ll pollard_rho(ll c,ll n){
	ll i=1,x,y,k=2,d;
	x=y=rnd()%n;
	while(1){
		d=__gcd(n+y-x,n);
		if(d>1 && d<n)
			return d;
		if(++i==k)y=x,k*=2;
		x=(mul(x,x,n)+n-c)%n; //mul要防爆
		if(y==x)return n;
	}
}
vector<ll> ans; //存结果(质因数,无序)
void rho(ll n){ //分解n
	if(isprime(n)){
		ans.push_back(n);
		return;
	}
	ll t;
	do{t=pollard_rho(rnd()%(n-1)+1,n);}while(t>=n);
	rho(t);
	rho(n/t);
}

单个约数个数函数

int get_divisor(int n){ //求约数个数
	int ans=0;
	for(int i=1;i<n;i=n/(n/(i+1)))
	if(n%i==0)
		ans++; //v.push_back(i); //记录约数
	return ans+1; //v.push_back(n); //记录约数
}

反素数生成

int pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll n; //范围
pair<ll,ll> ans; //ans是结果,ans.fi是最大反素数,ans.se是反素数约数个数
void dfs(ll num=1,ll cnt=1,int *p=pri,int pre=inf){ //注意ans要初始化
	if(make_pair(cnt,-num)>make_pair(ans.se,-ans.fi))
		ans={num,cnt};
	num*=*p;
	for(int i=1;i<=pre && num<=n;i++,num*=*p)
		dfs(num,p+1,i,cnt*(i+1));
}

\(n\) 以内约数个数最大值是 \(O(n^{\tfrac {1.066}{\ln\ln n}})\)

范围 1e4 1e5 1e6 1e9 1e16
最大反素数 7560 83160 720720 735134400 8086598962041600
反素数约数个数 64 128 240 1344 41472

数论杂项

数论分块

\(n=(k-n\%k)(n/k)+(n\%k)(n/k+1)\)
\(\lfloor \dfrac{n}{x}\rfloor=C\)\([x_{\min},x_{\max}]\) 作为一块,其中区间内的任一整数 \(x_0\) 满足 \(x_{\max}=n/(n/x_0)\)

for(int l=l0,r;l<=r0;l=r+1){
	r=min(r0,n/(n/l));
	//c=n/l;
	//len=l-r+1;
}

\(\lceil \dfrac{n}{x}\rceil=C\)\([x_{\min},x_{\max}]\) 作为一块:

for(int l=l0,r;l<=r0;l=r+1){
	r=min(r0,n/(n/l)); if(n%r==0)r=max(r-1,l);
	//c=(n+l-1)/l;
	//len=l-r+1;
}

二次剩余

莫比乌斯反演

斐波那契数列

快速倍增法求\(F_n\),返回二元组\((F_n,F_{n+1})\)\(O(\log n)\)

pii fib(ll n){ //fib(n).fi即结果
	if(n==0)return {0,1};
	pii p=fib(n>>1);
	ll a=p.fi,b=p.se;
	ll c=a*(2*b-a)%mod;
	ll d=(a*a+b*b)%mod;
	if(n&1)return {d,(c+d)%mod};
	else return {c,d};
}

组合数学

组合数取模 | Lucas+extra

Lucas定理用来求模意义下的组合数

真·Lucas,\(p\) 是质数(后面的exLucas都不纯正

ll lucas(ll a,ll b,ll p){ //a>=b
	if(b==0)return 1;
	return mul(c(a%p,b%p,p),lucas(a/p,b/p,p),p);
}

特例:如果p=2,可能lucas失效(?)

ll C(ll a,ll b){ //a>=b,p=2的情况
	return (a&b)==b;
}

快速阶乘和exLucas

struct Qfac{
	ll s[2000010];
	ll p,m;
	ll A(ll x){ //快速阶乘的A值
		if(x==0)return 1;
		ll c=A(x/p);
		return s[x%m]*qpow(s[m],x/m,m)%m*c%m;
	}
	ll B(ll x){ //快速阶乘的B值
		int ans=0;
		for(ll i=x;i;i/=p)ans+=i/p;
		return ans;
	}
	ll C(ll a,ll b){ //组合数,a>=b
		ll k=B(a)-B(b)-B(a-b);
		return A(a)*gcdinv(A(b),m)%m
			*gcdinv(A(a-b),m)%m
			*qpow(p,k,m)%m;
	}
	void init(ll _p,ll _m){ //初始化,一定要满足m=p^k
		p=_p,m=_m;
		s[0]=1;
		repeat(i,1,m+1)
			if(i%p)s[i]=s[i-1]*i%m;
			else s[i]=s[i-1];
	}
}qfac;
ll exlucas(ll a,ll b,ll mod){
	ll ans=0,m=mod;
	for(ll i=2;i<=m;i++) //不能repeat
	if(m%i==0){
		ll p=i,k=1;
		while(m%i==0)m/=i,k*=i;
		qfac.init(p,k);
		ans=(ans+qfac.C(a,b)*(mod/k)%mod*gcdinv(mod/k,k)%mod)%mod;
	}
	return (ans+mod)%mod;
}

线性递推组合数

struct CC{
	static const int N=100010;
	ll fac[N],inv[N];
	CC(){
		fac[0]=1;
		repeat(i,1,N)fac[i]=fac[i-1]*i%mod;
		inv[N-1]=qpow(fac[N-1],mod-2,mod);
		repeat_back(i,0,N-1)inv[i]=inv[i+1]*(i+1)%mod;
	}
	ll operator()(ll a,ll b){ //a>=b
		if(a<b)return 0;
		return fac[a]*inv[a-b]%mod*inv[b]%mod;
	}
}C;

线性递推二项式系数

组合数学函数

B[0]=B[1]=1;
repeat(i,2,N){
	B[i]=0;
	repeat(j,0,i)
		B[i]=(B[i]+C(i-1,j)*B[j]%mod)%mod;
}

第一类Stirling数

第二类Stirling数

康托展开+逆 编码与解码

康托展开+逆

//普通版,O(n^2)
int cantor(int a[],int n){
	int f=1,ans=1; //假设答案最小值是1
	repeat_back(i,0,n){
		int cnt=0;
		repeat(j,i+1,n)
			cnt+=a[j]<a[i];
		ans=(ans+f*cnt%mod)%mod; //ans+=f*cnt;
		f=f*(n-i)%mod; //f*=(n-i);
	}
	return ans;
}
//树状数组优化版,基于树状数组,O(nlogn)
int cantor(int a[],int n){
	static BIT t; t.init(); //树状数组
	ll f=1,ans=1; //假设答案最小值是1
	repeat_back(i,0,n){
		ans=(ans+f*t.sum(a[i])%mod)%mod; //ans+=f*t.sum(a[i]);
		t.add(a[i],1);
		f=f*(n-i)%mod; //f*=(n-i);
	}
	return ans;
}
//逆展开普通版,O(n^2)
int *decantor(int x,int n){
	static int f[13]={1};
	repeat(i,1,13)f[i]=f[i-1]*i;
	static int ans[N];
	set<int> s;
	x--;
	repeat(i,1,n+1)s.insert(i);
	repeat(i,0,n){
		int q=x/f[n-i-1];
		x%=f[n-i-1];
		auto it=s.begin();
		repeat(i,0,q)it++; //第q+1小的数
		ans[i]=*it;
		s.erase(it);
	}
	return ans;
}

编码与解码问题

<1>

<2>

置换群计数

Polya定理

不旋转,{U|D|L|R|F|B},k=6,共1个
对面中心连线为轴的90度旋转,{U|D|L R F B},k=3,共6个
对面中心连线为轴的180度旋转,{U|D|L R|F B},k=4,共3个
对棱中点连线为轴的180度旋转,{U L|D R|F B},k=3,共6个
对顶点连线为轴的120度旋转,{U L F|D R B},k=2,共8个
ans=0,cnt=0;
//只考虑旋转,不考虑翻转
repeat(i,1,n+1)
	ans+=qpow(3,__gcd(i,n));
cnt+=n;
//考虑翻转
if(n%2==0)ans+=(qpow(3,n/2+1)+qpow(3,n/2))*(n/2);
else ans+=qpow(3,(n+1)/2)*n;
cnt+=n;
cout<<ans/cnt<<endl;

组合数学的一些结论



博弈论

SG定理

void getSG(int n){
	mst(SG,0);
	repeat(i,1,n+1){
		mst(S,0);
		for(int j=0;f[j]<=i && j<=N;j++)
			S[SG[i-f[j]]]=1;
		for(int j=0;;j++)
		if(!S[j]){
			SG[i]=j;
			break;
		}
	}
}

Nim

Nimk

多项式

拉格朗日插值

repeat(i,0,n)x[i]%=mod,y[i]%=mod;
repeat(i,0,n){
	s1=y[i];
	s2=1;
	repeat(j,0,n)
	if(i!=j){
		s1=s1*(k-x[j])%mod;
		s2=s2*(x[i]-x[j])%mod;
	}
	ans=(ans+s1*getinv(s2)%mod+mod)%mod;
}

快速傅里叶变换+任意模数

struct FFT{
	static const int N=1<<20;
	struct cp{
		long double a,b;
		cp(){}
		cp(const long double &a,const long double &b):a(a),b(b){}
		cp operator+(const cp &t)const{return cp(a+t.a,b+t.b);}
		cp operator-(const cp &t)const{return cp(a-t.a,b-t.b);}
		cp operator*(const cp &t)const{return cp(a*t.a-b*t.b,a*t.b+b*t.a);}
		cp conj()const{return cp(a,-b);}
	};
	cp wn(int n,int f){
		static const long double pi=acos(-1.0);
		return cp(cos(pi/n),f*sin(pi/n));
	}
	int g[N];
	void dft(cp a[],int n,int f){
		repeat(i,0,n)if(i>g[i])swap(a[i],a[g[i]]);
		for(int i=1;i<n;i<<=1){
			cp w=wn(i,f);
			for(int j=0;j<n;j+=i<<1){
				cp e(1,0);
				for(int k=0;k<i;e=e*w,k++){
					cp x=a[j+k],y=a[j+k+i]*e;
					a[j+k]=x+y,a[j+k+i]=x-y;
				}
			}
		}
		if(f==-1){
			cp Inv(1.0/n,0);
			repeat(i,0,n)a[i]=a[i]*Inv;
		}
	}
	#ifdef CONV
	cp a[N],b[N];
	vector<ll> conv(const vector<ll> &u,const vector<ll> &v){ //一般fft
	    const int n=(int)u.size()-1,m=(int)v.size()-1;
	    const int k=32-__builtin_clz(n+m+1),s=1<<k;
		g[0]=0; repeat(i,1,s)g[i]=(g[i/2]/2)|((i&1)<<(k-1));
		repeat(i,0,s){
			a[i]=cp(i<=n?u[i]:0,0);
			b[i]=cp(i<=m?v[i]:0,0);
		}
	    dft(a,s,1); dft(b,s,1);
		repeat(i,0,s)a[i]=a[i]*b[i];
	    dft(a,s,-1);
	    vector<ll> ans;
	    repeat(i,0,n+m+1)ans+=llround(a[i].a);
	    return ans;
	}
	#endif
	#ifdef CONV_MOD
	cp a[N],b[N],Aa[N],Ab[N],Ba[N],Bb[N];
	vector<ll> conv_mod(const vector<ll> &u,const vector<ll> &v,ll mod){ //任意模数fft
		const int n=(int)u.size()-1,m=(int)v.size()-1,M=sqrt(mod)+1;
		const int k=32-__builtin_clz(n+m+1),s=1<<k;
		g[0]=0; repeat(i,1,s)g[i]=(g[i/2]/2)|((i&1)<<(k-1));
		repeat(i,0,s){
			a[i]=i<=n?cp(u[i]%mod%M,u[i]%mod/M):cp();
			b[i]=i<=m?cp(v[i]%mod%M,v[i]%mod/M):cp();
		}
		dft(a,s,1); dft(b,s,1);
		repeat(i,0,s){
			int j=(s-i)%s;
			cp t1=(a[i]+a[j].conj())*cp(0.5,0);
			cp t2=(a[i]-a[j].conj())*cp(0,-0.5);
			cp t3=(b[i]+b[j].conj())*cp(0.5,0);
			cp t4=(b[i]-b[j].conj())*cp(0,-0.5);
			Aa[i]=t1*t3,Ab[i]=t1*t4,Ba[i]=t2*t3,Bb[i]=t2*t4;
		}
		repeat(i,0,s){
			a[i]=Aa[i]+Ab[i]*cp(0,1);
			b[i]=Ba[i]+Bb[i]*cp(0,1);
		}
		dft(a,s,-1); dft(b,s,-1);
		vector<ll> ans;
		repeat(i,0,n+m+1){
			ll t1=llround(a[i].a)%mod;
			ll t2=llround(a[i].b)%mod;
			ll t3=llround(b[i].a)%mod;
			ll t4=llround(b[i].b)%mod;
			ans+=(t1+(t2+t3)*M%mod+t4*M*M)%mod;
		}
		return ans;
	}
	#endif
}fft;

多项式的一些概念





线性代数

矩阵乘法 矩阵快速幂

struct mat{
	static const int N=110;
	ll a[N][N];
	explicit mat(int e=0){
		repeat(i,0,n)
		repeat(j,0,n)
			a[i][j]=e*(i==j);
	}
	mat operator*(const mat &b)const{ //矩阵乘法
		mat ans(0);
		repeat(i,0,n)
		repeat(j,0,n){
			ll &t=ans.a[i][j];
			repeat(k,0,n)
				t=(t+a[i][k]*b.a[k][j])%mod;
		}
		return ans;
	}
};
mat qpow(mat a,ll b){ //矩阵快速幂
	mat ans(1);
	while(b){
		if(b&1)ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}

矩阵高级操作

int n,m;
#define T lf
struct mat{
	static const int N=110;
	vector< vector<T> > a;
	mat():a(N,vector<T>(N*2)){} //如果要求逆这里乘2
	T det;
	void r_div(int x,T k){ //第x行除以实数k
		T r=getinv(k,mod);
		repeat(i,0,m) //从x开始也没太大关系(对求det来说)
			a[x][i]=a[x][i]*r%mod;
		det=det*k%mod;
	}
	void r_plus(int x,int y,T k){ //第x行加上第y行的k倍
		repeat(i,0,m)
			a[x][i]=(a[x][i]+a[y][i]*k)%mod;
	}
	/*
	void r_div(int x,T k){ //lf版
		T r=1/k;
		repeat(i,0,m)
			a[x][i]*=r;
		det*=k;
	}
	void r_plus(int x,int y,T k){ //lf版
		repeat(i,0,m)
			a[x][i]+=a[y][i]*k;
	}
	*/
	bool gauss(){ //高斯消元,返回是否满秩,注意必须n<=m
		det=1;
		repeat(i,0,n){
			int t=-1;
			repeat(j,i,n)
			if(abs(a[j][i])>err){
				t=j;
				break;
			}
			if(t==-1){det=0; return 0;}
			if(t!=i){
				a[i].swap(a[t]);
				det=-det;
			}
			r_div(i,a[i][i]);
			repeat(j,0,n) //如果只要det可以从i+1开始
			if(j!=i && abs(a[j][i])>err)
				r_plus(j,i,-a[j][i]);
		}
		return 1;
	}
	T get_det(){ //返回行列式
		gauss();
		return det;
	}
	bool get_inv(){ //把自己变成逆矩阵,返回是否成功
		if(n!=m)return 0;
		repeat(i,0,n)
		repeat(j,0,n)
			a[i][j+n]=i==j; //生成增广矩阵
		m*=2;
		bool t=gauss();
		m/=2;
		repeat(i,0,n)
		repeat(j,0,n)
			a[i][j]=a[i][j+n];
		return t;
	}
}a;
int n;
struct mat{
	static const int N=110;
	vector< vector<ll> > a;
	mat():a(N,vector<ll>(N)){}
	ll det(int n){
		ll ans=1;
		repeat(i,0,n){
			repeat(j,i+1,n)
			while(a[j][i]){
				ll t=a[i][i]/a[j][i];
				repeat(k,i,n)a[i][k]=(a[i][k]-a[j][k]*t)%mod;
				swap(a[i],a[j]);
				ans=-ans;
			}
			ans=ans*a[i][i]%mod;
			if(!ans)return 0;
		}
		return (ans+mod)%mod;
	}
}a;

矩阵的一些结论




线性基

异或线性基

struct basis{
	static const int n=63;
	#define B(x,i) ((x>>i)&1)
	ll a[n],sz;
	bool failpush; //是否线性相关
	void init(){mst(a,0); sz=failpush=0;}
	void push(ll x){ //插入元素
		repeat(i,0,n)
		if(B(x,i))
			x^=a[i];
		if(x!=0){
			int p=63-__builtin_clzll(x);
			sz++;
			repeat(i,p+1,n)
			if(B(a[i],p))
				a[i]^=x;
			a[p]=x;
		}
		else failpush=1;
	}
	ll top(){ //最大值
		ll ans=0;
		repeat(i,0,n)
			ans^=a[i];
		return ans;
	}
	bool exist(ll x){ //是否存在
		repeat_back(i,0,n)
		if((x>>i)&1){
			if(a[i]==0)return 0;
			else x^=a[i];
		}
		return 1;
	}
	ll kth(ll k){ //第k小,不存在返回-1
		if(failpush)k--; //如果认为0是可能的答案就加这句话
		if(k>=(1ll<<sz))return -1;
		ll ans=0;
		repeat(i,0,n)
		if(a[i]!=0){
			if(k&1)ans^=a[i];
			k>>=1;
		}
		return ans;
	}
}b;
basis operator+(basis a,const basis &b){ //将b并入a
	repeat(i,0,a.n)
	if(b.a[i])
		a.push(b.a[i]);
	a.failpush|=b.failpush;
	return a;
}
struct basis{
	...
	void push(ll x){ //插入元素
		repeat_back(i,0,n)
		if((x>>i)&1){
			if(a[i]==0){a[i]=x; sz++; return;}
			else x^=a[i];
		}
		failpush=1;
	}
	ll top(){ //最大值
		ll ans=0;
		repeat_back(i,0,n)
			ans=max(ans,ans^a[i]);
		return ans;
	}
	void rebuild(){ //求第k小的前置操作
		repeat_back(i,0,n)
		repeat_back(j,0,i)
		if((a[i]>>j)&1)
			a[i]^=a[j];
	}
}b;

实数线性基

struct basis{
	lf a[N][N]; bool f[N]; int n; //f[i]表示向量a[i]是否被占
	void init(int _n){
		n=_n;
		fill(f,f+n,0);
	}
	bool push(lf x[]){ //返回0表示可以被线性表示,不需要插入
		repeat(i,0,n)
		if(fabs(x[i])>1e-5){ //这个值要大一些
			if(f[i]){
				lf t=x[i]/a[i][i];
				repeat(j,0,n)
					x[j]-=t*a[i][j];
			}
			else{
				f[i]=1;
				repeat(j,0,n)
					a[i][j]=x[j];
				return 1;
			}
		}
		return 0;
	}
}b;

数学杂项

主定理

质数表

42737, 46411, 50101, 52627, 54577, 191677, 194869, 210407, 221831, 241337, 578603, 625409, 713569, 788813, 862481, 2174729, 2326673, 2688877, 2779417, 3133583, 4489747, 6697841, 6791471, 6878533, 7883129, 9124553, 10415371, 11134633, 12214801, 15589333, 17148757, 17997457, 20278487, 27256133, 28678757, 38206199, 41337119, 47422547, 48543479, 52834961, 76993291, 85852231, 95217823, 108755593, 132972461, 171863609, 173629837, 176939899, 207808351, 227218703, 306112619, 311809637, 322711981, 330806107, 345593317, 345887293, 362838523, 373523729, 394207349, 409580177, 437359931, 483577261, 490845269, 512059357, 534387017, 698987533, 764016151, 906097321, 914067307, 954169327

1572869, 3145739, 6291469, 12582917, 25165843, 50331653 (适合哈希的素数)

19260817 原根15,是某个很好用的质数
1000000007 原根5
998244353 原根3

            r*2^k+1   r  k  g
                  3   1  1  2
                  5   1  2  2
                 17   1  4  3
                 97   3  5  5
                193   3  6  5
                257   1  8  3
               7681  15  9 17
              12289   3 12 11
              40961   5 13  3
              65537   1 16  3
             786433   3 18 10
            5767169  11 19  3
            7340033   7 20  3
           23068673  11 21  3
          104857601  25 22  3
          167772161   5 25  3
          469762049   7 26  3
          998244353 119 23  3
         1004535809 479 21  3
         2013265921  15 27 31
         2281701377  17 27  3
         3221225473   3 30  5
        75161927681  35 31  3
        77309411329   9 33  7
       206158430209   3 36 22
      2061584302081  15 37  7
      2748779069441   5 39  3
      6597069766657   3 41  5
     39582418599937   9 42  5
     79164837199873   9 43  5
    263882790666241  15 44  7
   1231453023109121  35 45  3
   1337006139375617  19 46  3
   3799912185593857  27 47  5
   4222124650659841  15 48 19
   7881299347898369   7 50  6
  31525197391593473   7 52  3
 180143985094819841   5 55  6
1945555039024054273  27 56  5
4179340454199820289  29 57  3

struct of 自动取模

struct mint{
	ll v;
	mint(ll _v){v=_v%mod;}
	mint operator+(const mint &b)const{return v+b.v;}
	mint operator-(const mint &b)const{return v-b.v;}
	mint operator*(const mint &b)const{return v*b.v;}
	explicit operator ll(){return (v+mod)%mod;}
};

struct of 高精度

struct big{
	vector<ll> a;
	static const ll k=1000000000,w=9;
	int size()const{return a.size();}
	explicit big(const ll &x=0){ //接收ll
		*this=big(to_string(x));
	}
	explicit big(const string &s){ //接收string
		static ll p10[9]={1};
		repeat(i,1,w)p10[i]=p10[i-1]*10;
		int len=s.size();
		int f=(s[0]=='-')?-1:1;
		a.resize(len/w+1);
		repeat(i,0,len-(f==-1))
			a[i/w]+=f*(s[len-1-i]-48)*p10[i%w];
		adjust();
	}
	int sgn(){return a.back()>=0?1:-1;} //这个只能在强/弱调整后使用
	void shrink(){ //收缩(内存不收缩)
		while(size()>1 && a.back()==0)a.pop_back();
	}
	void adjust(){ //弱调整
		repeat(i,0,3)a.push_back(0);
		repeat(i,0,size()-1){
			a[i+1]+=a[i]/k;
			a[i]%=k;
		}
		shrink();
	}
	void final_adjust(){ //强调整
		adjust();
		int f=sgn();
		repeat(i,0,size()-1){
			ll t=(a[i]+k*f)%k;
			a[i+1]+=(a[i]-t)/k;
			a[i]=t;
		}
		shrink();
	}
	operator string(){ //转换成string
		static char s[N]; char *p=s;
		final_adjust();
		if(sgn()==-1)*p++='-';
		repeat_back(i,0,size())
			sprintf(p,i==size()-1?"%lld":"%09lld",abs(a[i])),p+=strlen(p);
		return s;
	}
	const ll &operator[](int n)const{ //访问
		return a[n];
	}
	ll &operator[](int n){ //弹性访问
		repeat(i,0,n-size()+1)a.push_back(0);
		return a[n];
	}
};
big operator+(big a,const big &b){
	repeat(i,0,b.size())a[i]+=b[i];
	a.adjust();
	return a;
}
big operator-(big a,const big &b){
	repeat(i,0,b.size())a[i]-=b[i];
	a.adjust();
	return a;
}
big operator*(const big &a,const big &b){
	big ans;
	repeat(i,0,a.size()){
		repeat(j,0,b.size())
			ans[i+j]+=a[i]*b[j];
		ans.adjust();
	}
	return ans;
}
ll operator%(const big &a,ll mod){
	ll ans=0,p=1;
	repeat(i,0,a.size()){
		ans=(ans+p*a[i])%mod;
		p=(p*a.k)%mod;
	}
	return (ans+mod)%mod;
}
bool operator<(big a,big b){
	a.final_adjust();
	b.final_adjust();
	repeat_back(i,0,max(a.size(),b.size()))
		if(a[i]!=b[i])return a[i]<b[i];
	return 0;
}
bool operator==(big a,big b){
	a.final_adjust();
	b.final_adjust();
	repeat_back(i,0,max(a.size(),b.size()))
		if(a[i]!=b[i])return 0;
	return 1;
}

表达式求值

inline int lvl(const string &c){ //运算优先级,小括号要排最后
	if(c=="*")return 2;
	if(c=="(" || c==")")return 0;
	return 1;
}
string convert(const string &in) { //中缀转后缀
	stringstream ss;
	stack<string> op;
	string ans,s;
	repeat(i,0,in.size()-1){
		ss<<in[i];
		if(!isdigit(in[i]) || !isdigit(in[i+1])) //插入空格
			ss<<" ";
	}
	ss<<in.back();
	while(ss>>s){
		if(isdigit(s[0]))ans+=s+" ";
		else if(s=="(")op.push(s);
		else if(s==")"){
			while(!op.empty() && op.top()!="(")
				ans+=op.top()+" ",op.pop();
			op.pop();
		}
		else{
			while(!op.empty() && lvl(op.top())>=lvl(s))
				ans+=op.top()+" ",op.pop();
			op.push(s);
		}
	}
	while(!op.empty())ans+=op.top()+" ",op.pop();
	return ans;
}
ll calc(const string &in){ //后缀求值 
	stack<ll> num;
	stringstream ss;
	ss<<in;
	string s;
	while(ss>>s){
		char c=s[0];
		if(isdigit(c))
			num.push((stoll(s))%mod);
		else{
			ll b=num.top(); num.pop();
			ll a=num.top(); num.pop();
			if(c=='+')num.push((a+b)%mod);
			if(c=='-')num.push((a-b)%mod);
			if(c=='*')num.push((a*b)%mod);
			//if(c=='^')num.push(qpow(a,b));
		}
	}
	return num.top();
}

一些数学结论

约瑟夫问题

int jos(int n,int k){
	int res=0;
	repeat(i,1,n+1)res=(res+k)%i;
	return res; //res+1,如果编号从1开始
}
int jos(int n,int k){
	if(n==1 || k==1)return n-1;
	if(k>n)return (jos(n-1,k)+k)%n; //线性算法
	int res=jos(n-n/k,k)-n%k;
	if(res<0)res+=n; //mod n
	else res+=res/(k-1); //还原位置
	return res; //res+1,如果编号从1开始
}

格雷码 汉诺塔

格雷码
ll grey(ll n){ //第n个格雷码
	return n^(n>>1);
}
ll degrey(ll n){ //逆格雷码变换,法一
	repeat(i,0,63) //or 31
		n=n^(n>>1);
	return n;
}
ll degrey(ll n){ //逆格雷码变换,法二
	int ans=0;
	while(n){
		ans^=n;
		n>>=1;
	}
	return ans;
}
汉诺塔
cin>>n; //层数
repeat(k,1,(1<<n)){
	int i=__builtin_ctzll(k)+1;
	int p1=(k>>i)%3; //移动前状态
	int p2=(p1+1)%3; //移动后状态
	if(i%2==n%2){
		p1=(3-p1)%3;
		p2=(3-p2)%3;
	}
	cout<<"move "<<i<<": "<<"ABC"[p1]<<" -> "<<"ABC"[p2]<<endl;
}

Stern-Brocot树 Farey序列

浮点与近似计算

数值积分 | 自适应辛普森法

\(\int_{l}^{r}f(x)\mathrm{d}x\) 的近似值

lf raw(lf l,lf r){ //辛普森公式
	return (f(l)+f(r)+4*f((l+r)/2))*(r-l)/6;
}
lf asr(lf l,lf r,lf err,lf ans){
	lf m=(l+r)/2;
	lf x=raw(l,m),y=raw(m,r);
	if(fabs(x+y-ans)<=15*err)
		return x+y-(x+y-ans)/15;
	return asr(l,m,err/2,x)+asr(m,r,err/2,y);
}
//调用方法:asr(l,r,err,raw(l,r))
牛顿迭代法
lf newton(lf n){
	lf x=1;
	while(1){
		lf y=(x+n/x)/2; //这里求了sqrt
		if(fabs(x-y)<err)return x;
		x=y;
	}
}
public static BigInteger isqrtNewton(BigInteger n){
	BigInteger a=BigInteger.ONE.shiftLeft(n.bitLength()/2);
	boolean d=false;
	while(true){
		BigInteger b=n.divide(a).add(a).shiftRight(1);
		if(a.compareTo(b)==0 || a.compareTo(b)<0 && d)
			break;
		d=a.compareTo(b)>0;
		a=b;
	}
	return a;
}
others of 浮点与近似计算

others of 数学杂项









ACM模板_axiomofchoice

全文结束