ACM模板_axiomofchoice
目录
语法
c++
#include <bits/stdc++.h>
using namespace std;
#define lll __int128
typedef long long ll; const int inf=2e9;
typedef double lf; const lf err=1e-7;
typedef pair<int,int> pii;
#define repeat(i,a,b) for(int i=(a),iE=(b);i<iE;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,iE=(a);i>=iE;i--)
#define mst(a,x) memset((a),(x),sizeof(a))
#define qwq {cerr<<"qwq"<<endl;}
#define orz(x) {cerr<<#x": "<<x<<endl;}
#define Clear(a) {a=decltype(a)();}
ll read(){ll n; scanf("%lld",&n); return n;}
const int N=110;
const int mod=1e9+7;
//#define int ll
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
return 0;
}//如果没有万能头
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<map>平板电视红黑树
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。#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且最小）块状链表rope
#include <ext/rope>
using namespace __gnu_cxx;
rope<int> r; //块状链表
r.push_back(n);
r.insert(pos,n);
r.erase(pos,len);
r.substr(pos,len);
r[pos] //只能访问不能修改
//空……空缺随机数mt19937
高级一点的随机数mt19937(是一个类)，比rand()快
随机数范围unsigned int
#include<random>
mt19937 rnd(time(0));
cout<<rnd()<<endl;bitset
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位
支持所有位运算complex
complex<lf> c; //复数
complex<lf> c(1,2);
c.real(); //实部
c.imag(); //虚部浮点数常数
float 1e38, 有效数字6
double 1e308, 有效数字15
long double 1e4932, 有效数字18STL函数
将第k大的数置于k这个位置： nth_element(begin,begin+k,end);
返回num是否存在：binary_search(begin,end,num,[less])
返回第一个大于num的数字地址： upper_bound(begin,end,num)
返回第一个小于num的数字地址： upper_bound(begin,end,num,greater<type>())
返回第一个大于等于num的数字地址： lower_bound(begin,end,num)
返回第一个小于等于num的数字地址： lower_bound(begin,end,num,greater<type>())
返回是否存在： binary_search(begin,end,num,[less])
填充：fill(begin,end,element);
复制（注意会复制到b里）：copy(a_begin,a_end,b_begin);
vector去重（之前要排序）：a.erase(unique(a.begin(),a.end()),a.end());
单次归并（合并有序列表a,b至c）：merge(a_begin,a_end,b_begin,b_end,c_begin,[less]);
set,map合并：a.insert(b.begin(),b.end());
递增赋值（赋值为v,v+1,v+2,...）：iota(begin,end,v);
翻转：reverse(begin,end);decltype
int n; decltype(n) n2; //decltype(n) 等价于 int吸氧气
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")ifdef
#define DEBUG
#ifdef DEBUG
// do something
#endif
#ifndef DEBUG
// do something
#endif进制转换
itoa(n,str,base) //将n存入字符数组中(只能int)（不一定能用）
strtol(str,0,base),strtoll //返回字符数组的base进制数
stol(s,0,base),stoll //返回字符串的base进制数
sscanf,sprintf //十进制
to_string(n) //十进制位运算函数（不需要头文件）
__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的个数是否为奇数cmath
lround(x),lrint(x) //四舍五入到long
llround(x),llrint(x); //四舍五入到long long双关键字比较
不如用 make_pair(a.x,a.y)<make_pair(b.x,b.y) 或者 make_tuple
int类型还可以 pii(a.x,a.y)<pii(b.x,b.y)
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);
}
}编译运行 java Main.java
编译 javac Main.java //生成Main.class
运行 java Main
数据类型
int //4字节有符号
long //8字节有符号
double
boolean
char //还能表示Unicode字符
Stringfinal double PI=3.14; //final => (c++) const
var n=1; //var => (c++) auto
long型常量结尾加L，如1L
空指针null
数组
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() //是否读完if,switch,while,do while,for,for(i:A)同C++
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) //booleanMath
//不用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 *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一定要转换成BigIntegerBigDecimal
import java.math.BigDecimal;
n.divide(n2,2,BigDecimal.ROUND_HALF_UP) //保留两位（四舍五入）动态规划
多重背包
二进制版，O(mnlog(max{num}))
//m是总容量
repeat(i,0,n)
for(int b=1;num[i]>0;num[i]-=b,b<<=1){
int cost=min(b,num[i])*w[i];
repeat(j,cost,m+1)
dp[j]=max(dp[j],dp[j-cost]+val[i]);
}
return dp[m];单调队列版
//空缺最长不下降子序列LIS
二分查找优化，O(nlogn)
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;计算几何
向量（结构体）
struct vec{
lf x,y;
vec(lf x=0,lf y=0):x(x),y(y){}
vec operator-(vec b){return vec(x-b.x,y-b.y);}
vec operator+(vec b){return vec(x+b.x,y+b.y);}
vec operator*(lf k){return vec(k*x,k*y);}
bool operator<(vec b)const{return make_pair(x,y)<make_pair(b.x,b.y);}
lf len(){return sqrt(x*x+y*y);}
lf sqr(){return x*x+y*y;}
}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 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 false;
#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);
}曼哈顿距离、切比雪夫距离
曼：mdist=|x1-x2|+|y1-y2|
切：cdist=max(|x1-x2|,|y1-y2|)
转换：
mdist((x,y),*)=cdist((x+y,x-y),**)
cdist((x,y),*)=mdist(((x+y)/2,(x-y)/2),**)
Pick定理
正方形点阵：面积=内部点数+边上点数/2-1
三角形点阵：面积=2*内部点数+边上点数-2
二维凸包
求上凸包，按x坐标（键二为y）升序排序，从小到大加入表U，如果出现凹多边形情况则删除倒数第二个点。下凸包反着来。
O(nlogn)，排序是瓶颈
//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自动变成下凸包
}旋转卡壳
每次找到凸包每条边的最远点，基于二维凸包，O(nlogn)
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;
}点是否在线段上
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));
}最大空矩形 | 扫描法
在限定范围((0,0)到(l,w))内求面积最大的不覆盖任何点的矩形面积，O(n^2)，n是点数
如果是lf就把vec结构体内部、ans、u和d的类型改一下
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;
}平面最近点对 | 分治
O(nlogn)
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;
}最小圆覆盖 | 随机增量法
随机化，均摊O(n)
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(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 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;}三维凸包
将所有凸包上的面放入面集f中，其中face::p[i]作为a的下标，O(n^2)
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);
}
}数据结构
ST表
利用倍增实现对区间的查询操作，初始化O(nlogn)，查询O(1)
//RMQ=区间最值查询问题
struct RMQ{ //注意logN=log(N)+2
#define logN 18
int f[N][logN],log[N];
RMQ(){
log[1]=0;
repeat(i,2,N)
log[i]=log[i/2]+1;
}
void build(){
repeat(i,0,n)
f[i][0]=a[i];
repeat(k,1,logN)
repeat(i,0,n-(1<<k)+1)
f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]); //最大值
}
int query(int l,int r){
int s=log[r-l+1];
return max(f[l][s],f[r-(1<<s)+1][s]); //最大值
}
}rmq;单调队列MQ
求所有长度为k的区间中的最小值，完整跑下来O(n)
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((pii){n,T});
while(!q.empty() && q.front().second<=T-k)
q.pop_front();
}
}mq;树状数组BIT
单点+区间，修改查询O(logn)
#define lb(x) (x&(-x))
struct BIT{
ll t[500010]; //一倍内存吧
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;
}
};超级树状数组SPBIT
基本只允许加法，区间+区间，修改查询O(logn)
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));
}
};线段树ST
区间+区间，修改查询O(logn)
#define zero 0
struct ST{ //build(1,1,n) update(1,1,n,?,?,?) query(1,1,n,?,?)
ll a[400010],lazy[400010]; //四倍内存
void build(int n,int l,int r){
int lc=n*2,rc=n*2+1,m=(l+r)/2;
lazy[n]=zero;
if(l==r){
a[n]=a0[m];
return;
}
build(lc,l,m);
build(rc,m+1,r);
a[n]=a[lc]+a[rc];
}
void down(int n,int l,int r){
int lc=n*2,rc=n*2+1,m=(l+r)/2;
if(l<r){
lazy[lc]+=lazy[n];
lazy[rc]+=lazy[n];
}
a[n]+=lazy[n]*(r-l+1);
lazy[n]=zero;
}
void update(int n,int l,int r,int x,int y,ll num){
int lc=n*2,rc=n*2+1,m=(l+r)/2;
x=max(x,l); y=min(y,r); if(x>y){down(n,l,r);return;}//!!
if(x==l && y==r){
lazy[n]+=num;
down(n,l,r);
return;
}
down(n,l,r);
update(lc,l,m,x,y,num);
update(rc,m+1,r,x,y,num);
a[n]=a[lc]+a[rc];
}
ll query(int n,int l,int r,int x,int y){
int lc=n*2,rc=n*2+1,m=(l+r)/2;
x=max(x,l); y=min(y,r); if(x>y)return zero;
down(n,l,r);
if(x==l && y==r)
return a[n];
return query(lc,l,m,x,y)+query(rc,m+1,r,x,y);
}
}st;指针版线段树ST
（l,r,lc,rc更占内存）
#define zero 0
struct ST{
int data,lazy,l,r;
ST *lc,*rc;
ST(int l,int r):l(l),r(r){
lazy=zero;
if(l==r){
data=a[l];
return;
}
int m=(l+r)/2;
lc=new ST(l,m);
rc=new ST(m+1,r);
up();
}
void up(){
data=lc->data+rc->data;
}
void down(){
if(l<r){
lc->lazy+=lazy;
rc->lazy+=lazy;
}
data+=lazy*(r-l+1);
lazy=zero;
}
void update(int x,int y,int num){
x=max(x,l); y=min(y,r); if(x>y){down();return;}
if(x==l && y==r){
lazy+=num;
down();
return;
}
down();
lc->update(x,y,num);
rc->update(x,y,num);
up();
}
int query(int x,int y){
x=max(x,l); y=min(y,r); if(x>y)return zero;
down();
if(x==l && y==r)
return data;
return lc->query(x,y)+rc->query(x,y);
}
}*st;
//初始化st=new ST(1,n);带内存池指针版线段树ST
相比上一个，感觉时空没什么优化，但是可以重复构造线段树
#define zero 0
struct ST{
int data,lazy,l,r;
ST *lc,*rc;
ST(int,int);
ST(){};
void up(){
data=lc->data+rc->data;
}
void down(){
if(l<r){
lc->lazy+=lazy;
rc->lazy+=lazy;
}
data+=lazy*(r-l+1);
lazy=zero;
}
void update(int x,int y,int num){
x=max(x,l); y=min(y,r); if(x>y){down();return;}
if(x==l && y==r){
lazy+=num;
down();
return;
}
down();
lc->update(x,y,num);
rc->update(x,y,num);
up();
}
int query(int x,int y){
x=max(x,l); y=min(y,r); if(x>y)return zero;
down();
if(x==l && y==r)
return data;
return lc->query(x,y)+rc->query(x,y);
}
}*st;
ST pool[200010],*poolt; //两倍内存
ST::ST(int l,int r):l(l),r(r){
lazy=zero;
if(l==r){
data=a[l];
return;
}
int m=(l+r)/2;
lc=poolt++; *lc=ST(l,m);
rc=poolt++; *rc=ST(m+1,r);
up();
}
//初始化poolt=pool; st=poolt++; *st=ST(1,n);并查集DSU
合并查找O(loglogn)
struct DSU{ //合并：d[x]=d[y]，查找：d[x]==d[y]
int a[10010];
void init(){
repeat(i,0,n+1)a[i]=i;
}
int fa(int x){
return a[x]==x?x:a[x]=fa(a[x]);
}
int &operator[](int x){
return a[fa(x)];
}
}d;左偏树LLT
万年不用，O(?)
struct LLT{ //编号从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
}llt;
//添加元素llt.add(v),位置是llt.val.size()-1
//是否未被pop：llt.exist(x)
//合并：llt.join(x,y)
//堆顶：llt.val[llt.top(x)]
//弹出：llt.pop(x)zkw线段树
单点+区间
修改查询O(logn)
struct zkw{ //treelen的值是2^k-1且大于n（从0开始就2^k）
#define treelen 524287
#define op(a,b) max(a,b)
#define zero 0
ll a[treelen*2+10]; //两倍内存
void init(){
mst(a,0);
}
void up(int x){
a[x]=op(a[x<<1],a[(x<<1)^1]);
}
void update(ll x,ll k){ //位置x加上k
x+=treelen;
a[x]+=k; //也可以直接赋值等操作
while(x>>=1)up(x);
}
int sum(int l,int r){
int ans=zero;
for(l+=treelen-1,r+=treelen+1;l^r^1;l>>=1,r>>=1){
if(~l & 1)ans=op(ans,a[l^1]);
if(r & 1)ans=op(ans,a[r^1]);
}
return ans;
}
}t;多关键字堆
自己瞎搞的，查询、弹出指定关键字最大的元素
pair版，查询插入弹出O(logn)
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);
}
};vector版，查询插入弹出O(关键字数*logn)
using vi=vector<int>;
struct HEAP{
static const int n=2;
multiset< vi > a[n];
void init(){
repeat(i,0,n)
a[i].clear();
}
void push(vi x){
repeat(i,0,n){
swap(x[0],x[i]);
a[i].insert(x);
swap(x[0],x[i]);
}
}
vi top(int i){
vi x=*--a[i].end();
swap(x[0],x[i]);
return x;
}
void pop(int i){
vi x=top(i);
repeat(i,0,n){
swap(x[0],x[i]);
a[i].erase(a[i].lower_bound(x));
swap(x[0],x[i]);
}
}
};双头优先队列
自己瞎搞的，查询插入弹出O(logn)
struct HEAP{
multiset<int> s;
void init(){s.clear();}
void push(int x){s.insert(x);}
int front(){return *--s.end();}
int back(){return *s.begin();}
void pop_front(){s.erase(--s.end());}
void pop_back(){s.erase(s.begin());}
};图论
图论的一些概念、结论
基环图：树加一条边
仙人掌：每条边至多属于一个简单环的无向联通图
简单图：不含重边和自环
多重图：含重边的图
完全图：顶点两两相连的无向图
竞赛图：顶点两两相连的有向图
自环：两个端点是同一顶点的边
简单路径/回路：每个点至多经过一次的路径/回路（有时是每个边）
点u到v可达：有向图中，存在u到v的路径
点u和v联通：无向图中，存在u到v的路径
点割集：极小的，把图分成多个联通块的点集
割点：自身就是点割集的点
边割基：极小的，把图分成多个联通块的边集
桥：自身就是边割集的边
生成子图：点数和原图相同
导出子图/诱导子图：选取一个点集，尽可能多加边
正则图：所有点的度均相同的无向图
强正则图：与任意两个相邻的点相邻的点数相同，与任意两个不相邻的点相邻的点数相同的正则图
强正则图的点数 \(v\)，度 \(k\)，相邻的点的共度 \(\lambda\)，不相邻的点的共度 \(\mu\) 有 \(k(k-1-\lambda)=\mu(v-1-k)\)
强正则图的例子：所有完全图、所有nk顶点满n分图、五边形镶嵌一个五角星
点联通度：最小点割集的大小
边联通度：最小边割集的大小
Whitney定理：点联通度≤边联通度≤最小度
最大团：最大完全子图
最大独立集：最多的两两不连接的顶点
最大独立集即补图最大团
最小染色数：相邻的点不同色的最少色数
最小团覆盖数：覆盖整个图的最少团数
最小染色数等于补图最小团覆盖数
哈密顿通路：通过所有顶点有且仅有一次的路径，若存在则为半哈密顿图/哈密顿图
哈密顿回路：通过所有顶点有且仅有一次的回路，若存在则为哈密顿图
完全图 \(K_{2k+1}\) 的边集可以划分为 \(k\) 个哈密顿回路
完全图 \(K_{2k}\) 的边集去掉 \(k\) 条互不相邻的边后可以划分为 \(k-1\) 个哈密顿回路
Havel-Hakimi定理：给定一个度序列，反向构造出这个图
解：贪心，每次让剩余度(=k)最大的顶点连接其余最大的k个顶点
（我认为二路归并是最快的，可是找到的代码都用了sort()）
最短路径，最小环
有向图最小环Dijkstra，O(E(V+E)logV)
每条边(u,v)，对v进行Dijstra，计算dis[u]+edge[u][v]，适用稀图
有向图最小环Floyd，O(V^3)
普通Floyd完之后，任意两点，计算dis[i][j]+dis[j][i]，适用稠图
无向图最小环：删边，然后Dijkstra，O(E(V+E)logV)
Dijkstra，O((V+E)logV)
struct node{
int to,dis;
bool operator<(node b)const{
return dis>b.dis;
}
};
void dijkstra(int s){//s是起点
repeat(i,0,n){
vis[i]=0;
dis[i]=2147483647;
}
dis[s]=0; //last[s]=-1;
q=priority_queue<node>();
q.push((node){s,0});
while(!q.empty()){
x=q.top().to; q.pop();
if(vis[x])continue; vis[x]=1;
repeat(i,0,a[x].size()){
p=a[x][i].to;
if(dis[p]>dis[x]+a[x][i].dis){ //更新
dis[p]=dis[x]+a[x][i].dis;
q.push((node){p,dis[p]});
//last[p]=x; //last可以记录最短路（倒着）
}
}
}
}多源最短路径 | Floyd
O(V^3)
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优化（只考虑是否可达），O(V^3)
//bitset<N> g<N>;
repeat(i,0,n)
repeat(j,0,n)
if(g[j][i])
g[j]|=g[i];负环 | SPFA
spfa搜索中，有一个点入队n次即存在负环
邻接表从0开始编号，O(VE)
int n;
struct node{int to,dis;};
vector<node> e[N];
int cnt[N],inque[N],vis[N],dis[N];
bool spfa(int s){ //返回是否有负环（s为起点）
queue<int> q; q.push(s); inque[s]=0;
cnt[s]=1; dis[s]=0; //last[s]=-1;
while(!q.empty()){
int x=q.front(); q.pop(); inque[x]=0; //出队
vis[x]=1;
for(auto i:e[x]){
int p=i.to;
if(dis[p]>dis[x]+i.dis){
dis[p]=dis[x]+i.dis;
//last[p]=x; //last可以记录最短路（倒着）
if(inque[p])continue;
q.push(p); inque[p]=1; //入队（求最短路可以SLF优化）
if(++cnt[p]>n)return 1;
}
}
}
return 0;
}
bool solve(){ //返回是否有负环
fill(cnt,cnt+n,0);
fill(dis,dis+n,inf);
fill(inque,inque+n,0);
fill(vis,vis+n,0);
repeat(i,0,n)
if(!vis[i] && spfa(i))
return 1;
return 0;
}最小生成树 | Kruskal
对边长排序，然后添边，并查集判联通，O(ElogE)，排序是瓶颈
int Kruskal(){
int 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){
x=y; ans+=e[i].dis; cnt++;
}
if(cnt==n-1)break;
}
if(cnt!=n-1)return -1; else return ans;
}树的直径（最长路径）
以任意一点出发所能达到的最远节点为一个端点
以这个端点出发所能达到的最远节点为另一个端点
两次Dijkstra（其实只是dfs，维护vis[]和dis[]）
树的重心（以重心为根，其最大儿子子树最小）
DFS计算所有子树的size
最后计算最大儿子子树最小的节点，取最小的即可
最近公共祖先LCA
欧拉序列RMQ版本（编号从0开始），初始化O(nlogn)，查询O(1)
int n,m,s;
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]);
}强联通分量Tarjan
O(V+E)
vector<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],belong[N]; //belong染色结果
vector<int> sz; //第n个颜色的点数
int dcnt;
void dfs(int x){
if(vis[x])return;
vis[x]=1;
stk.push_back(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.back();
stk.pop_back();
instk[t]=0;
sz.back()++; //记录
belong[t]=sz.size()-1; //染色
}while(t!=x);
}
}拓扑排序
O(V+E)
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退出序
（不记录点的vis，只记录边的vis）
最大团，极大团计数
求最大团顶点数（和最大团），g[][]编号从0开始，O(指数)
int g[N][N],p[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=p[x][i],k=0;
if(Max[u]+x<=ans)return 0;
repeat(j,i+1,cur)
if(g[u][p[x][j]])
p[x+1][k++]=p[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])
p[1][k++]=j;
//rec.clear(); rec.push_back(i);
if(dfs(1,k)){
ans++;
//maxrec=rec;
}
Max[i]=ans;
}
}求极大团个数（和所有极大团），g[][]的编号从1开始！O(指数)
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);
}弦图，区间图 | 最大势算法MCS
弦是连接环上不相邻点的边；弦图是所有长度大于3的环都有弦的无向图（类似三角剖分）
单纯点：所有与v相连的点构成一个团，则v是一个单纯点
完美消除序列：即点集的一个排列 \([v_1,v_2,...,v_n]\) 满足任意 \(v_i\) 在 \([v_{i+1},...,v_n]\) 的导出子图中是一个单纯点
定理：无向图是弦图 \(\Leftrightarrow\) 无向图存在完美消除序列
定理：最大团顶点数 \(\le\) 最小染色数（弦图取等号）
定理：最大独立集顶点数 \(\le\) 最小团覆盖（弦图取等号）
最大势算法MCS求完美消除序列：每次求出与 \([v_{i+1},...,v_n]\) 相邻点数最大的点作为 \(v_i\)
e[][]点编号从1开始！rec下标从1开始！桶优化，O(V+E)
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--;
}
}判断弦图（判断是否为完美消除序列）：对所有 \(v_i\)，\([v_{i+1},...,v_n]\) 中与 \(v_i\) 相连的最靠前一个点 \(v_j\) 是否与与 \(v_i\) 连接的其他点相连
编号规则同上，大佬：O(V+E)，我：O((V+E)logV)
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;
}区间图：给出的每个区间都看成点，有公共部分的两个区间之间连一条边
区间图是弦图（反过来不一定），可以应用弦图的所有算法
区间图的判定：所有弦图可以写成一个极大团树（所有极大团看成一个顶点，极大团之间有公共顶点就连一条边），区间图的极大团树是一个链
稳定婚姻 | 延迟认可
稳定意味着不存在一对不是情侣的男女，都认为当前伴侣不如对方
编号从0开始，O(n^2)
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); //下次努力
}
}二分图匹配
匈牙利，O(VE)
int n,m; //n个左顶点，m个右顶点
vector<int> a[N]; //左顶点x与右顶点a[x][0..sz]有连接
int dcnt,mch[N],dfn[N]; //mch[p]表示左顶点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 true;
}
}
}
return false;
}
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;
}构造网络跑Dinic，基于Dinic，O(V*sqrt(E))
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;前向星
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(){ //初始化
a.clear();
fill(head,head+n,-1);
}
//for(int i=head[x];i!=-1;i=a[i].nxt) //遍历x出发的边(x,a[i].to)网络最大流
EK，单路增广，O(V*E^2)
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;
}
int n,m,s,t; //点数，边数，源点，汇点
queue<int> q;
struct {int to,e;} pre[N]; //路径的前一个点，这条边的位置
bool vis[N];
bool bfs(){ //找一条增广路
fill(vis,vis+n,0); vis[s]=1;
q=queue<int>(); q.push(s);
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];~i;i=a[i].nxt){
int p=a[i].to;
if(vis[p] || a[i].w==0)continue;
pre[p].to=x;
pre[p].e=i;
if(p==t)return 1;
vis[p]=1;
q.push(p);
}
}
return 0;
}
void init(){ //EK的初始化
a.clear();
fill(head,head+n,-1);
}
int ek(){ //返回最大流
int ans=0;
while(bfs()){
int flow=inf;
for(int i=t;i!=s;i=pre[i].to)
flow=min(flow,a[pre[i].e].w);
for(int i=t;i!=s;i=pre[i].to){
a[pre[i].e].w-=flow;
a[pre[i].e^1].w+=flow;
}
ans+=flow;
}
return ans;
}
//填加边(x,y)的方法
//addedge(x,y,w);
//addedge(y,x,0); //反向弧提供改错机会Dinic，多路增广，O(V^2*E)
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;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;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(){ //Dinic的初始化
a.clear();
fill(head,head+n,-1);
fill(inque,inque+n,0);
}
int dinic(){ //返回最大流
int ans=0;
while(bfs())
ans+=dfs(s,inf);
return ans;
}
//填加边(x,y)的方法
//addedge(x,y,w);
//addedge(y,x,0); //反向弧提供改错机会ISAP，仅一次BFS与多路增广，O(V^2*E)
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;
int dep[N],gap[N]; //gap[x]为等于x的dep[i]的个数
bool bfs(){ //记录dep和gap
fill(dep,dep+n,-1); dep[t]=0;
fill(gap,gap+n,0); gap[0]=1;
q=queue<int>(); q.push(t);
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];~i;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 flow){
int now,ans=0;
if(x==t)return flow;
for(int i=cur[x];~i;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(flow,a[i].w))){
a[i].w-=now;
a[i^1].w+=now;
ans+=now,flow-=now; //流量更新
if(flow==0)return ans;
}
}
gap[dep[x]]--;
if(gap[dep[x]]==0)dep[s]=n;
dep[x]++;
gap[dep[x]]++;
return ans;
}
void init(){ //ISAP的初始化
a.clear();
fill(head,head+n,-1);
}
int isap(){ //返回最大流
int ans=0;
if(bfs())
while(dep[s]<n){
copy(head,head+n,cur); //当前弧初始化
ans+=dfs(s,inf);
}
return ans;
}
//填加边(x,y)的方法
//addedge(x,y,w);
//addedge(y,x,0); //反向弧提供改错机会字符串
寻找模式p在文本t中的所有出现
KMP算法，前缀数组pi[]
pi[x]表示在前x个字符组成的字符串中
满足k!=x且前k个字符和后k个字符组成的字符串相等的k的最大值
求pi和kmp算法如下（字符串匹配同样可以用hash）
O(n)
void get_pi(){
pi[0]=0;
int k=0;
repeat(i,1,s.length()){
while(k>0 && s[i]!=s[k])
k=pi[k-1];
if(s[i]==s[k])
k++;
pi[i]=k;
}
}字符串匹配可以构造s=p+#+t
cin>>s1>>s2;
s=s2+' '+s1;
get_pi();
repeat(i,s2.size()+1,s.size())
if(pi[i]==s2.size())
cout<<i-2*s2.size()+1<<endl;Z函数，扩展kmp
z[x]表示原字符串与后(len-x)个字符组成的字符串中
满足它们的前k个字符组成的字符串相等的k的最大值
（即最大公共前缀长度）
z[0]是多少都无所谓
字符串匹配可以构造s=p+#+t
O(n)
void get_z(){
z[0]=0;
int l=0,r=0;
repeat(i,1,s.length()){
if(i<=r)
z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<s.length() && s[z[i]]==s[i+z[i]])
++z[i];
if(i+z[i]-1>r)
l=i,r=i+z[i]-1;
}
}字典树Trie
struct trie{
int a[1000001][26],top;
bool exist[1000001];
void init(){
top=1;
mst(a[0],0);
}
int add(){
mst(a[top],0);
exist[top]=0;
return top++;
}
void insert(const char *s){
int p=0;
for(int i=0;s[i];i++){
int c=s[i]-'a'; //小写字母
if(!a[p][c])a[p][c]=add();
p=a[p][c];
//son[p]++; //如果要记录子树大小
}
exist[p]=1;
}
bool find(const char *s){
int p=0;
for(int i=0;s[i];i++){
int c=s[i]-'a'; //小写字母
if(!a[p][c])return 0;
p=a[p][c];
}
return exist[p];
}
}t;马拉车Manacher
需要预处理，比如"12"->"%*1*2**"。O(n)
len[0]=0;
mx=0;
id=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;
//if(s[i]=='*')ans+=len[i]/2;
//else ans+=(len[i]-1)/2;
}
}杂项
位运算巨佬操作
中点向下取整(x+y)/2: (x & y) + ((x ^ y) >> 1)
中点向上取整(x+y+1)/2: (x | y) - ((x ^ y) >> 1)
//一般来说用x + (y - x >> 1)
abs(n): (n ^ (n >> 31)) - (n >> 31)
max(a,b): b & ((a - b) >> 31) | a & (~(a - b) >> 31)
min(a,b): a & ((a - b) >> 31) | b & (~(a - b) >> 31)
离散化
从小到大标号并赋值
//map版
void disc(int a[],int n){
map<int,int> m;
repeat(i,0,n)
m[a[i]]=0;
int cnt=0; //从1开始编号
for(auto i:m)
m[i.first]=++cnt;
repeat(i,0,n)
a[i]=m[a[i]];
}
//lower_bound版
void disc(int a[],int n){
vector<int> m(a,a+n);
sort(m.begin(),m.end());
m.erase(unique(m.begin(),m.end()),m.end());
repeat(i,0,n)
a[i]=lower_bound(m.begin(),m.end(),a[i])-m.begin(); //从0开始编号
}枚举二进制子集
枚举二进制数m的非空子集
for(int s=m;s;s=(s-1)&m){
work(s);
}枚举n个元素的大小为k的二进制子集
int s=(1<<k)-1;
while(s<1<<n){
work(s);
int x=s&-s,y=s+x;
s=((s&~y)/x>>1)|y; //这里有一个位反~
}质数表
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
NTT素数表， \(g\) 是模 \((r \cdot 2^k+1)\) 的原根
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快读快写
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<<3)+(x<<1)+(c^48);
return x*tag;
}
void write2(ll x) {
static int a[35];
int top=0;
do{a[top++]=x%10;}while(x/=10);
while(top)putchar(a[--top]+48);
}
void write(ll x){
if(x<0)x=-x,putchar('-');
if(x>=10)write(x/10);
putchar(x%10^48);
}主定理
对于 T(n)=aT(n/b)+n^k （要估算n^k的k值）
若 log(b,a)>k, 则 T(n)=O(n^log(b,a))
若 log(b,a)=k, 则 T(n)=O(n^k*log(n))
若 log(b,a)<k, （有省略） 则 T(n)=O(n^k)01分数规划
n个物品，都有两个属性a[i]和b[i]，任意取m个物品使它们的sum(a[j])/sum(b[j])最大
题解：二分答案
x是否满足条件即判断sum(a[j])/sum(b[j])>=x，即sum(a[j]-x*b[j])>=0
因此对{a[i]-x*b[i]}进行排序，取前k个最大值进行测试
求逆序数 | 归并排序
O(nlogn)
void merge(int l,int r){ //归并排序
//对[l,r-1]的数排序
if(r-l<=1)return;
int mid=l+(r-l>>1);
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];
}最大空矩阵 | 悬线法
求01矩阵中全是0的最大连续子矩阵（面积最大）O(nm)
此处障碍物是正方形。如果障碍只是一些整点，答案从a*b变为(a+1)*(b+1)
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;
}精确覆盖 | 舞蹈链
在01矩阵中找到某些行，它们两两不相交，且它们的并等于全集（也可以看作n个集合）
x[],y[]编号从1开始！O(指数)，节点数<5000
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;高维前缀和
（以二维为例）
法一O(n^t*2^t)（t是维数）
法二O(n^t*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];STL手写hash
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<int,int,custom_hash> m;模拟退火SA
以当前状态为中心，半径为温度的圆内选一个点
计算 d = 当前最优解减去当前解
如果小于 0 则直接状态转移
否则状态转移的概率是 exp(-k*d/t)
最后温度乘以降温系数，返回第一步
需要调 3 个参数：初始温度，终止温度，降温系数（？）
对拍
#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
operator<的比较内容一定要写完整
试一试输入^Z能否结束
无向图输入要给两个值赋值g[x][y]=g[x][y]=1
多组输入时，图记得初始化数学
[TOC]
数论基本操作
模乘法 | 龟速乘
//int128版本
ll slow(ll a,ll b,ll mod){return (__int128)a*b%mod;}
//每位运算一次版本
ll slow(ll a,ll b,ll mod){
ll ans=0;
while(b){
if(b&1)ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ans;
}
//把b分成两部分版本，要保证mod小于1<<42（约等于4e12），a,b<mod
ll slow(ll a,ll b,ll mod){
a%=mod,b%=mod;
ll l=a*(b>>21)%mod*(1ll<<21)%mod;
ll r=a*(b&(1ll<<21)-1)%mod;
return (l+r)%mod;
}最大公约数
__gcd(a,b) //推荐
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} //不推荐233裴蜀定理 | 扩展欧几里得
求ax+by=gcd(a,b)的一个解，d存gcd(a,b)
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b)d=a,x=1,y=0;
else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}快速幂
ll qpow(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod; //必要时slow
a=a*a%mod; //必要时slow
b>>=1;
}
return ans;
}单个乘法逆元
扩欧版
ll getinv(ll n,ll mod){
ll d,x,y;
exgcd(n,mod,d,x,y);
return (x%mod+mod)%mod;
}快速幂版
ll getinv(ll n,ll mod){ //mod必须必须是质数!!
return qpow(n,mod-2,mod);
}唯一分解
用数组表示数字唯一分解式的素数的指数，如50={1,0,2,0,…}
可以用来计算阶乘和乘除操作
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]++;
}set维护版
struct fac{
#define facN 1010
ll a[facN]; set<ll> s;
fac(){mst(a,0); s.clear();}
void lcm(ll n){ //求lcm(*this,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;单个欧拉函数
\(\varphi(n)=\)小于n且与n互质的正整数个数
令n的唯一分解式\(n=Π({p_k}^{a_k})\)，则\(\varphi(n)=n\cdot Π(1-\frac 1 {p_k})\)
O(sqrt(n))
int euler_phi(int n){
int m = int(sqrt(n+0.5));
int ans = n;
for(int i = 2; i <= m; i++)
if(n % i == 0){
ans = ans / i * (i-1);
while(n % i == 0)n /= i;
}
if(n > 1)ans = ans / n * (n-1);
return ans;
}素数判定
朴素算法，O(sqrt(n))
bool isprime(int n){
if(n<=3)return n>=2;
if(n%2==0 || n%3==0)return false;
repeat(i,1,int(sqrt(n)+1.5)/6+1)
if(n%(i*6-1)==0 || n%(i*6+1)==0)return false;
return true;
}Miller-Rabin素性测试，O(10*(logn)^3)
bool isprime(int n){
if(n<4)return n>1;
int a=n-1,b=0;
while(a%2==0)a/=2,++b;
repeat(i,0,10){
int x=rand()%(n-2)+2,v=qpow(x,a,n);
if(v==1 || v==n-1)continue;
repeat(j,0,b+1){
v=slow(v,v,n);
if(v==n-1)break;
}
if(v!=n-1)return 0;
}
return 1;
}大数分解 | Pollard-rho
O(n^(1/4))
//基于MR素性测试
ll pollard_rho(ll c,ll n){
ll i=1,x,y,k=2,d;
x=y=rand()%n;
do{
i++;
d=__gcd(n+y-x,n);
if(d>1 && d<n)
return d;
if(i==k)y=x,k*=2;
x=(slow(x,x,n)+n-c)%n;
}while(y!=x);
return n;
}
void rho(ll n){
if(isprime(n)){
ans.push_back(n);
return;
}
ll t;
do{t=pollard_rho(rand()%(n-1)+1,n);}while(t>=n);
rho(t);
rho(n/t);
return;
}反素数问题
求因数最多的数（因数个数一样则取最小）
抓住两个性质DFS
（之前先判断素数或者打表一下，算出p1...p16的值(2到53)）
质数表：int p[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
\(M = {p_1}^{k_1} * {p_2}^{k_2} * ...\)
其中，\(p_1,p_2,...\)是从2开始的连续质数
DFS时，枚举\(k_n\)，可行性剪枝
数论分块
\(n=(k-n\%k)(n/k)+(n\%k)(n/k+1)\)
将 \(\lfloor \frac{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 \frac{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;
}筛法
筛素数
O(n)
//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的最小质因数
}
}
}筛欧拉函数
线性版，O(n)
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);
}
}
}不是线性但节省力气和空间版，O(nloglogn)
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);
}
}筛莫比乌斯函数
O(n)
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];
}
}
}杜教筛
\(S(n)=\sum_{i=1}^nf(i)\)
由公式
\(\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac i d)=\sum_{i=1}^n g(i)S(\lfloor\frac n i \rfloor)\)
右式拿出一项得
\(g(1)S(n)=\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac i d)-\sum_{i=2}^n g(i)S(\lfloor\frac n i \rfloor)\)
//目前只有mu的杜教筛
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;线性递推
线性递推乘法逆元
求1..(n-1)的逆元，O(n)
void get_inv(int n){
inv[1]=1;
repeat(i,2,n)
inv[i]=mod-mod/i*inv[mod%i]%mod;
}求a[1..n]的逆元，离线，O(n)
void get_inv(int a[],int n){//求a[1..n]的逆元，存在inv[1..n]中
static int pre[N]={1};
repeat(i,1,n+1)
pre[i]=1ll*pre[i-1]*a[i]%mod;
int inv_pre=qpow(pre[n],mod-2);
repeat_back(i,1,n+1){
inv[i]=1ll*pre[i-1]*inv_pre%mod;
inv_pre=1ll*inv_pre*a[i]%mod;
}
}线性递推组合数
O(n)初始化，O(1)查询
int C(int a,int b){ //a>=b
return fac[a]*fac_inv[a-b]%mod*fac_inv[b]%mod;
}
void init(){
fac[0]=1;
repeat(i,1,N)fac[i]=fac[i-1]*i%mod;
fac_inv[N-1]=qpow(fac[N-1],mod-2);
repeat_back(i,0,N-1)fac_inv[i]=fac_inv[i+1]*(i+1)%mod;
}线性递推二项式系数
C(n,k)=(n-k+1)*C(n,k-1)/k
高级模运算
线性同余方程组 | 中国剩余定理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=getinv(k%m[i],m[i]); //扩欧!!
ans=(ans+a[i]*k*t)%M; //两个乘号可能都要slow
}
return (ans+M)%M;
}
//exCRT，m[i]不需要两两互质，基于扩欧exgcd和龟速乘slow
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;
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+=slow(x,c/g,m[i]/g)*M; //龟速乘
M*=m[i]/g;
ans=(ans%M+M)%M;
}
return (ans+M)%M;
}指标or离散对数 | 大步小步BSGS+extra
求 \(a^x \equiv b \pmod m\) ，O(sqrt(m))
//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[slow(b,p,mod)]=i; //p==a^i
p=slow(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=slow(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=slow(c,a/g,mod);
ans++;
if(b==c)return ans;
}
ll t=bsgs(a,slow(b,getinv(c,mod),mod),mod); //必须扩欧逆元!!
if(t==-1)return -1;
return t+ans;
}阶与原根
判断是否有原根：若 \(m\) 有原根，则 \(m\) 一定是下列形式：\(2,4,p^a,2p^a\)（ \(p\) 是奇素数， \(a\) 是正整数）
求所有原根：若 \(g\) 为 \(m\) 的一个原根，则 \(g^s\space(1\le s\le\varphi(m),\gcd(s,\varphi(m))=1)\) 给出了 \(m\) 的所有原根。因此若 \(m\) 有原根，则 \(m\) 有 \(\varphi(\varphi(m))\) 个原根
求一个原根，O(nloglogn)实际远远不到
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=true;
for(auto j:a)
if(qpow(i,(n-1)/j,n)==1){
f=false;
break;
}
if(f)return i;
}
}N次剩余
求 \(x^a \equiv b \pmod m\) ，基于BSGS、原根
//只求一个
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=slow(now,ps,mod))
ans.push_back(now);
sort(ans.begin(),ans.end());
}二次剩余
对于奇素数模数 \(p\)，存在 \(\frac {p-1} 2\) 个二次剩余 \(\{1^2,2^2,...,(\frac {p-1} 2)^2\}\)，和相同数量的二次非剩余
对于奇素数模数 \(p\)，如果 \(n^{\frac{p-1}2}\equiv1\pmod{p}\) ，则 \(n\) 是一个二次剩余；如果 \(n^{\frac{p-1}2}\equiv-1\pmod{p}\)，则 \(n\) 是一个二次非剩余
对于奇素数模数 \(p\)，二次剩余的乘积是二次剩余，二次剩余与非二次剩余乘积为非二次剩余，非二次剩余乘积是二次剩余
费马-欧拉素数定理：\((4n+1)\) 型素数只能用一种方法表示为一个范数（两个完全平方数之和），\((4n+3)\) 型素数不能表示为一个范数
二次互反率：记 \(p^{\frac{q-1}2}\) 的符号为 \((\frac p q)\) ，则对奇素数 \(p,q\) 有 \((\frac p q)\cdot(\frac q p)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}\)
特殊函数
莫比乌斯反演
记\([P]=\left\{\begin{array}{} 1&命题P为真\\0&命题P为假\end{array}\right.\)
引理1：\(\lfloor \frac{a}{bc}\rfloor=\lfloor \frac{\lfloor \frac{a}{b}\rfloor}{c}\rfloor\)
引理2：\(n\) 的因数个数 \(≤\lfloor 2\sqrt n \rfloor\)
数论分块：将 \(\lfloor \frac{n}{x}\rfloor=C\) 的 \([x_{\min},x_{\max}]\) 作为一块，其中区间内的任一整数 \(x_0\) 满足 \(x_{\max}=\lfloor\frac n{\lfloor\frac n x\rfloor}\rfloor\)
def-积性函数：\(\gcd(x,y)=1\Rightarrow f(xy)=f(x)f(y)\)
def-单位函数：\(\varepsilon(n)=[n=1]\)
def-恒等函数：\(id(n)=n\)
def-狄利克雷Dirichlet卷积：\((f*g)(n)=\sum_{d|n}f(d)g(\frac n d)\)
\(\varepsilon\) 为狄利克雷卷积的单位元
莫比乌斯函数性质：\(\mu(n)=\left\{\begin{array}{} 1&n=1\\0&n含有平方因子\\(-1)^k&k为n的本质不同质因数个数\end{array}\right.\)
莫比乌斯函数是积性函数
超级重要结论：\(\varepsilon=\mu*1\)，即\(\varepsilon(n)=\sum_{d|n}\mu(d)\)
莫比乌斯反演公式：若\(f=g*1\)，则\(g=f*\mu\)；或者，若\(f(n)=\sum_{d|n}g(d)\)，则\(g(n)=\sum_{d|n}\mu(d)f(\frac n d)\)
（补充）欧拉函数性质：\(\varphi*1=id\)
例题：求模意义下的 \(\sum_{i=1}^n \sum_{j=1}^m \frac{i\cdot j}{\gcd(i,j)}\)
\(ans=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j,\gcd(\frac i d,\frac j d)=1}\frac{i\cdot j}d\)
非常经典的化法：
\(ans=\sum_{d=1}^n d\cdot\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1]i\cdot j\)
设 \(sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1]i\cdot j\)
\(sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{c|i,c|j}{\mu(c)}\cdot i\cdot j\)
设 \(i'=\frac i c,j'=\frac j c\)
\(sum(n,m)=\sum_{c=1}^n\mu(c)\cdot c^2\cdot\sum_{i'=1}^{\lfloor\frac nc\rfloor}\sum_{j'=1}^{\lfloor\frac mc\rfloor} i'\cdot j'\)
易得 \(\sum_{i=1}^{n}\sum_{j=1}^{m} i\cdot j=\frac 1 4 n(n+1) m(m+1)\)
斐波那契数列
定义：\(F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}\)
\(F_n=\frac 1 {\sqrt{5}} [(\frac 1 \Phi)^n-(-\Phi)^n)]\)
\(F_{a+b-1}=F_{a-1}F_{b-1}+F_aF_b\) （重要公式）
\(F_{n-1}F_{n+1}-F_n^2=(-1)^n\) （卡西尼性质）
\(F_{n}^2+F_{n+1}^2=F_{2n+1}\)
\(F_{n+1}^2-F_{n-1}^2=F_{2n}\) （由上一条写两遍相减得到）
\(F_1+F_3+F_5+...+F_{2n-1}=F_{2n}\) （奇数项求和）
\(F_2+F_4+F_6+...+F_{2n}=F_{2n+1}-1\) （偶数项求和）
\(F_1^2+F_2^2+F_3^2+...+F_n^2=F_nF_{n+1}\)
\(F_1+2F_2+3F_3+...+nF_n=nF_{n+2}-F_{n+3}+2\)
\(-F_1+F_2-F_3+...+(-1)^nF_n=(-1)^n(F_{n+1}-F_n)+1\)
\(F_{2n-2m-2}(F_{2n}+F_{2n+2})=F_{2m+2}+F_{4n-2m}\)
\(F_a \mid F_b \Leftrightarrow a \mid b\)
\(\gcd(F_a,F_b)=F_{\gcd(a,b)}\)
当 \(p\) 为 \(5k\pm 1\) 型素数时，\(\left\{\begin{array}{} F_{p-1}\equiv 0\pmod p \\ F_p\equiv 1\pmod p \\ F_{p+1}\equiv 1\pmod p \end{array}\right.\)
当 \(p\) 为 \(5k\pm 2\) 型素数时，\(\left\{\begin{array}{} F_{p-1}\equiv 1\pmod p \\ F_p\equiv -1\pmod p \\ F_{p+1}\equiv 0\pmod p \end{array}\right.\)
\(F_{n+2}\) 为集合 {1,2,3,...,n-2} 中不包含相邻正整数的子集个数（包括空集）
F(n)%m 的周期 \(\le 6m\) （ \(m=2\times 5^k\) 取等号）
快速倍增法求\(F_n\)，返回二元组\((F_n,F_{n+1})\) ，O(logn)
pii fib(ll n){ //fib(n).first
if(n==0)return {0,1};
pii p=fib(n>>1);
ll a=p.first,b=p.second;
ll c=a*(2*b-a);
ll d=a*a+b*b;
if(n&1)return {d,c+d};
else return {c,d};
}排列组合
组合数取模 | 卢卡斯定理Lucas+extra
卢卡斯定理用来求模意义下的组合数
//Lucas，p是质数
ll lucas(ll a,ll b,ll p){
if(b==0)return 1;
return slow(c(a%p,b%p,p),lucas(a/p,b/p,p),p);
}
//exLucas，p不需要是质数
//空缺编码与解码
（多重集康托展开与逆展开）
<1>
给定一个字符串，求出它的编号
例，输入acab，输出5（aabc,aacb,abac,abca,acab,...）
用递归，令d(S)是小于S的排列数，f(S)是S的全排列数
小于acab的第一个字母只能是a，所以d(acab)=d(cab)
第二个字母是a,b,c，所以d(acab)=f(bc)+f(ac)+d(ab)
d(ab)=0
因此d(acab)=4，加1之后就是答案
<2>
给定编号求字符串，对每一位进行尝试即可
康托展开Cantor+逆
排列里的元素都是从1到n
//普通版，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;
}浮点数误差分析
const lf err=1e-7;
#define iszero(x) (fabs(x)<err)
#define less(x,y) (x+err<y)
#define greater(x,y) (x>y+err)博弈论
SG定理
有向无环图中，两个玩家轮流推一个棋子，不能走的判负
假设x的k个后继状态{yi}
SG(x)=mex{SG(yi)}，mex(S)=不属于集合S的最小自然数
当且仅当XOR{SG(起点1),SG(起点2),...}为0时先手必败
（如果只有一个起点，SG的值可以只考虑01）
例题：拿n堆石子，每次只能拿一堆中的斐波那契数颗石子
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
n堆石子，分别有ai颗石子
两人每次可以拿任意堆任意非空的石子，拿不了的人判负
解：NimSum=XOR{ai}，当且仅当NimSum为0时先手必败（SG证）
注：先手必胜策略是找到任意第(63-__builtin_clzll(NimSum))位是1的a[i]，并取走a[i]^NimSum个石子
Nimk
每次最多选取k堆石子，选中的每一堆都取走任意非空的石子
解：当且仅当下述命题成立，先手必胜
存在t使得sum(ai & (1<<t))%(k+1)!=0
多项式
拉格朗日插值
函数曲线通过n个点(xi,yi)，求f(k)
拉格朗日插值：f(x)=sum(i,1,n){yi*PI(j!=i)(x-xj)/(xi-xj)}
O(n^2)
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)%mod;
}
ans=(ans+s1*getinv(s2)%mod+mod)%mod;
}快速傅里叶变换FFT
求两个多项式的卷积，O(nlogn)
struct cf{
lf x,y;
cf(lf x=0,lf y=0):x(x),y(y){};
cf operator+(cf b){return cf(x+b.x,y+b.y);}
cf operator-(cf b){return cf(x-b.x,y-b.y);}
cf operator*(cf b){return cf(x*b.x-y*b.y,x*b.y+y*b.x);}
};
//或者#define cf complex<lf>，输出的x改成real()
const lf pi=acos(-1);
void fft(cf *a,int n,int f){ //n为2^k，f为正负1，结果存在a
static int rev[N];
int bit=0;
while((1<<bit)<n)bit++;
repeat(i,0,n){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(int mid=1;mid<n;mid*=2){
cf t(cos(pi/mid),f*sin(pi/mid));
for(int i=0;i<n;i+=mid*2){
cf om(1,0);
for(int j=0;j<mid;j++,om=om*t){
cf x=a[i+j],y=om*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
cf a[N],b[N];
int c[N];
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n=1048576*2,na=read(),nb=read();
repeat(i,0,na+1)a[i]=cf(read(),0);
repeat(i,0,nb+1)b[i]=cf(read(),0);
fft(a,n,1),fft(b,n,1);
repeat(i,0,n)a[i]=a[i]*b[i];
fft(a,n,-1);
repeat(i,0,n)c[i]=llround(a[i].x/n);
repeat(i,0,na+nb+1)printf("%d ",c[i]);
return 0;
}线性代数
矩阵乘法、矩阵快速幂
struct matrix{
#define M 8
ll m[M][M];
matrix(int e=0){
mst(m,0);
repeat(i,0,M)
m[i][i]=e;
}
matrix operator*(matrix &b)const{ //矩阵乘法
matrix ans;
repeat(i,0,M)
repeat(j,0,M){
ll &t=ans.m[i][j];
repeat(k,0,M)
t=(t+m[i][k]*b.m[k][j])%mod;
}
return ans;
}
};
matrix qpow(matrix a,ll b){ //矩阵快速幂
matrix ans(1);
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}矩阵高级操作
struct matrix{
#define iszero(x) (fabs(x)<err)
static const int N=110;
//int n,m;
lf a[N][N];
lf det;
void r_swap(int x,int y){ //交换第x行和第y行
repeat(i,0,m)
swap(a[x][i],a[y][i]);
det=-det;
}
void r_mul(int x,lf k){ //第x行乘以实数k
repeat(i,0,m) //从x开始也没太大关系（对高斯消元来说）
a[x][i]*=k;
det/=k;
}
void r_plus(int x,int y,lf k){ //第x行加上第y行的k倍
repeat(i,0,m)
a[x][i]+=a[y][i]*k;
}
bool gauss(){ //高斯消元，返回是否满秩
det=1;
repeat(i,0,n){
int t=-1;
repeat(j,i,n)
if(!iszero(a[j][i])){
t=j;
break;
}
if(t==-1){det=0; return false;}
if(t!=i)r_swap(i,t);
r_mul(i,1/a[i][i]);
repeat(j,0,n) //如果只要det可以从i+1开始
if(j!=i && !iszero(a[j][i]))
r_plus(j,i,-a[j][i]);
}
return true;
}
lf get_det(){ //返回行列式
gauss();
return det;
}
bool get_inv(){ //把自己变成逆矩阵，返回是否成功
if(n!=m)return false;
repeat(i,0,n)
repeat(j,0,n)
a[i][j+n]=i==j; //生成
m=2*n;
bool t=gauss();
m=n;
repeat(i,0,n)
repeat(j,0,n)
a[i][j]=a[i][j+n];
return t;
}
};矩阵的一些结论
\(n\times n\)方阵\(A\)有：\(\left[\begin{array}{c}A&E\\O&E\end{array}\right]^{k+1}=\left[\begin{array}{c}A^k&E+A+A^2+...+A^k\\O&E\end{array}\right]\)
线性基
插入、查询最大值、查询是否存在O(logn)，查询第k小O((logn)^2)
struct basis{
#define n 63
ll a[n];
basis(){mst(a,0);}
void insert(ll x){ //插入元素
repeat_back(i,0,n)
if((x>>i)&1)
if(a[i]==0){
a[i]=x;
return;
}
else x^=a[i];
}
ll top(){ //最大值
ll ans=0;
repeat_back(i,0,n)
ans=max(ans,ans^a[i]);
return ans;
}
bool exist(ll x){ //是否存在
repeat_back(i,0,n)
if((x>>i)&1)
if(a[i]==0){
return false;
}
else x^=a[i];
return true;
}
void rebuild(){ //求第k小的前置操作
repeat_back(i,0,n)
repeat_back(j,0,i)
if((a[i]>>j)&1)
a[i]^=a[j];
}
ll kth(ll k){ //第k小
ll ans=0;
rebuild();
repeat(i,0,n)
if(a[i]!=0){
if(k&1==1)ans^=a[i];
k>>=1;
}
return ans;
}
#undef n
};数学杂项
约瑟夫问题
n个人编号0..(n-1)，每次数到k出局，求最后剩下的人的编号
线性算法，O(n)
int jos(int n,int k){
int res=0;
repeat(i,1,n+1)res=(res+k)%i;
return res; //res+1，如果编号从1开始
}对数算法，适用于k较小情况，O(klogn)
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开始
}格雷码和汉诺塔
格雷码
一些性质：
相邻格雷码只变化一次
grey(n-1)到grey(n)修改了二进制的第(__builtin_ctzll(n)+1)位
grey(0)..grey(2\*\*k-1)是k维超立方体顶点的哈密顿回路，其中格雷码每一位代表一个维度的坐标
格雷码变换，正O(1)，逆O(logn)
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;
}汉诺塔
假设盘数为n，总共需要移动 (1<<n)-1 次
第k次移动第 i=__builtin_ctzll(n)+1 小的盘子
该盘是第 (k>>i)+1 次移动
（可以算出其他盘的状态：总共移动了 ((k+(1<<(i-1)))>>i) 次）
该盘的移动顺序是：
A->C->B->A（当i和n奇偶性相同）
A->B->C->A（当i和n奇偶性不同）
char ch[4]="ABC";
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<<": "<<ch[p1]<<" -> "<<ch[p2]<<endl;
}置换群计数
Polya定理
例：立方体 \(n=6\) 个面，每个面染上 \(m=3\) 种颜色中的一种
两个染色方案相同意味着两个立方体经过旋转可以重合
其染色方案数为：\(\frac{\sum m^{k_i}}{|k|}\)
\(k_i\)为某一置换可以拆分的循环置换数
\(|k|\)为所有置换数
不旋转，{U|D|L|R|F|B}，k=6，共1个k
对面中心连线为轴的90度旋转，{U|D|L R F B}，k=3，共6个k
对面中心连线为轴的180度旋转，{U|D|L R|F B}，k=4，共3个k
对棱中点连线为轴的180度旋转，{U L|D R|F B}，k=3，共6个k
对顶点连线为轴的120度旋转，{U L F|D R B}，k=2，共8个k因此 \(\frac{3^6+3^3 \cdot 6+3^4 \cdot 3+3^3 \cdot 6+3^2 \cdot 8}{1+6+3+6+8}=57\)
例题（poj1286），n个点连成环，染3种颜色，允许旋转和翻转
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;一些简单的数学结论
三个水杯容量为a,b,c（正整数），a=b+c且a装满水，得到容积为a/2的水需要倒a/gcd(b,c)-1次水
兰顿蚂蚁（白色异或右转，黑色异或左转），约一万步后出现周期为104步的无限重复（高速公路）
埃及分数Engel展开：令 \(u_1=x,u_{n+1}=u_n\times\lceil\frac 1 {u_n}\rceil-1\)（到0为止）\(a_n=\lceil\frac 1 {u_n}\rceil\) \(x=\frac 1{a_1}+\frac 1{a_1a_2}+\frac 1{a_1a_2a_3}+...\)
一个长为n+m的数组，n个1，m个-1，前缀和最大为k，则可能的数组有\(C_{n+m}^{m+k}-C_{n+m}^{m+k+1}\)
若要让点 \(p=xi+yj+zk\) 绕轴 \(l=ai+bj+ck\)（单位向量）转 \(\theta\) 弧度，可以让 \(p\) 左乘 \(q=\cos\frac \theta 2+(ai+bj+ck)\sin\frac \theta 2\)，右乘 \(q^{-1}=\cos\frac \theta 2-(ai+bj+ck)\sin\frac \theta 2\) （四元数的性质）
任意勾股数能由复数 \((a+bi)^2\space(a,b∈\Z)\) 得到
牛顿迭代：\(x_{n+1}=x_n-\frac{f(x)}{f'(x)}\)（求 \(f(x)\) 的零点）
检验 \(x_{n+1}=f(x_n)\) 多次迭代可以收敛于 \(x_0\) 的方法：看 \(|f'(x_0)|\le1\) 是否成立
任意正整数 \(a\) 都存在正整数 \(b,c\) 使得 \(a<b<c\) 且 \(a^2,b^2,c^2\) 成等差数列：构造 \(b=5a,c=7a\)
\(\lim\limits_{n\rightarrow\infty}\frac{错排(n)}{n!}=\frac 1 e,e\approx 2.718281828459045235360287471352\)
\(\lim\limits_{n\rightarrow\infty}(\sum\frac 1 n-\ln n)=\gamma\approx 0.577215664901532860606\)
任意有理数 \(a\) 可以写成三个有理数的立方和 \(a=(\frac{a^3-3^6}{3^2a^2+3^4a+3^6})^3+(\frac{-a^3+3^5a+3^6}{3^2a^2+3^4a+3^6})^3+(\frac{3^3a^2+3^5a}{3^2a^2+3^4a+3^6})^3\)
四面体体积公式（\(a\) 与 \(a_1\) 是对棱）
\(V^2=\frac 1 {288} \left|\left|\begin{array}{c} 0&a^2&b^2&c^2&1\\ a^2&0&c_1^2&b_1^2&1\\ b^2&c_1^2&0&a_1^2&1\\ c^2&b_1^2&a_1^2&0&1\\ 1&1&1&1&0\\ \end{array}\right|\right|\)
