• 語法
  • C++11
    • 初始代碼
    • 如果沒有萬能頭
    • 容器
    • 其他語法
    • 神奇特性
  • Java
  • python3
• 常規演算法
  • 演算法基礎
  • 離散化
  • 01分數規劃
  • 任務規劃 | Livshits-Kladov定理
  • 分治
    • 逆序數×二維偏序
  • 最大空矩陣 | 懸線法
  • 搜索
    • 舞蹈鏈×DLX
    • 啟發式演算法
  • 動態規劃
    • 多重背包
    • 最長不降子序列×LIS
    • 數位dp
    • 換根dp
    • 斜率優化
    • 四邊形優化
• 計算幾何
  • struct of 向量
  • 平面幾何基本操作
    • 判斷兩條線段是否相交
    • others of 平面幾何基本操作
  • 二維凸包
  • 旋轉卡殼
  • 最大空矩形 | 掃描法
  • 平面最近點對 | 分治
  • 最小圓覆寫 | 隨機增量法×RIA
  • 半面交 | S&I演算法
  • Delaunay三角剖分
  • struct of 三維向量
  • 球面幾何
  • 三維凸包
  • 計算幾何雜項
    • 正冪反演
    • others of 計算幾何雜項
• 資料結構
  • st表
    • <補充>貓樹
  • 單調佇列
  • 樹狀陣列
  • 線段樹
    • <補充>權值線段樹（動態開點 線段樹合并 線段樹分裂）
    • <補充>zkw線段樹
    • <補充>可持久化陣列
    • <補充>李超線段樹
  • 并查集
    • <補充>種類并查集
    • <補充>可持久化并查集
  • 左偏樹
  • 珂朵莉樹×老司機樹
  • K-D tree
  • 劃分樹
  • 莫隊
  • 二叉搜索樹
    • 不平衡的二叉搜索樹
    • 無旋treap
    • <補充> 可持久化treap
  • 一些建議
• 圖論
  • 圖論的一些概念
  • 圖論基礎
    • 前向星
    • 拓撲排序×Toposort
    • 歐拉路徑 歐拉回路
    • dfs樹 bfs樹
  • 最短路徑
    • Dijkstra
    • Floyd
    • SPFA
    • Johnson
    • 最小環
  • 最小生成樹×MST
    • Kruskal
    • Boruvka
    • 最小樹形圖 | 朱劉演算法
  • 樹論
    • 樹的直徑
    • 樹的重心
    • 最近公共祖先×LCA
      • 樹上倍增解法
      • 歐拉序列+st表解法
      • 樹鏈剖分解法
      • Tarjan解法
      • 一些關于lca的問題
    • 樹鏈剖分
    • 樹分治
      • 點分治
  • 聯通性相關
    • 強聯通分量scc+縮點 | Tarjan
    • 邊雙連通分量 | Tarjan
    • 割點×割頂
  • 2-sat問題
  • 支配樹 | Lengauer?Tarjan演算法
  • 圖上的NP問題
    • 最大團+極大團計數
    • 最小染色數
  • 弦圖+區間圖
  • 仙人掌 | 圓方樹
  • 二分圖
    • 二分圖的一些概念
    • 二分圖匹配×最大匹配
    • 最大權匹配 | KM
    • 穩定婚姻 | 延遲認可
    • 一般圖最大匹配 | 帶花樹
  • 網路流
    • 網路流的一些概念
    • 最大流
      • Dinic
      • ISAP
    • 最小費用最大流 | MCMF
  • 圖論雜項
    • 矩陣樹定理
    • Prufer序列
    • LGV引理
    • others of 圖論雜項
• 字串
  • 哈希×Hash
    • 字串哈希
    • 質因數哈希
  • 字串函式
    • 前綴函式×kmp
    • z函式×exkmp
    • 馬拉車×Manacher
    • 最小表示法
    • 后綴陣列×SA
    • height陣列
  • 自動機
    • 字典樹×Trie
    • AC自動機
    • 后綴自動機×SAM
• 雜項
  • 位運算
    • 位運算函式
    • 列舉二進制子集
  • 浮點數
  • 常數優化
    • 快讀快寫
    • STL手寫記憶體分配器
  • 在TLE邊緣試探
  • 對拍
  • 戰術分析 坑點
• 數學
  • 數論
    • 基本操作
      • 模乘 模冪 模逆 擴歐
      • 階乘 組合數
      • 防爆模乘
      • 最大公約數
    • 高級模操作
      • 同余方程組 | CRT+extra
      • 離散對數 | BSGS+extra
      • 階與原根
      • N次剩余
    • 數論函式的生成
      • 單個歐拉函式
      • 線性遞推乘法逆元
      • 線性篩
        • 篩素數
        • 篩歐拉函式
        • 篩莫比烏斯函式
        • 篩其他函式
      • min_25篩
    • 素數約數相關
      • 唯一分解 質因數分解
      • 素數判定 | 樸素 or Miller-Rabin
      • 大數分解 | Pollard-rho
      • 單個約數個數函式
      • 反素數生成
    • 數論雜項
      • 數論分塊
      • 二次剩余
      • 莫比烏斯反演
      • 杜教篩
      • 斐波那契數列
      • 佩爾方程×Pell
  • 組合數學
    • 組合數取模 | Lucas+extra
    • 康托展開+逆 編碼與解碼
    • 置換群計數
    • 組合數學的一些結論
  • 博弈論
    • SG函式 SG定理
    • Nim游戲
    • 刪邊游戲×Green Hachenbush
    • 翻硬幣游戲
    • 高維組合游戲 | Nim積
    • 不平等博弈 | 超現實數
    • 其他博弈結論
  • 代數結構
    • 置換群
    • 多項式
      • 拉格朗日插值
      • 快速傅里葉變換+任意模數
      • 多項式的一些概念
    • 矩陣
      • 矩陣乘法 矩陣快速冪
      • 矩陣高級操作
      • 異或方程組
      • 線性基
      • 線性規劃 | 單純形法
      • 矩陣的一些結論
  • 數學雜項
    • 主定理
    • 質數表
    • struct of 自動取模
    • struct of 高精度
    • 運算式求值
    • 一些數學結論
      • 約瑟夫問題
      • 格雷碼 漢諾塔
      • Stern-Brocot樹 Farey序列
      • 浮點與近似計算
      • others of 數學雜項

語法

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 fi first
#define se second
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; 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; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;} typedef pair<ll,ll> pii; template<typename T> void operator<<(vector<T> &a,T b){a.push_back(b);}
const ll 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;}
#define int ll
void Solve(){
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}

放在本地的內容（比如可以放進 bits/stdc++.h）（當然修改了頭檔案還要編譯一下）

template<typename A,typename B>
std::ostream &operator<<(std::ostream &o,const std::pair<A,B> &x){
	return o<<'('<<x.first<<','<<x.second<<')';
}
#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 pause [&]{system("pause");}()

如果沒有萬能頭

#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>

其他定義

#pragma GCC optimize(2) //(3),("Ofast")
#define lll __int128
#define inline __inline __attribute__((always_inline))
//struct name{bool operator()(const type &x,const type &y){return func(x,y);}}
#define vector basic_string
#define sortunique(a) ({sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end());})
#define gets(s) (getchar(),scanf("%[^\n]",s)+1)
template<typename T> T sqr(const T &x){return x*x;}
typedef long double lf;
template<typename A,typename B>void operator<<(A &a,B b){a.push_back(b);}
#define endl "\n"

容器

平板電視紅黑樹

#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

平板電視優先佇列

• pairing_heap_tag 配對堆，應該是可并堆里最快的
• thin_heap_tag 斐波那契堆
• std::priority_queue 不合并就很快

#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); //區間賦值到x
r.replace(pos,x); //相當于r[pos]=x;
r.substr(pos,len); //這是啥不會用
r[pos] //只能訪問不能修改
r.clear();
rope<int> *his[N]; his[0]=new rope<int>(); his[i]=new rope<int>(*his[i-1]); //據說O(1)拷貝，一行可持久化

其他語法

STL

a=move(b); //容器移動（a賦值為b，b清空）
priority_queue<int>(begin,end) //O(n)建堆

a.find(key) //set,map查找，沒找到回傳a.end()
a.lower_bound(key) //set,map限制最小值
a.insert(b.begin(),b.end()); //set,map合并（時間復雜度極高）

complex<lf> c; complex<lf> c(1,2);//復數
c.real(),c.imag() //實部、虛部

bitset<32> b; //宣告一個32位的bitset
b[n]; b[n]=1; //訪問和修改
b.none(); //回傳是否為空
b.count(); //回傳1的個數
b.to_ullong(); b.to_string(); //轉換

unordered容器手寫hash

struct myhash{
	typedef unsigned long long ull;
	ull f(ull x)const{
		x+=0x321354564536; //亂敲
		x=(x^(x>>30))*0x3212132123; //亂敲
		return x^(x>>31);
	}
	ull operator()(pii x)const{
		static ull t=chrono::steady_clock::now().time_since_epoch().count();
		return f(x.fi+t)^f(x.se+t*2);
	}
};
unordered_set<pii,myhash> a;

cmath

fmod(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]"); //也是遇到非小寫字母停止，只不過不讀入字串

神奇特性

• 命名空間rel_ops：之后只定義小于就能用其他所有次序關系符號
• raw strings：R"(abc\n)" 相當于 "abc\\n"
• 定義數字開頭的變數：type operator ""_name(type number){/*...*/}（之后 1_name 即把1帶入上述函式中，引數型別只能是ull,llf,char,(const char *,size_t)）
• 高級宏：__VA_ARGS__是引數串列(對應...)，__LINE__ 是當前行數，__FUNCTION__是當前函式名，__COUNTER__是宏展開次數-1
• 位域：struct{int a:3;}; 表示struct里a占3 bit，可以節省空間
• %n：scanf,printf 中 %n 將讀入/輸出的字符個數寫入變數

Java

import java.util.*;
import java.math.BigInteger;
import java.math.BigDecimal;
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,String

• final double PI=3.14; //final => (c++) const
• var n=1; //var => (c++) auto
• long 型常量結尾加 L，如 1L

陣列

int[] arr=new int[100]; //陣列
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); //格式化

輸入

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) //回傳是否相等
s1.compareTo(s2) //s1>s2回傳1，s1<s2回傳-1，s1==s2回傳0
s1.contains(s2) //回傳是否包含子串s2
s1.indexOf(s2,begin=0) //回傳子串位置
s1.substring(2,4) //回傳子串，首末坐標[2,4)
s1.charAt(3) //回傳第4個字符，就像c++的s1[3]
s1.length() //回傳長度
s1+s2 //回傳連接結果
String.format("%d",n) //回傳格式化結果

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)

BigInteger

import java.math.BigInteger;
BigInteger n=new BigInteger("0");
BigInteger[] arr=new BigInteger[10];
n1.intValue() //轉換為int
n1.longValue() //轉換
n1.doubleValue() //轉換
n1.add(n2) //加法
n1.subtract(n2) //減法
n1.multiply(n2) //乘法
n1.divide(n2) //除法
n1.mod(n2) //取模
BigInteger.valueOf(I) //int轉換為BigInteger
n1.compareTo(n2) //n1>n2回傳1，n1<n2回傳-1，n1==n2回傳0
n1.abs()
n1.pow(I)
n1.toString(I) //回傳I進制字串
//運算時n2一定要轉換成BigInteger

BigDecimal

import java.math.BigDecimal;
n1.divide(n2,2,BigDecimal.ROUND_HALF_UP) //保留兩位（四舍五入）
//貌似沒有sqrt等操作，都得自己實作qwq

python3

eval 運算式求值

常規演算法

演算法基礎

• STL自帶演算法

fill(begin,end,element); //填充
fill_n(begin,n,element); //填充
iota(begin,end,t); //遞增填充（賦值為t,t+1,t+2,...）
copy(a_begin,a_end,b_begin); //復制（注意會復制到b里）
reverse(begin,end); //翻轉

nth_element(begin,begin+k,end); //將第k+1小置于位置k，平均O(n)
binary_search(begin,end,key,[less]) //回傳是否存在
upper_bound(begin,end,key,[less]) //回傳限制最小值地址
lower_bound(begin,end,key,[less]) //回傳嚴格限制最小值地址
merge(a_begin,a_end,b_begin,b_end,c_begin,[less]); //歸并a和b（結果存c）
inplace_merge(begin,begin+k,end); //歸并（原地保存）
next_permutation(begin,end); prev_permutation(begin,end); //允許多重集，回傳不到底，使用方法 do{/*...*/}while(next_permutation(begin,end));
min_element(begin,end); max_element(begin,end); //回傳最值的指標
for_each(begin,end,work); //每個元素進行work操作

auto it=back_inserter(a); //it=x表示往a.push_back(x)

• 進制轉換

strtol(str,0,base),strtoll //回傳字符陣列的base進制數
stol(s,0,base),stoll //回傳字串的base進制數
sscanf,sprintf //十進制
to_string(n) //十進制

• 亂數

#include<random>
mt19937 rnd(time(0));
//巨佬定義：mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<rnd()<<endl; //范圍是unsigned int
rnd.max() //回傳最大值
lf rndf(){return rnd()*1.0/rnd.max();}
lf rndf2(){return rndf()*2-1;}

• 手寫二分/三分

while(l<=r){
	int mid=(l+r)/2; //l+(r-l)/2
	if(ok(mid))l=m+1; else r=m-1; //小的值容易ok
}
//此時r是ok的右邊界

while(l<r){
	int x=(l+r)/2,y=x+1; //l+(r-l)/2
	if(work(x)<work(y))l=x+1; else r=y-1; //最大值
}
//此時l和r均為極值點

#define f(x) (-x*x+23*x)
const lf ph=(sqrt(5)-1)/2; //0.618
lf dfs(lf l,lf x,lf r,lf fx){
	if(abs(l-r)<1e-9)return x;
	lf y=l+ph*(r-l),fy=f(y);
	if(fx<fy)return dfs(x,y,r,fy);
	else return dfs(y,x,l,fx);
}
lf search(lf l,lf r){
	lf x=r-ph*(r-l);
	return dfs(l,x,r,f(x));
}

• 次大值

int m1=-inf,m2=-inf;
repeat(i,0,n){m1=max(m1,a[i]); if(m1>m2)swap(m1,m2);}
//m1即次大值

離散化

• 從小到大標號并賦值，\(O(n\log n)\)，是個好東西

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

struct Disc{ //離散化后a[]的值互不相同，但是a[i]與a[j]∈[d.pre[a[i]],d.nxt[a[i]]]在離散化前是相同的
	int b[N],pre[N],nxt[N];
	void init(int a[],int n){
		copy(a,a+n,b); sort(b,b+n);
		pre[0]=0;
		repeat(i,1,n){
			if(b[i]==b[i-1])pre[i]=pre[i-1];
			else pre[i]=i;
		}
		nxt[n-1]=n-1;
		repeat_back(i,0,n-1){
			if(b[i]==b[i+1])nxt[i]=nxt[i+1];
			else nxt[i]=i;
		}
		repeat(i,0,n){
			a[i]=lower_bound(b,b+n,a[i])-b;
			b[a[i]]--;
		}
	}
}d;

01分數規劃

• \(n\) 個物品，都有兩個屬性 \(a_i\) 和 \(b_i\)，任意取 \(k\) 個物品使它們的 \(\dfrac {\sum a_j}{\sum b_j}\) 最大
• 解：二分答案
• \(m\) 是否滿足條件即判斷 \(\dfrac {\sum a_j}{\sum b_j}\ge m\)，即 \(\sum(a_j-mb_j)\ge 0\)
• 因此計算 \(c_i=a_i-mb_i\) ，取前 \(k\) 個最大值看它們之和是否 \(\ge 0\)
• 如果限制條件是 \(\sum b_j\ge W\)，則將 \(b_j\) 看成體積，\(a_j-mb_j\) 看成價值，轉換為背包dp

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

任務規劃 | Livshits-Kladov定理

• 給出 \(n\) 個任務，第 \(i\) 個任務花費 \(t_i\) 時間，該任務開始之前等待 \(t\) 時間的代價是 \(f_i(t)\) 個數，求一個任務排列方式，最小化代價 \(\sum\limits_{i=1}^n f_j(\sum\limits_{j=1}^{i-1}t_i)\)
• Livshits-Kladov定理：當 \(f_i(t)\) 是一次函式 / 指數函式 / 相同的單增函式時，最優解可以用排序計算
• 一次函式：\(f_i(t)=c_it+d_i\)，按 \(\dfrac {c_i}{t_i}\) 升序排列
• 指數函式：\(f_i(t)=c_ia^t+d_i\)，按 \(\dfrac{1-a^{t_i}}{c_i}\) 升序排列
• 相同的單增函式：按 \(t_i\) 升序排序

分治

逆序數×二維偏序

• \(O(n\log n)\)

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

最大空矩陣 | 懸線法

• 求01矩陣中全是0的最大連續子矩陣（面積最大）\(O(nm)\)
• 此處障礙物是正方形，如果障礙只是一些整點，答案從 \(ab\) 變為 \((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;
}

搜索

舞蹈鏈×DLX

精確覆寫

• 在01矩陣中找到某些行，它們兩兩不相交，且它們的并等于全集
• xy編號從 \(1\) 開始！\(O(\exp)\)，節點數 \(<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]; //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){
		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){
		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){
		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;
		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;

重復覆寫

• 在01矩陣中找到最少的行，它們的并等于全集
• xy編號還是從 \(1\) 開始！\(O(\exp)\)，節點數可能 \(<3000\)

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]=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

• 定義 \(g(v)\) 是 \(s\) 到 \(v\) 的實際代價，\(h(v)\) 是 \(v\) 到 \(t\) 的估計代價
• 定義估價函式 \(f(v)=g(v)+h(v)\)
• 每次從堆里取出 \(f(v)\) 最小的點進行更新
• 如果滿足 \(h(v_1)+w(v_2,v_1)\ge h(v_2)\) （存疑）則不需要重復更新同一點，可以用set標記，已標記的不入堆

模擬退火

• 以當前狀態 \(X\) 為中心，半徑為溫度 \(T\) 的圓（或球）內選一個新狀態 \(Y\)
• 計算 \(D=E(Y)-E(X)\) 新狀態勢能減去當前狀態勢能
• 如果 \(D<0\) 則狀態轉移（勢能 \(E\) 越小越優）
• 否則狀態轉移的概率是 \(\exp(-\dfrac{KD}{T})\)（Metropolis接受準則，學不會）
• 最后溫度乘以降溫系數，回傳第一步
• 需要調 \(3\) 個引數：初始溫度，終止溫度，降溫系數（？）

注意點：

• 讓運行時間在TLE邊緣試探
• 多跑幾次退火
• 多交幾次（注意風險）
• 可以先不用某準則，輸出中間程序后再調參

lf rndf(){return rnd()*1.0/rnd.max();}
vec rndvec(){return vec(rndf()*2-1,rndf()*2-1);}
//lf E(vec); //計算勢能
struct state{ //表示一個狀態
	vec v; lf e; //位置和勢能
	state(vec v=vec()):v(v),e(E(v)){}
	operator lf(){return e;}
};
state getstate(){
	state X; lf T=1000;
	auto work=[&](){
		state Y=X.v+rndvec()*T;
		if(Y<X /*|| rndf()<exp(-K*(Y.e-X.e)/T)*/){X=Y; return 1;}
		return 0;
	};
	while(T>1e-9){
		if(work()){work(); work(); T*=1.1;}
		T*=0.99992;
	}
	return X;
}

void solve(){
	state X;
	repeat(i,0,6){
		state Y=getstate();
		if(X>Y)X=Y;
	}
	printf("%.10f\n",lf(X));
}

動態規劃

多重背包

• 二進制版，\(O(nV\log num)\)，\(V\) 是總容量

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]

• 單調佇列版，\(O(nV)\)，\(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]

最長不降子序列×LIS

• 二分查找優化，\(O(n\log n)\)

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

• 記憶化搜索，dfs的引數lim表示是否被限制，lz表示當前位的前一位是不是前導零
• 復雜度等于狀態數
• 如果每個方案貢獻不是1，dp可能要變成struct陣列(cnt,sum,....)

ll dp[20][*][2],bit[20]; //這個[2]表示lz狀態，如果lz被使用了的話就需要記錄
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

• 兩次dfs
• 第一次求所有點所在子樹的答案 \(dp_v\)，此時 \(dp_{rt}\) 是 \(rt\) 的最終答案
• 第二次將根轉移來算其他點的最終答案，回溯時復原即可

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

斜率優化

• 例：HDOJ3507
• \(dp_i=\min\limits_{j=0}^{i-1}[dp_j+(s_i-s_j)^2+M]\)
• 考慮 \(k<j<i\)，\(j\) 決策優于 \(k\Leftrightarrow dp_j+(s_i-s_j)^2<dp_k+(s_i-s_k)^2\)
• 一通操作后 \(\dfrac{s_j^2+dp_j-s_k^2-dp_k}{2(s_j-s_k)}<s_i\)，即尋找點集 \(\{(2s_j,s_j^2+dp_j)\}\) 的下凸包中斜率剛好 \(>s_i\) 的線段的左端點，作為決策點

四邊形優化

• \(dp(l,r)=\min\limits_{k=l}^{r-1}[dp(l,k)+dp(k+1,r)]+w(l,r)\)
• 其中 \(w(l,r)\) 滿足
  • 區間包含單調性：任意 \(l \le l' \le r' \le r\) 有 \(w(l',r')\le w(l,r)\)
  • 四邊形不等式：任意 \(a \le b \le c \le d\) 有 \(w(a,c)+w(b,d)\le w(a,d)+w(b,c)\)（若等號恒成立則滿足四邊形恒等式）
• 決策單調性：令 \(m(l,r)\) 為最優決策點（滿足 \(dp(l,r)=dp(l,m)+dp(m+1,r)+w(l,r)\)），則有 \(m(l,r-1) \le m(l,r) \le m(l+1,r)\)，遍歷這個區間可以優化至 \(O(n^2)\)

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

• \(dp(i)=\min\limits_{k=1}^{i-1}w(k,i)\)，\(w(l,r)\) 滿足四邊形不等式
• 決策單調性：令 \(m_i\) 為最優決策點（滿足 \(dp(i)=w(m,i)\)），則 \(m_{i-1}\le m_i\)，因此可以分治優化成 \(O(n\log n)\)

計算幾何

struct of 向量

• rotate()回傳逆時針旋轉后的點，left()回傳朝左的單位向量
• trans()回傳p沿a,b拉伸的結果，arctrans()回傳p在坐標系<a,b>中的坐標
• 常量式寫法，不要另加變數，需要加變數就再搞個struct
• 直線類在半面交里，其中包含線段交點

struct vec{
	lf x,y; vec(){} vec(lf x,lf y):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);}
	vec left(){return vec(-y,x).trunc();}
	lf theta(){return atan2(y,x);}
	friend lf cross(vec a,vec b){return a.x*b.y-a.y*b.x;};
	friend lf cross(vec a,vec b,vec c){return cross(a-c,b-c);}
	friend lf dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
	friend vec trans(vec p,vec a,vec b){
		swap(a.y,b.x);
		return vec(dot(a,p),dot(b,p));
	}
	friend vec arctrans(vec p,vec a,vec b){
		lf t=cross(a,b);
		return vec(-cross(b,p)/t,cross(a,p)/t);
	}
	void output(){printf("%.12f %.12f\n",x,y);}
}a[N];

• 整數向量

struct vec{
	int x,y; vec(){} vec(int x,int y):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);}
	void operator+=(const vec &b){x+=b.x,y+=b.y;}
	void operator-=(const vec &b){x-=b.x,y-=b.y;}
	vec operator*(lf k){return vec(k*x,k*y);}
	bool operator==(vec b)const{return x==b.x && y==b.y;}
	int sqr(){return x*x+y*y;}
	void output(){printf("%lld %lld\n",x,y);}
}a[N]; const vec dn[]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

平面幾何基本操作

判斷兩條線段是否相交

• 快速排斥實驗：判斷線段所在矩形是否相交（用來減小常數，可省略）
• 跨立實驗：任一線段的兩端點在另一線段的兩側

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)<eps
	&& (a.y-p.y)*(b.y-p.y)<eps
	&& abs(cross(a-b,a-p))<eps;
}

多邊形面積

lf area(vec a[],int n){
	lf ans=0;
	repeat(i,0,n)
		ans+=cross(a[i],a[(i+1)%n]);
	return abs(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));
}

二維凸包

• 求上凸包，按坐標 \((x,y)\) 字典升序排序，從小到大加入堆疊，如果出現凹多邊形情況則出堆疊，下凸包反著來
• \(O(n\log n)\)，排序是瓶頸

vector<vec> st;
void push(vec &v,int b){
	while((int)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,[](vec a,vec b){
		return make_pair(a.x,a.y)<make_pair(b.x,b.y);
	});
	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(n\log n)\)

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

最大空矩形 | 掃描法

• 在范圍 \((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(n\log n)\)，可能有鍋

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

最小圓覆寫 | 隨機增量法×RIA

• eps可能要非常小，隨機化，均攤 \(O(n)\)

struct cir{ //圓（結構體）
	vec v; lf r;
	bool out(vec a){ //點a在圓外
		return (v-a).len()>r+eps;
	}
	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){
	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;
}

半面交 | S&I演算法

• 編號從 \(0\) 開始，\(O(n\log n)\)

struct line{
	vec p1,p2; lf th;
	line(){}
	line(vec p1,vec p2):p1(p1),p2(p2){
		th=(p2-p1).theta();
	}
	bool contain(vec v){
		return cross(v,p2,p1)<=eps;
	}
	vec PI(line b){ //point of intersection
		lf t1=cross(p1,b.p2,b.p1);
		lf t2=cross(p2,b.p2,b.p1);
		return vec((t1*p2.x-t2*p1.x)/(t1-t2),(t1*p2.y-t2*p1.y)/(t1-t2));
	}
};
vector<vec> ans; //ans: output, shows a convex hull
namespace half{
line a[N]; int n; //(a[],n): input, the final area will be the left of the lines
deque<line> q;
void solve(){
	a[n++]=line(vec(inf,inf),vec(-inf,inf));
	a[n++]=line(vec(-inf,inf),vec(-inf,-inf));
	a[n++]=line(vec(-inf,-inf),vec(inf,-inf));
	a[n++]=line(vec(inf,-inf),vec(inf,inf));
	sort(a,a+n,[](line a,line b){
		if(a.th<b.th-eps)return 1;
		if(a.th<b.th+eps && b.contain(a.p1)==1)return 1;
		return 0;
	});
	n=unique(a,a+n,[](line a,line b){return abs(a.th-b.th)<eps;})-a;
	q.clear();
	#define r q.rbegin()
	repeat(i,0,n){
		while(q.size()>1 && !a[i].contain(r[0].PI(r[1])))q.pop_back();
		while(q.size()>1 && !a[i].contain(q[0].PI(q[1])))q.pop_front();
		q.push_back(a[i]);
	}
	while(q.size()>1 && !q[0].contain(r[0].PI(r[1])))q.pop_back();
	while(q.size()>1 && !r[0].contain(q[0].PI(q[1])))q.pop_front();
	#undef r
	ans.clear();
	repeat(i,0,(int)q.size()-1)ans<<q[i].PI(q[i+1]);
	ans<<q[0].PI(q.back());
}
}

Delaunay三角剖分

• 編號從 \(0\) 開始，\(O(n\log n)\)

const lf eps=1e-8;
struct vec{
	lf x,y; int id;
	explicit vec(lf a=0,lf b=0,int c=-1):x(a),y(b),id(c){}
	bool operator<(const vec &a)const{
		return x<a.x || (abs(x-a.x)<eps && y<a.y);
	}
	bool operator==(const vec &a)const{
		return abs(x-a.x)<eps && abs(y-a.y)<eps;
	}
	lf dist2(const vec &b){
		return (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y);
	}
};
struct vec3D{
	lf x,y,z;
	explicit vec3D(lf a=0,lf b=0,lf c=0):x(a),y(b),z(c){}
	vec3D(const vec &v){x=v.x,y=v.y,z=v.x*v.x+v.y*v.y;}
	vec3D operator-(const vec3D &a)const{
		return vec3D(x-a.x,y-a.y,z-a.z);
	}
};
struct edge{
	int id;
	list<edge>::iterator c;
	edge(int id=0){this->id=id;}
};
int cmp(lf v){return abs(v)>eps?(v>0?1:-1):0;}
lf cross(const vec &o,const vec &a,const vec &b){
	return(a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
lf dot(const vec3D &a,const vec3D &b){return a.x*b.x+a.y*b.y+a.z*b.z;}
vec3D cross(const vec3D &a,const vec3D &b){
	return vec3D(a.y*b.z-a.z*b.y,-a.x*b.z+a.z*b.x,a.x*b.y-a.y*b.x);
}
vector<pii> ans; //三角剖分結果
struct DT{ //使用方法：直接solve()
	list<edge> a[N]; vec v[N]; int n;
	void solve(int _n,vec _v[]){
		n=_n;
		copy(_v,_v+n,v);
		sort(v,v+n);
		divide(0,n-1);
		ans.clear();
		for(int i=0;i<n;i++){
			for(auto p:a[i]){
				if(p.id<i)continue;
				ans.push_back({v[i].id,v[p.id].id});
			}
		}
	}
	int incircle(const vec &a,vec b,vec c,const vec &v){
		if(cross(a,b,c)<0)swap(b,c);
		vec3D a3(a),b3(b),c3(c),p3(v);
		b3=b3-a3,c3=c3-a3,p3=p3-a3;
		vec3D f=cross(b3,c3);
		return cmp(dot(p3,f));
	}
	int intersection(const vec &a,const vec &b,const vec &c,const vec &d){
		return cmp(cross(a,c,b))*cmp(cross(a,b,d))>0 &&
			cmp(cross(c,a,d))*cmp(cross(c,d,b))>0;
	}
	void addedge(int u,int v){
		a[u].push_front(edge(v));
		a[v].push_front(edge(u));
		a[u].begin()->c=a[v].begin();
		a[v].begin()->c=a[u].begin();
	}
	void divide(int l,int r){
		if(r-l<=2){
			for(int i=l;i<=r;i++)
				for(int j=i+1;j<=r;j++)addedge(i,j);
			return;
		}
		int mid=(l+r)/2;
		divide(l,mid); divide(mid+1,r);
		int nowl=l,nowr=r;
		for(int update=1;update;){
			update=0;
			vec vl=v[nowl],vr=v[nowr];
			for(auto i:a[nowl]){
				vec t=v[i.id];
				lf v=cross(vr,vl,t);
				if(cmp(v)>0 || (cmp(v)== 0 && vr.dist2(t)<vr.dist2(vl))){
					nowl=i.id,update=1;
					break;
				}
			}
			if(update)continue;
			for(auto i:a[nowr]){
				vec t=v[i.id];
				lf v=cross(vl,vr,t);
				if(cmp(v)<0 || (cmp(v)== 0 && vl.dist2(t)<vl.dist2(vr))){
					nowr=i.id,update=1;
					break;
				}
			}
		}
		addedge(nowl,nowr);
		while(1){
			vec vl=v[nowl],vr=v[nowr];
			int ch=-1,side=0;
			for(auto i:a[nowl])
			if(cmp(cross(vl,vr,v[i.id]))>0 && (ch==-1 || incircle(vl,vr,v[ch],v[i.id])<0)){
				ch=i.id,side=-1;
			}
			for(auto i:a[nowr])
			if(cmp(cross(vr,v[i.id],vl))>0 && (ch==-1 || incircle(vl,vr,v[ch],v[i.id])<0)){
				ch=i.id,side=1;
			}
			if(ch==-1)break;
			if(side==-1){
				for(auto it=a[nowl].begin();it!=a[nowl].end();){
					if(intersection(vl,v[it->id],vr,v[ch])){
						a[it->id].erase(it->c);
						a[nowl].erase(it++);
					}
					else it++;
				}
				nowl=ch;
				addedge(nowl,nowr);
			}
			else{
				for(auto it=a[nowr].begin();it!=a[nowr].end();){
					if(intersection(vr,v[it->id],vl,v[ch])){
						a[it->id].erase(it->c);
						a[nowr].erase(it++);
					}
					else it++;
				}
				nowr=ch;
				addedge(nowl,nowr);
			}
		}
	}
}dt;

• 可以求最小生成樹

vec a[N]; DSU d;
vector<int> e[N]; //最小生成樹結果
void mst(){ //求最小生成樹
	dt.solve(n,a);
	sort(ans.begin(),ans.end(),[](const pii &A,const pii &B){
		return a[A.fi].dist2(a[A.se])<a[B.fi].dist2(a[B.se]);
	});
	d.init(n);
	for(auto i:ans)
	if(d[i.fi]!=d[i.se]){
		e[i.fi].push_back(i.se);
		e[i.se].push_back(i.fi);
		d[i.fi]=d[i.se];
	}
}

struct of 三維向量

• trunc(K) 回傳 K 在 *this 上的投影向量
• rotate(P,L,th) 回傳點 P 繞軸 (O,L) 旋轉 th 弧度后的點
• rotate(P,L0,L1,th) 回傳點 P 繞軸 (L0,L1) 旋轉 th 弧度后的點

struct vec{
	lf x,y,z; vec(){} vec(lf x,lf y,lf z):x(x),y(y),z(z){}
	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_tuple(b.x,b.y,b.z);}
	lf sqr(){return x*x+y*y+z*z;}
	lf len(){return sqrt(x*x+y*y+z*z);}
	vec trunc(lf k=1){return *this*(k/len());}
	vec trunc(vec k){return *this*(dot(*this,k)/sqr());}
	friend 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);
	}
	friend lf dot(vec a,vec b){return a.x*b.x+a.y*b.y+a.z*b.z;}
	friend vec rotate(vec p,vec l,lf th){
		struct four{
			lf r; vec v;
			four operator*(four b){
				return {r*b.r-dot(v,b.v),v*b.r+b.v*r+cross(v,b.v)};
			}
		};
		l=l.trunc();
		four P={0,p};
		four Q1={cos(th/2),l*sin(th/2)};
		four Q2={cos(th/2),vec()-l*sin(th/2)};
		return ((Q1*P)*Q2).v;
	}
	friend vec rotate(vec p,vec l0,vec l1,lf th){
		return rotate(p-l0,l1-l0,th)+l0;
	}
	void output(){printf("%.12f %.12f %.12f\n",x,y,z);}
};

球面幾何

vec to_vec(lf lng,lf lat){ //lng經度，lat緯度，-90<lat<90
	lng*=pi/180,lat*=pi/180;
	lf z=sin(lat),m=cos(lat);
	lf x=cos(lng)*m,y=sin(lng)*m;
	return vec(x,y,z);
};
lf to_lng(vec v){return atan2(v.y,v.x)*180/pi;}
lf to_lat(vec v){return asin(v.z)*180/pi;}
lf angle(vec a,vec b){return acos(dot(a,b));}

三維凸包

• 將所有凸包上的面放入面集 f 中，其中 face::p[i] 作為 a 的下標，\(O(n^2)\)

const lf eps=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)*eps;
		y+=(rand()*1.0/RAND_MAX-0.5)*eps;
		z+=(rand()*1.0/RAND_MAX-0.5)*eps;
	}
}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);
	}
}

計算幾何雜項

正冪反演

• 給定反演中心 \(O\) 和反演半徑 \(R\)，若直線上的點 \(OPQ\) 滿足 \(|OP|\cdot|OQ|=R^2\)，則 \(P\) 和 \(Q\) 互為反演點（令 \(R=1\) 也可）
• 不經過反演中心的圓的反演圖形是圓（計算時取圓上靠近/遠離中心的兩個點）
• 經過反演中心的圓的反演圖形是直線（計算時取遠離中心的點，做垂線）

others of 計算幾何雜項

曼哈頓、切比雪夫距離

• 曼：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定理

• 可以用Pick定理求多邊形內部整點個數，其中一條線段上的點數為 \(\gcd(|x_1-x_2|,|y_1-y_2|)+1\)
• 正方形點陣：面積 = 內部點數 + 邊上點數 / 2 - 1
• 三角形點陣：面積 = 2 * 內部點數 + 邊上點數 - 2

公式

• 三角形面積 \(S=\sqrt{P(P-a)(P-b)(P-c)}\)，\(P\) 為半周長
• 斯特瓦爾特定理：\(BC\) 上一點 \(P\)，有 \(AP=\sqrt{AB^2\cdot \dfrac{CP}{BC}+AC^2\cdot \dfrac{BP}{BC}-BP\cdot CP}\)
• 三角形內切圓半徑 \(r=\dfrac {2S} C\)，外接圓半徑 \(R=\dfrac{a}{2\sin A}=\dfrac{abc}{4S}\)
• 四邊形有 \(a^2+b^2+c^2+d^2=D_1^2+D_2^2+4M^2\)，\(D_1,D_2\) 為對角線，\(M\) 為對角線中點連線
• 圓內接四邊形有 \(ac+bd=D_1D_2\)，\(S=\sqrt{(P-a)(P-b)(P-c)(P-d)}\)，\(P\) 為半周長
• 棱臺體積 \(V=\dfrac 13(S_1+S_2+\sqrt{S_1S_2})h\)，\(S_1,S_2\) 為上下底面積
• 正棱臺側面積 \(\dfrac 1 2(C_1+C_2)L\)，\(C_1,C_2\) 為上下底周長，\(L\) 為斜高（上下底對應的平行邊的距離）
• 球全面積 \(S=4\pi r^2\)，體積 \(V=\dfrac 43\pi r^3\)，
• 球臺(球在平行平面之間的部分)有 \(h=|\sqrt{r^2-r_1^2}\pm\sqrt{r^2-r_2^2}|\)，側面積 \(S=2\pi r h\)，體積 \(V=\dfrac{1}{6}\pi h[3(r_1^2+r_2^2)+h^2]\)，\(r_1,r_2\) 為上下底面半徑
• 正三角形面積 \(S=\dfrac{\sqrt 3}{4}a^2\)，正四面體面積 \(S=\dfrac{\sqrt 2}{12}a^3\)
• 四面體體積公式

lf sqr(lf x){return x*x;}
lf V(lf a,lf b,lf c,lf d,lf e,lf f){ //a,b,c共頂點
	lf A=b*b+c*c-d*d;
	lf B=a*a+c*c-e*e;
	lf C=a*a+b*b-f*f;
	return sqrt(4*sqr(a*b*c)-sqr(a*A)-sqr(b*B)-sqr(c*C)+A*B*C)/12;
}

資料結構

st表

普通st表

• 編號從 \(0\) 開始，初始化 \(O(n\log n)\) 查詢 \(O(1)\)

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表

• 編號從 \(0\) 開始，初始化 \(O(nm\log n\log m)\) 查詢 \(O(1)\)

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;

<補充>貓樹

• 編號從 \(0\) 開始，初始化 \(O(n\log n)\) 查詢 \(O(1)\)

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;

單調佇列

• 求所有長度為k的區間中的最大值，線性復雜度

struct MQ{ //查詢就用mq.q.front().first
	deque<pii> q; //first:保存的最大值; second:時間戳
	void init(){q.clear();}
	void push(int x,int k){
		static int T=0; T++;
		while(!q.empty() && q.back().fi<=x) //max
			q.pop_back();
		q.push_back({x,T});
		while(!q.empty() && q.front().se<=T-k)
			q.pop_front();
	}
	void work(function<int&(int)> a,int n,int k){ //原地保存，編號從0開始
		init();
		repeat(i,0,n){
			push(a(i),k);
			if(i+1>=k)a(i+1-k)=q.front().fi;
		}
	}
	void work(int a[][N],int n,int m,int k){ //原地保存，編號從0開始
		repeat(i,0,n){
			init();
			repeat(j,0,m){
				push(a[i][j],k);
				if(j+1>=k)a[i][j+1-k]=q.front().fi;
			}
		}
		m-=k-1;
		repeat(j,0,m){
			init();
			repeat(i,0,n){
				push(a[i][j],k);
				if(i+1>=k)a[i+1-k][j]=q.front().fi;
			}
		}
	}
}mq;
//求n*m矩陣中所有k*k連續子矩陣最大值之和 //編號從1開始
repeat(i,1,n+1)
	mq.work([&](int x)->int&{return a[i][x+1];},m,k);
repeat(j,1,m-k+2)
	mq.work([&](int x)->int&{return a[x+1][j];},n,k);
ll ans=0; repeat(i,1,n-k+2)repeat(j,1,m-k+2)ans+=a[i][j];
//或者
mq.work((int(*)[N])&(a[1][1]),n,m,k);

樹狀陣列

普通樹狀陣列

• 單點+區間，修改查詢 \(O(\log n)\)

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

• 大佬的第 \(k\) 小（權值樹狀陣列）

int findkth(int k){
	int ans=0,cnt=0;
	for (int i=20;i>=0;--i){
		ans+=1<<i;
		if (ans>=n || cnt+t[ans]>=k)ans-=1<<i;
		else cnt+=t[ans];
	}
	return ans+1;
}

超級樹狀陣列

• 基于樹狀陣列，基本只允許加法，區間+區間，\(O(\log n)\)

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;

二維超級樹狀陣列

• 修改查詢 \(O(\log n\cdot\log m)\)

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;

線段樹

• 基本上適用于所有（線段樹能實作的）區間+區間
• 我刪了修改運算的零元，加了偷懶狀態(state)，終于能支持賦值操作.jpg

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){
		if(x>r || y<l){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){
		if(x>r || y<l)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);
}

<補充>權值線段樹（動態開點 線段樹合并 線段樹分裂）

• 初始 \(n\) 個線段樹，支持對某個線段樹插入權值、合并兩個線段樹、查詢某個線段樹第k小數
• 編號從 \(1\) 開始，\(O(n\log n)\)

DSU d;
struct seg{
	seg *lc,*rc; int sz;
}tr[N<<5],*pl,*rt[N];
#define LL lc,l,m
#define RR rc,m+1,r
int size(seg *s){return s?s->sz:0;}
seg *newnode(){*pl=seg(); return pl++;}
void up(seg *s){s->sz=size(s->lc)+size(s->rc);}
void insert(seg *&s,int l,int r,int v,int num=1){ //insert v, (s=rt[d[x]])
	if(!s)s=newnode(); s->sz+=num;
	if(l==r)return;
	int m=(l+r)/2;
	if(v<=m)insert(s->LL,v,num);
	else insert(s->RR,v,num);
}
seg *merge(seg *a,seg *b,int l,int r){ //private, return the merged tree
	if(!a)return b; if(!b)return a;
	a->sz+=b->sz;
	if(l==r)return a;
	int m=(l+r)/2;
	a->lc=merge(a->lc,b->LL);
	a->rc=merge(a->rc,b->RR);
	return a;
}
void merge(int x,int y,int l,int r){ //merge tree x and y
	if(d[x]==d[y])return; 
	rt[d[x]]=merge(rt[d[x]],rt[d[y]],l,r);
	d[y]=d[x];
}
int kth(seg *s,int l,int r,int k){ //kth in s, (k=1,2,...,sz, s=rt[d[x]])
	if(l==r)return l;
	int m=(l+r)/2,lv=size(s->lc);
	if(k<=lv)return kth(s->LL,k);
	else return kth(s->RR,k-lv);
}
int query(seg *s,int l,int r,int x,int y){ //count the numbers between [x,y] (s=rt[d[x]])
	if(!s || x>r || y<l)return 0;
	if(x<=l && y>=r)return s->sz;
	int m=(l+r)/2;
	return query(s->LL,x,y)+query(s->RR,x,y);
}
void split(seg *&s,int l,int r,int x,int y,seg *&t){ //the numbers between [x,y] trans from s to t, (s=rt[d[x]], t=rt[d[y]])
	if(!s || x>r || y<l)return;
	if(x<=l && y>=r){t=merge(s,t,l,r); s=0; return;}
	if(!t)t=newnode();
	int m=(l+r)/2;
	split(s->LL,x,y,t->lc);
	split(s->RR,x,y,t->rc);
	up(s); up(t);
}
void init(int n){ //create n trees
	pl=tr; d.init(n);
	fill(rt,rt+n+1,nullptr);
}

<補充>zkw線段樹

• 單點+區間，編號從0開始，建樹 \(O(n)\) 修改查詢 \(O(\log n)\)
• 代碼量和常數都和樹狀陣列差不多

struct seg{
	#define U(a,b) max(a,b) //查詢操作
	const 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;

<補充>可持久化陣列

• 單點修改并創建新版本：h[top]=update(h[i],x,v);（每次 \(O(\log n)\) 額外記憶體）
• 單點查詢 h[i]->query(x);
• 初始化 \(O(n)\)，修改查詢 \(O(\log n)\)

struct seg *pl; int segl,segr;
struct seg{
	ll a; seg *lc,*rc;
	ll query(int x,int l=segl,int r=segr){
		if(l==r)return a;
		int m=(l+r)>>1;
		if(x<=m)return lc->query(x,l,m);
		else return rc->query(x,m+1,r);
	}
	friend seg *update(seg *u,int x,ll v,int l=segl,int r=segr){
		*++pl=*u; u=pl;
		if(l==r)u->a=v;
		else{
			int m=(l+r)>>1;
			if(x<=m)u->lc=update(u->lc,x,v,l,m);
			else u->rc=update(u->rc,x,v,m+1,r);
		}
		return u;
	}
	void init(int l,int r){
		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);
	}
}pool[N*20],*h[N]; //h: versions
void init(int l,int r){
	segl=l,segr=r;
	pl=pool; pl->init(l,r); h[0]=pl;
}

<補充>李超線段樹

• 支持插入線段、查詢所有線段與 \(x=x_0\) 交點最高的那條線段
• 修改 \(O(\log^2n)\)，查詢 \(O(\log n)\)

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

并查集

• 合并查找 \(O(α(n))\)，可視為 \(O(1)\)

普通并查集

• 精簡版，只有路徑壓縮

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;

<補充>可持久化并查集

• 啟發式合并，不能路徑壓縮，\(O(\log^2 n)\)

struct seg *pl; int segl,segr;
struct seg{
	ll a; seg *lc,*rc;
}pool[N*20*3];
pair<seg *,seg *> h[N];
void init(int l,int r){
	segl=l,segr=r; pl=pool;
	iota(in+l,in+r+1,l); h[0].fi=pl; pl->init(l,r);
	fill(in+l,in+r+1,1); h[0].se=++pl; pl->init(l,r);
}
int fa(seg *a,int x){
	int t; while((t=a->query(x))!=x)x=t; return x;
}
void join(seg *&a,seg *&sz,int x,int y){ //a=h[i].fi,sz=h[i].se
	x=fa(a,x); y=fa(a,y);
	if(x!=y){
		int sx=sz->query(x),sy=sz->query(y);
		if(sx<sy)swap(x,y),swap(sx,sy);
		a=update(a,y,x),sz=update(sz,x,sx+sy);
	}
}

左偏樹

• 萬年不用，\(O(?)\)
• 如果沒有特殊要求一律平板電視

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)

珂朵莉樹×老司機樹

• 珂朵莉數以區間形式存盤資料，非常暴力，適用于有區間賦值操作的題
• 均攤 \(O(n\log\log n)\)，但是很可能被卡

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

• 例題：luogu P4148
• 支持在線在(x,y)處插入值、查詢二維區間和
• 插入、查詢 \(O(\log n)\)

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;

劃分樹

• 靜態區間第 \(k\) 小，可代替主席樹
• 編號從 \(1\) 開始，初始化 \(O(n\log n)\)，查詢 \(O(\log n)\)

struct divtree{ //tr.query(l,r,k,1,n): kth in [l,r]
	int a[N],pos[25][N],tr[25][N];
	void build(int l,int r,int dep){ //private
		if(l==r)return;
		int m=(l+r)>>1;
		int same=m-l+1;
		repeat(i,l,r+1)
			same-=(tr[dep][i]<a[m]);
		int ls=l,rs=m+1;
		repeat(i,l,r+1){
			int flag=0;
			if(tr[dep][i]<a[m] || (tr[dep][i]==a[m] && same>0)){
				flag=1;
				tr[dep+1][ls++]=tr[dep][i];
				same-=(tr[dep][i]==a[m]);
			}
			else{
				tr[dep+1][rs++]=tr[dep][i];
			}
			pos[dep][i]=pos[dep][i-1]+flag;
		}
		build(l,m,dep+1);
		build(m+1,r,dep+1);
	}
	int query(int ql,int qr,int k,int L,int R,int dep=0){
		if(ql==qr)
			return tr[dep][ql];
		int m=(L+R)>>1;
		int x=pos[dep][ql-1]-pos[dep][L-1];
		int y=pos[dep][qr]-pos[dep][L-1];
		int rx=ql-L-x,ry=qr-L-y;
		int cnt=y-x;
		if(cnt>=k)
			return query(L+x,L+y-1,k,L,m,dep+1);
		else
			return query(m+rx+1,m+1+ry,k-cnt,m+1,R,dep+1);
	}
	void init(int in[],int n){
		repeat(i,1,n+1)tr[0][i]=a[i]=in[i];
		sort(a+1,a+n+1);
		build(1,n,0);
	}
}tr;

莫隊

• 離線（甚至在線）處理區間問題，猛得一批

普通莫隊

• 移動指標 \(l,r\) 來求所有區間的答案
• 塊大小為 \(\sqrt n\)，\(O(n^{\tfrac 3 2})\)

int unit,n,bkt[N],a[N],final[N]; //bkt是桶
ll ans;
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; //查詢區間
void update(int x,int d){
	int &b=bkt[a[x]];
	ans-=C(b,2); //操作示例
	b+=d;
	ans+=C(b,2); //操作示例
}
void solve(){ //final[]即最終答案
	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[i.id]=ans;
	}
}
//repeat(i,0,m)query.push_back({read(),read(),i}); //輸入查詢區間

帶修莫隊

• 相比與普通莫隊，多了一個時間軸
• 塊大小為 \(\sqrt[3]{nt}\)，\(O(\sqrt[3]{n^4t})\)
• 空缺

二叉搜索樹

不平衡的二叉搜索樹

• 左子樹所有結點 \(\le v <\) 右子樹所有節點，目前僅支持插入，查詢可以寫一個 map<int,TR *>

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]來訪問根節點

無旋treap

• 普通平衡樹按v分裂，文藝平衡樹按sz分裂
• insert,erase操作在普通平衡樹中，push_back,output(dfs)在文藝平衡樹中
• 普通平衡樹

struct treap{
	struct node{
		int pri,v,sz;
		node *l,*r;
		node(int _v){pri=rnd(); v=_v; l=r=0; sz=1;}
		node(){}
		friend int size(node *u){return u?u->sz:0;}
		void up(){sz=1+size(l)+size(r);}
		friend pair<node *,node *> split(node *u,int key){ //按v分裂
			if(u==0)return {0,0};
			if(key<u->v){
				auto o=split(u->l,key);
				u->l=o.se; u->up();
				return {o.fi,u};
			}
			else{
				auto o=split(u->r,key);
				u->r=o.fi; u->up();
				return {u,o.se};
			}
		}
		friend node *merge(node *x,node *y){
			if(x==0)return y;
			if(y==0)return x;
			if(x->pri>y->pri){
				x->r=merge(x->r,y); x->up();
				return x;
			}
			else{
				y->l=merge(x,y->l); y->up();
				return y;
			}
		}
		int find_by_order(int ord){
			if(ord==size(l))return v;
			if(ord<size(l))return l->find_by_order(ord);
			else return r->find_by_order(ord-size(l)-1);
		}
	}pool[N],*pl,*rt;
	void init(){
		pl=pool;
		rt=0;
	}
	void insert(int key){
		auto o=split(rt,key);
		*++pl=node(key);
		o.fi=merge(o.fi,pl);
		rt=merge(o.fi,o.se);
	}
	void erase_all(int key){
		auto o=split(rt,key-1),s=split(o.se,key);
		rt=merge(o.fi,s.se);
	}
	void erase_one(int key){
		auto o=split(rt,key-1),s=split(o.se,key);
		rt=merge(o.fi,merge(merge(s.fi->l,s.fi->r),s.se));
	}
	int order(int key){
		auto o=split(rt,key-1);
		int ans=size(o.fi);
		rt=merge(o.fi,o.se);
		return ans;
	}
	int operator[](int x){
		return rt->find_by_order(x);
	}
	int lower_bound(int key){
		auto o=split(rt,key-1);
		int ans=o.se->find_by_order(0);
		rt=merge(o.fi,o.se);
		return ans;
	}
	int nxt(int key){return lower_bound(key+1);}
}tr;
//if(opt==1)tr.insert(x);
//if(opt==2)tr.erase_one(x);
//if(opt==3)cout<<tr.order(x)+1<<endl; //x的排名
//if(opt==4)cout<<tr[x-1]<<endl; //排名為x
//if(opt==5)cout<<tr[tr.order(x)-1]<<endl; //前驅
//if(opt==6)cout<<tr.nxt(x)<<endl; //后繼

• 文藝平衡樹，tag表示翻轉子樹（區間）

struct treap{
	struct node{
		int pri,v,sz,tag;
		node *l,*r;
		node(int _v){pri=(int)rnd(); v=_v; l=r=0; sz=1; tag=0;}
		node(){}
		friend int size(node *u){return u?u->sz:0;}
		void up(){sz=1+size(l)+size(r);}
		void down(){
			if(tag){
				swap(l,r);
				if(l)l->tag^=1;
				if(r)r->tag^=1;
				tag=0;
			}
		}
		friend pair<node *,node *> split(node *u,int key){ //按sz分裂
			if(u==0)return {0,0};
			u->down();
			if(key<size(u->l)){
				auto o=split(u->l,key);
				u->l=o.se; u->up();
				return {o.fi,u};
			}
			else{
				auto o=split(u->r,key-size(u->l)-1);
				u->r=o.fi; u->up();
				return {u,o.se};
			}
		}
		friend node *merge(node *x,node *y){
			if(x==0 || y==0)return max(x,y);
			if(x->pri>y->pri){
				x->down();
				x->r=merge(x->r,y); x->up();
				return x;
			}
			else{
				y->down();
				y->l=merge(x,y->l); y->up();
				return y;
			}
		}
	}pool[N],*pl,*rt;
	void init(){
		pl=pool;
		rt=0;
	}
	void push_back(int v){
		*++pl=node(v);
		rt=merge(rt,pl);
	}
	void add_tag(int l,int r){ //編號從0開始
		node *a,*b,*c;
		tie(a,b)=split(rt,l-1);
		tie(b,c)=split(b,r-l);
		if(b)b->tag^=1;
		rt=merge(a,merge(b,c));
	}
	void output(node *u){
		if(u==0)return; u->down();
		output(u->l); cout<<u->v<<' '; output(u->r);
	}
}tr;

<補充> 可持久化treap

• 其他函式從treap板子里照搬（但是把rt作為引數）
• h[i]=h[j] 就是克隆
• 普通平衡樹

struct node *pl; 
struct node{
	int pri,v,sz;
	node *l,*r;
	node(int _v){pri=rnd(); v=_v; l=r=0; sz=1;}
	node(){}
	friend int size(node *u){return u?u->sz:0;}
	void up(){sz=1+size(l)+size(r);}
	friend pair<node *,node *> split(node *u,int key){
		if(u==0)return {0,0};
		node *w=++pl; *w=*u;
		if(key<u->v){
			auto o=split(u->l,key);
			w->l=o.se; w->up();
			return {o.fi,w};
		}
		else{
			auto o=split(u->r,key);
			w->r=o.fi; w->up();
			return {w,o.se};
		}
	}
	friend node *merge(node *x,node *y){
		if(x==0)return y;
		if(y==0)return x;
		node *w=++pl; 
		if(x->pri>y->pri){
			*w=*x;
			w->r=merge(x->r,y);
		}
		else{
			*w=*y;
			w->l=merge(x,y->l);
		}
		w->up();
		return w;
	}
}pool[N*60],*h[N];

一些建議

雙頭優先佇列可以用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);
	}
};

高維前綴和

• 以二維為例，t是維數
• 法一 \(O(n^t2^t)\)
• 法二 \(O(n^tt)\)

//<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]）

手寫deque很可能比stl deque慢（吸氧時）

圖論

圖論的一些概念

---

• 基環圖：樹加一條邊
• 簡單圖：不含重邊和自環
• 完全圖：頂點兩兩相連的無向圖
• 競賽圖：頂點兩兩相連的有向圖
• 點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\) 個哈密頓回路

---

圖論基礎

前向星

struct edge{int to,w,nxt;}; //指向，權值，下一條邊
vector<edge> a;
int head[N];
void addedge(int x,int y,int w){
	a.push_back({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)

拓撲排序×Toposort

• \(O(V+E)\)

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

歐拉路徑 歐拉回路

• 若存在則路徑為 \(dfs\) 退出序（最后的序列還要再反過來）（如果for從小到大，可以得到最小字典序）
• （不記錄點的 \(vis\)，只記錄邊的 \(vis\)）

dfs樹 bfs樹

• 無向圖dfs樹：樹邊、返祖邊
• 有向圖dfs樹：樹邊、返祖邊、橫叉邊、前向邊
• 無向圖bfs樹：樹邊、返祖邊、橫叉邊
• 空缺

最短路徑

Dijkstra

• 僅限正權，\(O(E\log E)\)

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

• \(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+1\) 次即存在負環
• 編號從 \(0\) 開始，\(O(VE)\)

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

• SPFA+Dijkstra實作全源最短路，編號從 \(0\) 開始，\(O(VE\log E)\)

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

最小環

• 有向圖最小環Dijkstra，\(O(VE\log E)\)：對每個點 \(v\) 進行Dijkstra，到達 \(v\) 的邊更新答案，適用稀圖
• 有向圖最小環Floyd，\(O(V^3)\)：Floyd完之后，任意兩點計算 \(dis_{u,v}+dis_{v,u}\)，適用稠圖
• 無邊權無向圖最小環：以每個頂點為根生成bfs樹（不是dfs），橫叉邊更新答案，\(O(VE)\)
• 有邊權無向圖最小環：上面的bfs改成Dijkstra，\(O(VE \log E)\)

//無邊權無向圖最小環
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;
}

最小生成樹×MST

Kruskal

• 對邊長排序，然后添邊，并查集判聯通，\(O(E\log E)\)，排序是瓶頸

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

• 類似Prim演算法，但是可以多路增廣（名詞迷惑行為），\(O(E\log V)\)

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

最小樹形圖 | 朱劉演算法

• 其實有更高級的Tarjan演算法 \(O(E+V\log V)\)，但是學不會
• 編號從1開始，求的是葉向樹形圖，\(O(VE)\)

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

樹論

樹的直徑

• 直徑：即最長路徑
• 求直徑：以任意一點出發所能達到的最遠節點為一個端點，以這個端點出發所能達到的最遠節點為另一個端點（也可以樹上dp）

樹的重心

• 重心：以重心為根，其最大兒子子樹最小
• 性質
  • 以重心為根，所有子樹大小不超過整棵樹的一半
  • 重心最多有兩個
  • 重心到所有結點距離之和最小
  • 兩棵樹通過一條邊相連，則新樹的重心在是原來兩棵樹重心的路徑上
  • 一棵樹添加或洗掉一個葉子，重心最多移動一條邊的距離
  • 重心不一定在直徑上

void dfs(int x,int fa=-1){
	static int sz[N],maxx[N];
	sz[x]=1; maxx[x]=0;
	for(auto p:a[x])if(p!=fa){
		dfs(p,x);
		maxx[x]=max(maxx[x],sz[p]);
		sz[x]+=sz[p];
	}
	maxx[x]=max(maxx[x],n-sz[x]);
	if(maxx[x]<maxx[rt])rt=x;
}

最近公共祖先×LCA

樹上倍增解法

• 編號從哪開始都可以，初始化 \(O(n\log n)\)，查詢 \(O(\log n)\)

vector<int> e[N]; int dep[N],fa[N][22];
#define log(x) (31-__builtin_clz(x))
void dfs(int x){
	repeat(i,1,log(dep[x])+1){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		//dis[x][i]=U(dis[x][i-1],dis[fa[x][i-1]][i-1]);
	}
	for(auto p:e[x])
	if(fa[x][0]!=p){
		fa[p][0]=x,dep[p]=dep[x]+1,dfs(p);
		//dis[p][0]=f(x,p);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
		x=fa[x][log(dep[x]-dep[y])];
	if(x==y)return x;
	repeat_back(i,0,log(dep[x])+1)
	if(fa[x][i]!=fa[y][i])
		x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void init(int s){fa[s][0]=s; dep[s]=0; dfs(s);}
/*
lf len2(int x,int y){ //y是x的祖先
	lf ans=0;
	while(dep[x]>dep[y]){
		ans=U(ans,dis[x][log(dep[x]-dep[y])]);
		x=fa[x][log(dep[x]-dep[y])];
	}
	return ans;
}
lf length(int x,int y){int l=lca(x,y); return U(len2(x,l),len2(y,l));} //無修查詢鏈上資訊
*/

歐拉序列+st表解法

• 編號從 \(0\) 開始，初始化 \(O(n\log n)\)，查詢 \(O(1)\)

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*2][logN],log[N*2];
	RMQ(){
		log[1]=0;
		repeat(i,2,N*2)
			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();

樹鏈剖分解法

• 編號從哪開始都可以，初始化 \(O(n)\)，查詢 \(O(\log n)\)

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

Tarjan解法

• 離線演算法，基于并查集
• qry 和 ans 編號從 \(0\) 開始，\(O(n+m)\)，大常數（不看好）

vector<int> e[N]; vector<pii> qry,q[N]; //qry輸入
DSU d; bool vis[N]; int ans[N]; //ans輸出
void dfs(int x){
	vis[x]=1;
	for(auto i:q[x])if(vis[i.fi])ans[i.se]=d[i.fi];
	for(auto p:e[x])if(!vis[p])dfs(p),d[p]=x;
}
void solve(int n,int s){
	repeat(i,0,qry.size()){
		q[qry[i].fi].push_back({qry[i].se,i});
		q[qry[i].se].push_back({qry[i].fi,i});
	}
	d.init(n); dfs(s);
}

一些關于lca的問題

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

int intersection(int x,int y,int xx,int yy){ //樹上兩條路徑公共點個數
	int t[4]={lca(x,xx),lca(x,yy),lca(y,xx),lca(y,yy)};
	sort(t,t+4,[](int x,int y){return dep[x]<dep[y];});
	int r=lca(x,y),rr=lca(xx,yy);
	if(dep[t[0]]<min(dep[r],dep[rr]) || dep[t[2]]<max(dep[r],dep[rr]))
		return 0;
	int tt=lca(t[2],t[3]);
	return 1+dep[t[2]]+dep[t[3]]-dep[tt]*2;
}

樹鏈剖分

• 編號從 \(0\) 開始，處理鏈 \(O(\log^2 n)\)，處理子樹 \(O(\log n)\)

vector<int> e[N];
int dep[N],son[N],sz[N],top[N],fa[N];
int id[N],arcid[N],idcnt; //id[x]:結點x在樹剖序中的位置，arcid相反
void dfs1(int x){
	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){
	arcid[idcnt]=x; id[x]=idcnt++; top[x]=tv;
	if(son[x]==-1)return;
	dfs2(son[x],tv);
	for(auto p:e[x]){
		if(p==fa[x] || p==son[x])continue;
		dfs2(p,p);
	}
}
int lab[N]; //初始點權
seg tr[N*2],*pl; //if(l==r){a=lab[arcid[l]];return;}
void init(int s){
	idcnt=0; fa[s]=s;
	dfs1(s); dfs2(s,s);
	seginit(0,idcnt-1); //線段樹的初始化
}
void upchain(int x,int y,int d){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tr->update(id[top[x]],id[x],d);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	tr->update(id[x],id[y],d);
}
ll qchain(int x,int y){
	ll ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=tr->query(id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans+=tr->query(id[x],id[y]);
	return ans;
}
void uptree(int x,int d){
	tr->update(id[x],id[x]+sz[x]-1,d);
}
ll qtree(int x){
	return tr->query(id[x],id[x]+sz[x]-1);
}

樹分治

點分治

• 每次找樹的重心（最大子樹最小的點），去掉它后對所有子樹進行相同操作
• 一般 \(O(n\log n)\)
• 例：luogu P3806，帶邊權的樹，詢問長度為 \(q_i\) 的路徑是否存在

vector<pii> a[N];
bool vis[N];
vector<pii> q; //q[i].fi: query; q[i].se: answer
namespace center{
vector<int> rec;
int sz[N],maxx[N];
void dfs(int x,int fa=-1){
	rec<<x;
	sz[x]=1; maxx[x]=0;
	for(auto i:a[x]){
		int p=i.fi;
		if(p!=fa && !vis[p]){
			dfs(p,x);
			sz[x]+=sz[p];
			maxx[x]=max(maxx[x],sz[p]);
		}
	}
}
int get(int x){ //get center
	rec.clear(); dfs(x); int n=sz[x],ans=x;
	for(auto x:rec){
		maxx[x]=max(maxx[x],n-sz[x]);
		if(maxx[x]<maxx[ans])ans=x;
	}
	return ans;
}
}
vector<int> rec;
void getdist(int x,int dis,int fa=-1){
	if(dis<10000010)rec<<dis;
	for(auto i:a[x]){
		int p=i.fi;
		if(p!=fa && !vis[p]){
			getdist(p,dis+i.se,x);
		}
	}
}
unordered_set<int> bkt;
void dfs(int x){
	x=center::get(x);
	bkt.clear(); bkt.insert(0);
	vis[x]=1;
	for(auto i:a[x]){ //這部分統計各個子樹的資訊并更新答案
		int p=i.fi;
		if(!vis[p]){
			rec.clear(); getdist(p,i.se);
			for(auto i:rec){
				for(auto &j:q)
				if(bkt.count(j.fi-i))
					j.se=1;
			}
			for(auto i:rec)bkt.insert(i);
		}
	}
	for(auto i:a[x]){ //這部分進一步分治
		int p=i.fi;
		if(!vis[p]){
			dfs(p); 
		}
	}
}

聯通性相關

強聯通分量scc+縮點 | Tarjan

• 編號從0開始，\(O(V+E)\)

vector<int> a[N];
stack<int> stk;
bool vis[N],instk[N];
int dfn[N],low[N],co[N],w[N]; //co:染色結果，w:點權
vector<int> sz; //sz:第i個顏色的點數
int n,m,dcnt;
void dfs(int x){ //Tarjan求強聯通分量
	vis[x]=instk[x]=1; stk.push(x);
	dfn[x]=low[x]=++dcnt;
	for(auto p:a[x]){
		if(!vis[p])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 getscc(){
	fill(vis,vis+n,0);
	sz.clear();
	repeat(i,0,n)if(!vis[i])dfs(i);
}
void shrink(){ //縮點，在a里重構
	static set<pii> eset;
	eset.clear();
	getscc();
	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);
	}
}

• 例題：給一個有向圖，連最少的邊使其變為scc，解：scc縮點后輸出 \(\max(\sum\limits_i[indeg[i]=0],\sum\limits_i[outdeg[i]=0])\)，特判只有一個scc的情況

邊雙連通分量 | Tarjan

• 編號從0開始，\(O(V+E)\)

void dfs(int x,int fa){ //Tarjan求邊雙聯通分量
	vis[x]=instk[x]=1; stk.push(x);
	dfn[x]=low[x]=++dcnt;
	for(auto p:a[x])
	if(p!=fa){
		if(!vis[p])dfs(p,x);
		if(instk[p])low[x]=min(low[x],low[p]);
	}
	else fa=-1; //處理重邊
	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 getscc(){
	fill(vis,vis+n,0);
	sz.clear();
	repeat(i,0,n)if(!vis[i])dfs(i,-1);
}
//全域變數，shrink()同scc

割點×割頂

• Tarjan

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問題

可行解

• 有 \(2n\) 個頂點，其中頂點 \(2i\) 和頂點 \(2i+1\) 中能且僅能選一個，邊 \((u,v)\) 表示選了 \(u\) 就必須選 \(v\)，求一個可行解
• 暴力版，可以跑出字典序最小的解，編號從 \(0\) 開始，\(O(VE)\)，（但是難以跑到上界）

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;

• SCC縮點版，\(O(V+E)\)，空缺
• 2-SAT計數
• 空缺（太恐怖了）

支配樹 | Lengauer?Tarjan演算法

• 有向圖給定源點，若刪掉 \(r\)，源點不可達 \(u\)，則稱 \(r\) 是 \(u\) 的支配點
• 支配樹即所有非源點的點與最近支配點(idom)連邊形成的樹（源點為根）

vector<int> a[N],b[N],tr[N]; //tr: result
int fa[N],dfn[N],dcnt,arcdfn[N];
int c[N],best[N],sm[N],im[N]; //im: result
void init(int n){
	dcnt=0;
	iota(c,c+n+1,0);
	repeat(i,1,n+1){
		tr[i].clear();
		a[i].clear();
		b[i].clear();
	}
	repeat(i,1,n+1)sm[i]=best[i]=i;
	fill(dfn,dfn+n+1,0);
}
void dfs(int u){
	dfn[u]=++dcnt; arcdfn[dcnt]=u;
	for(auto v:a[u])if(!dfn[v]){fa[v]=u; dfs(v);}
}
int find(int x){
	if(c[x]==x)return x;
	int &f=c[x],rt=find(f);
	if(dfn[sm[best[x]]]>dfn[sm[best[f]]])
		best[x]=best[f];
	return f=rt;
}
void solve(int s){
	dfs(s);
	repeat_back(i,2,dcnt+1){
		int x=arcdfn[i],mn=dcnt+1;
		for(auto u:b[x]){
			if(!dfn[u])continue;
			find(u); mn=min(mn,dfn[sm[best[u]]]);
		}
		c[x]=fa[x];
		tr[sm[x]=arcdfn[mn]]<<x;
		x=arcdfn[i-1];
		for(auto u:tr[x]){
			find(u);
			if(sm[best[u]]!=x)im[u]=best[u];
			else im[u]=x;
		}
		tr[x].clear();
	}
	repeat(i,2,dcnt+1){
		int u=arcdfn[i];
		if(im[u]!=sm[u])im[u]=im[im[u]];
		tr[im[u]]<<u;
	}
}

圖上的NP問題

最大團+極大團計數

• 求最大團頂點數（和最大團），g[][] 編號從 \(0\) 開始，\(O(\exp)\)

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

• 求極大團個數（和所有極大團），g[][] 的編號從 \(1\) 開始！\(O(\exp)\)

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

最小染色數

• \(O(\exp)\)，n=17 可用

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

弦圖+區間圖

• 弦是連接環上不相鄰點的邊；弦圖是所有長度大于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)\log V)\)

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

---

• 區間圖：給出的每個區間都看成點，有公共部分的兩個區間之間連一條邊
• 區間圖是弦圖（反過來不一定），可以應用弦圖的所有演算法
• 區間圖的判定：所有弦圖可以寫成一個極大團樹（所有極大團看成一個頂點，極大團之間有公共頂點就連一條邊），區間圖的極大團樹是一個鏈

仙人掌 | 圓方樹

• 仙人掌：每條邊至多屬于一個簡單環的無向聯通圖
• 圓方樹：原來的點稱為圓點，每個環新建一個方點，環上的圓點都與方點連接
• 子仙人掌：以 \(r\) 為根，點 \(p\) 的子仙人掌是刪掉 \(p\) 到 \(r\) 的所有簡單路徑后 \(p\) 所在的聯通塊，這個子仙人掌就是圓方樹中以 \(r\) 為根時，\(p\) 子樹中的所有圓點
• 仙人掌的判定（樹上差分）編號從哪開始都可以，\(O(n+m)\)

vector<int> a[N]; //vector<int> rec; //rec存每個環的大小
bool vis[N]; int fa[N],lab[N],dep[N]; bool ans;
void dfs(int x){
	vis[x]=1;
	for(auto p:a[x])if(p!=fa[x]){
		if(!vis[p]){
			fa[p]=x; dep[p]=dep[x]+1;
			dfs(p); lab[x]+=lab[p];
		}
		else if(dep[p]<dep[x]){
			lab[x]++; lab[p]--;
			//rec.push_back(dep[x]-dep[p]+1);
		}
	}
	if(lab[x]>=2)ans=0;
}
bool iscactus(int s){
	fill(vis,vis+n+1,0);
	ans=1; fa[s]=-1; dfs(s); return ans;
}

二分圖

二分圖的一些概念

---

• 最小點覆寫（最小的點集，使所有邊都能被覆寫） = 最大匹配
• 最大獨立集 = 頂點數 - 最大匹配
• 最小路徑覆寫 = （開點前）頂點數 - 最大匹配，右頂點未被匹配的都看作起點
• 最小帶權點覆寫 = 點權之和 - 最大帶權獨立集（左式用最小割求）

---

• 霍爾定理：最大匹配 = 左頂點數 \(\Leftrightarrow\) 所有左頂點子集 \(S\) 都有 \(|S|\le|\omega(S)|\) ，\(\omega(S)\) 是 \(S\) 的領域
• 運用：若在最大匹配中有 \(t\) 個左頂點失配，因此最大匹配 = 左頂點數 - \(t\)
• 對任意左頂點子集 \(S\) 都有 \(|S|\le|\omega(S)|+t\)，\(t\ge|S|-|\omega(S)|\) ，求右式最大值即可求最大匹配

---

二分圖匹配×最大匹配

• 匈牙利×hungarian，左右頂點編號從 \(0\) 開始，\(O(VE)\)

vector<int> a[N]; //a: input, the left vertex x is connected to the right vertex a[x][i]
int dcnt,mch[N],dfn[N]; //mch: output, the right vertex p is connected to the left vertex mch[p]
bool dfs(int x){
	for(auto p:a[x]){
		if(dfn[p]!=dcnt){
			dfn[p]=dcnt;
			if(mch[p]==-1 || dfs(mch[p])){
				mch[p]=x;
				return 1;
			}
		}
	}
	return 0;
}
int hun(int n,int m){ //n,m: the number of the left/right vertexes. return max matching
	int ans=0;
	repeat(i,0,m)mch[i]=-1;
	repeat(i,0,n){
		dcnt++;
		if(dfs(i))ans++;
	}
	return ans;
}

• HK演算法×Hopcroft-karp，左頂點編號從 \(0\) 開始，右頂點編號從 \(n\)開始，\(O(E\sqrt V)\)

vector<int> a[N]; //a: input, the left vertex x is connected to the right vertex a[x][i]
int mch[N*2],dep[N*2]; //mch: output, the vertex p is connected to the vertex mch[p] (p could be either left or right vertex)
bool bfs(int n,int m){
	static queue<int> q;
	fill(dep,dep+n+m,0);
	bool flag=0;
	repeat(i,0,n)if(mch[i]==-1)q.push(i);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto p:a[x]){
			if(!dep[p]){
				dep[p]=dep[x]+1;
				if(mch[p]==-1)flag=1;
				else dep[mch[p]]=dep[p]+1,q.push(mch[p]);
			}
		}
	}
	return flag;
}
bool dfs(int x){
	for(auto p:a[x]){
		if(dep[p]!=dep[x]+1) continue;
		dep[p]=0;
		if(mch[p]==-1 || dfs(mch[p])) {
			mch[x]=p; mch[p]=x;
			return 1;
		}
	}
	return 0;
}
int solve(int n,int m){ //n,m: the number of the left/right vertexes. return max matching
	int ans=0;
	fill(mch,mch+n+m,-1);
	while(bfs(n,m)){
		repeat(i,0,n)
		if(mch[i]==-1 && dfs(i))
			ans++;
	}
	return ans;
}

• 網路流建圖，編號從 \(0\) 開始，\(O(E\sqrt V)\)

int work(int n1,int n2,vector<pii> &eset){
	int n=n1+n2+2;
	int s=0,t=n1+n2+1;
	flow.init(n);
	repeat(i,1,n1+1)add(s,i,1);
	repeat(i,n1+1,n1+n2+1)add(i,t,1);
	for(const auto &i:eset){
		int x=i.fi,y=i.se;
		add(x+1,n1+y+1,1);
	}
	return flow.solve(s,t);
}

最大權匹配 | KM

• 求滿二分圖的最大權匹配
• 如果沒有邊就建零邊，而且要求n<=m
• 編號從 \(0\) 開始，\(O(n^3)\)

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

穩定婚姻 | 延遲認可

• 穩定意味著不存在一對不是情侶的男女，都認為當前伴侶不如對方
• 編號從 \(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); //下次努力
	}
}

一般圖最大匹配 | 帶花樹

• 對于一個無向圖，找最多的邊使得這些邊兩兩無公共端點
• 編號從 \(1\) 開始，\(O(n^3)\)

int n; DSU d;
deque<int> q; vector<int> e[N];
int mch[N],vis[N],dfn[N],fa[N],dcnt=0;
int lca(int x,int y){
	dcnt++;
	while(1){
		if(x==0)swap(x,y); x=d[x];
		if(dfn[x]==dcnt)return x;
		else dfn[x]=dcnt,x=fa[mch[x]];
	}
}
void shrink(int x,int y,int p){
	while(d[x]!=p){
		fa[x]=y; y=mch[x];
		if(vis[y]==2)vis[y]=1,q.push_back(y);
		if(d[x]==x)d[x]=p;
		if(d[y]==y)d[y]=p;
		x=fa[y];
	}
}
bool match(int s){
	d.init(n); fill(fa,fa+n+1,0);
	fill(vis,vis+n+1,0); vis[s]=1;
	q.assign(1,s);
	while(!q.empty()){
		int x=q.front(); q.pop_front();
		for(auto p:e[x]){
			if(d[x]==d[p] || vis[p]==2)continue;
			if(!vis[p]){
				vis[p]=2; fa[p]=x;
				if(!mch[p]){
					for(int now=p,last,tmp;now;now=last){
						last=mch[tmp=fa[now]];
						mch[now]=tmp,mch[tmp]=now;
					}
					return 1;
				}
				vis[mch[p]]=1; q.push_back(mch[p]);
			}
			else if(vis[p]==1){
				int l=lca(x,p);
				shrink(x,p,l);
				shrink(p,x,l);
			}
		}
	}	
	return 0;
}
int solve(){ //回傳匹配數，mch[]是匹配結果（即匹配x和mch[x]），==0表示不匹配
	int ans=0; fill(mch,mch+n+1,0);
	repeat(i,1,n+1)ans+=(!mch[i] && match(i));
	return ans;
}

• 例題：給定一個無向圖和 \(d_i\)（\(1\le d_i\le 2\)），求是否能刪去一些邊后滿足點 \(i\) 的度剛好是 \(d_i\)

::n=n*2+m*2; //::n是帶花樹板子里的n
repeat(i,1,n+1)cnt+=deg[i]=read();
repeat(i,1,m+1){
	int x=read(),y=read();
	if(deg[x]==2 && deg[y]==2){ //(x,e)(x',e)(y,e')(y',e')(e,e')
		add(x,n*2+i),add(x+n,n*2+i),add(y,n*2+m+i),add(y+n,n*2+m+i),add(n*2+i,n*2+m+i);
		cnt+=2;
	}
	else{ //(x,y),度為2再添一條邊
		add(x,y); if(deg[x]==2)add(x+n,y); if(deg[y]==2)add(x,y+n);
	}
}
puts(solve()*2==cnt?"Yes":"No");

網路流

網路流的一些概念

---

• \(c(u,v)\) 為 \(u\) 到 \(v\) 的容量，\(f(u,v)\) 為 \(u\) 到 \(v\) 的流量，\(f(u,v)<c(u,v)\)
• \(c[X,Y]\) 為 \(X\) 到 \(Y\) 的容量和，不包括 \(Y\) 到 \(X\) 的容量；\(f(X,Y)\) 為 \(X\) 到 \(Y\) 的流量和，要減去 \(Y\) 到 \(X\) 的流量

---

• 費用流（最小費用最大流）：保證最大流后的最小費用

---

• 割：割 \([S,T]\) 是點集的一個分割且 \(S\) 包含源點，\(T\) 包含匯點，稱 \(f(S,T)\) 為割的凈流，\(c[S,T]\) 為割的容量
• 最大流最小割定理：最大流即最小割容量
• 求最小割：在最大流殘量網路中，令源點可達的點集為 \(S\)，其余的為 \(T\) 即可（但是滿流邊不一定都在 \(S,T\) 之間）

---

• 閉合子圖：子圖內所有點的兒子都在子圖內，點權之和最大的閉合子圖為最大閉合子圖
• 求最大閉合子圖：點權為正則s向該點連邊，邊權為點權，為負則向t連邊，邊權為點權絕對值，原圖所有邊的權設為inf，跑最小割，如果連s的邊被割則不選這個點，若連t的邊被割則選這個點

---

最大流

• 以下頂點編號均從 \(0\) 開始

Dinic

• 多路增廣，\(O(V^2E)\)

struct FLOW{
	struct edge{int to,w,nxt;};
	vector<edge> a; int head[N],cur[N];
	int n,s,t;
	queue<int> q; bool inque[N];
	int dep[N];
	void ae(int x,int y,int w){ //add edge
		a.push_back({y,w,head[x]});
		head[x]=a.size()-1;
	}
	bool bfs(){ //get dep[]
		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){ //extend
		int now,ans=0;
		if(x==t)return flow;
		for(int &i=cur[x];i!=-1;i=a[i].nxt){
			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){
		n=_n+1; a.clear();
		fill(head,head+n,-1);
		fill(inque,inque+n,0);
	}
	int solve(int _s,int _t){ //return max flow
		s=_s,t=_t;
		int ans=0;
		while(bfs())ans+=dfs(s,inf);
		return ans;
	}
}flow;
void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);}
//先flow.init(n)，再add添邊，最后flow.solve(s,t)

ISAP

• 僅一次bfs與多路增廣，\(O(V^2E)\)，有鍋！！

struct FLOW{
	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];
	void ae(int x,int y,int w){
		a.push_back({y,w,head[x]});
		head[x]=a.size()-1;
	}
	bool bfs(){
		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;
void add(int x,int y,int w){flow.ae(x,y,w),flow.ae(y,x,0);}
//先flow.init(n)，再add添邊，最后flow.solve(s,t)

最小費用最大流 | MCMF

• 費用流一般指最小費用最大流（最大費用最大流把費用取反即可）
• MCMF，單路增廣，\(O(VE^2)\)

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;
void add(int x,int y,int w,int 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();
}

有向圖矩陣樹定理

• 根向樹形圖計數，每條邊指向父親
• （葉向樹形圖，即每條邊指向兒子，只要修改一個地方）
• 如果要求所有根的樹形圖之和，就求逆的主對角線之和乘以行列式（\(A^*=|A|A^{-1}\)）

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定理

• 有向歐拉圖的歐拉回路總數等于任意根的根向樹形圖個數乘以 \(\Pi(deg(v)-1)!\)（←階乘）（\(deg(v)\) 是 \(v\) 的入度或出度，反正入度等于出度）

Enumerative properties of Ferrers graphs

• 二分圖，左頂點連編號為 \(1,2,...,a_i\) 的右頂點，則該圖的生成樹個數為 \(\dfrac{\prod\limits_{i∈A}deg_i}{\max\limits_{i∈A}deg_i}\cdot\dfrac{\prod\limits_{i∈B}deg_i}{\max\limits_{i∈B}deg_i}\) 左頂點度之積（去掉度最大的）乘以右頂點度之積（去掉度最大的）

Prufer序列

• \(n\) 個點的無根樹與長度 \(n-2\) 值域 \([1,n]\) 的序列有雙射關系，Prufer序列就是其中一種
• 無根樹轉Prufer：設無根樹點數為 \(n\)，每次洗掉度為 \(1\) 且編號最小的結點并把它所連接的點的編號加入Prufer序列，進行 \(n-2\) 次操作
• Prufer轉無根樹：計算每個點的度為在序列中出現的次數加 \(1\)，每次找度為 \(1\) 的編號最小的點與序列中第一個點連接，并將后者的度減 \(1\)
• Cayley定理：完全圖 \(K_n\) 有 \(n^{n-2}\) 棵生成樹
• 擴展：\(k\) 個聯通塊，第 \(i\) 個聯通塊有 \(s_i\)個點，則添加 \(k-1\) 條邊使整個圖聯通的方案數有 \(n^{k-2}\Pi_{i=1}^k s_i\) 個

LGV引理

• DAG上固定 \(2n\) 個點 \([A_1,\cdots,A_n,B_1,\cdots,B_n]\)，若有 \(n\) 條路徑 \([A_1→B_1,\cdots,A_n→B_n]\) 兩兩不相交，則方案數為
• \(M=\left|\begin{array}{c}e(A_1,B_1)&\cdots &e(A_1,B_n)\\\vdots&\ddots&\vdots\\e(A_n,B_1)&\cdots&e(A_n,B_n)\end{array}\right|\)
• 其中 \(e(u,v)\) 表示 \(u→v\) 的路徑計數

others of 圖論雜項

Havel-Hakimi定理

• 給定一個度序列，反向構造出這個圖
• 解：貪心，每次讓剩余度最大的頂點 \(k\) 連接其余頂點中剩余度最大的 \(deg_k\) 個頂點
• （我認為二路歸并比較快，可是找到的代碼都用了sort()）

無向圖三元環計數

• 無向圖定向，\(pii(deg_i,i)>pii(deg_j,j)\Leftrightarrow\) 建立有向邊 \((i,j)\)，然后暴力列舉 \(u\)，將 \(u\) 的所有兒子 \(\omega(u)\) 標記為 \(dcnt\)，暴力列舉 \(v∈\omega(u)\)，若 \(v\) 的兒子被標記為 \(dcnt\) 則 \(ans++\)，\(O(E\log E)\)

字串

• （我字串是最菜的）
• 尋找模式串p在文本串t中的所有出現

哈希×Hash

字串哈希

• 如果不需要區間資訊，可以呼叫 hash<string>()(s) 獲得ull范圍的hash值
• 碰撞概率：單哈希 \(10^6\) 次比較大約有 \(\dfrac 1 {1000}\) 概率碰撞
• 支持查詢子串hash值，初始化 \(O(n)\)，子串查詢 \(O(1)\)

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)};
		#undef q
	}
	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;

質因數哈希

int fac(int n,int c,int mod,const function<int(int)> &f){
	int p=c*c%mod,ans=0;
	for(int i=2;i*i<=n;i++){
		int cnt=0;
		while(n%i==0)n/=i,cnt++;
		ans=(ans+p*f(cnt))%mod;
		p=p*c%mod;
	}
	if(n>1)ans=(ans+qpow(c,n,mod)*f(1))%mod;
	return ans;
}
//例：匹配乘積為x^k（x任意）的兩個數
pii hash1(int n){
	return pii(
		fac(n,101,2147483647,[](int x){return x%k;}),
		fac(n,103,1000000007,[](int x){return x%k;})
	);
}
pii hash2(int n){
	return pii(
		fac(n,101,2147483647,[](int x){return (k-x%k)%k;}),
		fac(n,103,1000000007,[](int x){return (k-x%k)%k;})
	);
}

字串函式

前綴函式×kmp

• \(p[x]\) 表示滿足 s.substr(0,k)==s.substr(x-k,k) 且 \(x\not=k\) 的 \(k\) 的最大值，\(p[0]=0\)
• 線性復雜度

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.push_back(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

• \(z[x]\) 表示滿足 s.substr(0,k)==s.substr(x,k) 的 \(k\) 的最大值，\(z[0]=0\)
• 線性復雜度

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

• 預處理為 "#*A*A*A*A*A*"
• 線性復雜度

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

最小表示法

• 求 \(s\) 重復無數次的字串最小后綴的左端點
• 線性復雜度

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

后綴陣列×SA

• \(sa[i]\) 表示所有后綴中第 \(i\) 小的后綴是 s.substr(sa[i],-1)
• \(rk[i]\) 表示所有后綴中 s.substr(i,-1) 是第 \(rk[i]\) 小
• 編號從 \(1\) 開始！\(O(n\log n)\)

int sa[N],rk[N]; //sa,rk即結果
void get_sa(const string &S){
	static int pre[N*2],id[N],px[N],cnt[N];
	int n=S.length(),m=256;
	const char *const s=S.c_str()-1; //為了編號從1開始
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;w<n;w<<=1){
		int t=0;
		for(int i=n;i>n-w;i--)id[++t]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>w)id[++t]=sa[i]-w;
		mst(cnt,0);
		for(int i=1;i<=n;i++)cnt[px[i]=rk[id[i]]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[px[i]]--]=id[i];
		memcpy(pre,rk,sizeof(rk));
		int p=0;
		static auto pp=[&](int x){return pii(pre[x],pre[x+w]);};
		for(int i=1;i<=n;i++)
			rk[sa[i]]=pp(sa[i])==pp(sa[i-1])?p:++p;
		m=p; //優化計數排序值域
	}
}

• sa可以在同一文本串中在線多次查找模式串（二分查找）

height陣列

• 定義 \(lcp(i,j)=\) 后綴 \(i\) 和后綴 \(j\) 的最長公共前綴長度
• 定義 \(height[i]=lcp(sa[i],sa[i-1])\)，\(height[1]=0\)
• \(height[rk[i]]\ge height[rk[i-1]]-1\)
• 編號從 \(1\) 開始，\(O(n)\)

for(int i=1,k=0;i<=n;i++){
	if(k)k--;
	while(s[i+k]==s[sa[rk[i]-1]+k])k++;
	ht[rk[i]]=k;
}

• 不相等的子串個數為 \(\dfrac{n(n+1)}{2}-\sum\limits_{i=2}^{n}height[i]\)

自動機

字典樹×Trie

• 線性復雜度

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自動機

• 先構建字典樹，再構建fail樹和字典圖
• 線性復雜度

struct AC{
	static const int sigma=26,c0='a'; //小寫字母
	struct node{
		int to[sigma],fail,trie_cnt,cnt;
		int &operator[](int x){return to[x];}
		//vector<int> p; //指向模式串集合
	}a[N];
	int t;
	vector<int> q; //存了bfs序
	void init(){t=0; a[t++]=node(); q.clear();}
	void insert(const char s[]/*,int ptr*/){ //將模式串插入字典樹
		int k=0;
		for(int i=0;s[i];i++){
			int c=s[i]-c0;
			if(!a[k][c])a[k][c]=t,a[t++]=node();
			k=a[k][c];
		}
		a[k].trie_cnt++;
		//a[k].p.push_back(ptr);
	}
	void build(){ //構建fail樹，將字典樹擴展為圖
		int tail=0;
		repeat(i,0,sigma)
		if(a[0][i])
			q.push_back(a[0][i]);
		while(tail!=(int)q.size()){
			int k=q[tail++];
			repeat(i,0,sigma)
			if(a[k][i])
				a[a[k][i]].fail=a[a[k].fail][i],q.push_back(a[k][i]);
			else
				a[k][i]=a[a[k].fail][i];
		}
	}
	void query(const char s[]){ //記錄文本串中模式串出現次數
		int k=0;
		for(int i=0;s[i];i++){
			int c=s[i]-c0;
			k=a[k][c];
			a[k].cnt++; //fail樹上差分
			//for(int kk=k;kk!=0;kk=a[kk].fail)
			//for(auto p:a[kk].p)
				//ans[p]++; //代替下面的反向遍歷，我也不知道什么時候用
		}
		repeat_back(i,0,q.size()){ //反向遍歷bfs序
			a[a[q[i]].fail].cnt+=a[q[i]].cnt; //差分求和
			//for(auto p:a[q[i]].p)ans[p]=a[q[i]].cnt; //反饋答案
		}
	}
}ac;

后綴自動機×SAM

• 給定字串中所有子串對應了SAM中從源點出發的一條路徑
• SAM是一個DAG，至多有 \(2n-1\) 個結點和 \(3n-4\) 條邊
• 每個結點表示一個endpos等價類，對應子串長度區間 \([a[a[i].fa].len+1,a[i].len]\)
• 構造 \(O(n)\)，編號從 \(1\) 開始（\(a[1]\) 表示源點）

struct SAM{
	static const int sigma=26,c0='a'; //小寫字母
	struct node{
		int to[sigma],fa,len;
		int &operator[](int x){return to[x];}
	}a[N*2];
	int last,tot;
	void init(){last=tot=1;}
	int add(){a[++tot]=node(); return tot;}
	void push(int c){
		c-=c0;
		int x=last,nx=last=add();
		a[nx].len=a[x].len+1;
		for(;x && a[x][c]==0;x=a[x].fa)a[x][c]=nx;
		if(x==0)a[nx].fa=1;
		else{
			int p=a[x][c];
			if(a[p].len==a[x].len+1)a[nx].fa=p;
			else{
				int np=add();
				a[np]=a[p]; a[np].len=a[x].len+1;
				a[p].fa=a[nx].fa=np;
				for(;x && a[x][c]==p;x=a[x].fa)a[x][c]=np;
			}
		}
	}
}sam;
//構造：for(auto i:s)sam.push(i);

雜項

位運算

位運算巨佬操作

• 中點向下取整 (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)

#define B(x,i) ((x>>i)&1) //回傳x的第i位
#define Bswap(x,i,j) (B(x,i)^B(x,j)) && (x^=(1ll<<i)|(1ll<<j)) //交換x的i位和j位
#define Bset(x,i,b) (B(x,i)^b) && (x^=(1ll<<i)) //將x的第i位賦值為b

位運算函式

• （不需要頭檔案）

__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的個數是否為奇數

列舉二進制子集

• 列舉二進制數m的非空子集

for(int s=m;s;s=(s-1)&m){
	work(s);
}

• 列舉n個元素的大小為k的二進制子集（要保證k不等于0）

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 eps=1e-11;
if(abs(x)<eps)x=abs(x); //輸出浮點數的預處理

浮點數常量

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

常數優化

估計函式用時

• clock() 可以獲取時刻，單位毫秒，運行函式前后的時間之差即為用時
• 一些巨佬測出來的結論：

- 整數加減：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;

吸氧氣

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

其他優化

//（都是聽說的）
1ll*a 比 (ll)a 快
取模：x%mod 優化為 x<mod?x:x%mod
減少浮點除法：a/b+c/d 優化為 (a*d+b*c)/(b*d)
精度足夠時用ll代替浮點型別
多路并行運算，如 (a+b)+(c+d) 比 ((a+b)+c)+d 快
加上inline，以及強制行內__inline __attribute__((always_inline))
多重for回圈時，修改for的順序保證記憶體連續訪問
多使用區域變數

在TLE邊緣試探

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

對拍

#include<bits/stdc++.h>
using namespace std;
int main(){
	for(int i=0;;i++){
		if(i%10==0)cerr<<i<<endl;
		system("gen.exe > test.in");
		system("test1.exe < test.in > a.out");
		system("test2.exe < test.in > b.out");
		if(system("fc a.out b.out")){
			system("pause");
			return 0;
		}
	}
}

備選

#include<bits/stdc++.h>
using namespace std;
ifstream a,b;
int main(){
	for(int i=0;;i++){
		if(i%10==0)cerr<<i<<endl;
		system("datamaker.exe > data.txt");
		system("A.exe < data.txt > a.out");
		system("B.exe < data.txt > b.out");
		a.open("a.out");
		b.open("b.out");
		while(a.good() || b.good()){
			if(a.get()!=b.get()){
				system("pause");
				return 0;
			}
		}
		a.close(),b.close();
	}
}

戰術分析 坑點

（我真的真的真的太南了）

ll t; 1<<t回傳int，必須是1ll<<t
int x; x<<y的y會先對32取模
operator<的比較內容一定要寫完整
試一試輸入^Z能否結束
無向圖輸入要給兩個值賦值g[x][y]=g[x][y]=1
多組輸入時，圖記得初始化
建模的轉換函式的宏定義一定要加括號，或者寫成函式
多想想極端資料！！
islower()等函式回傳值不一定是0或1
多用相空間角度思考問題
記憶體比我想象的要大一些（有時候1e7可以塞下）
在64位編譯器（我的編譯器）中set每個元素需要額外32位元組記憶體
struct里放大陣列，最好用vector代替
deque占用很大很大的記憶體

數學

數論

基本操作

模乘 模冪 模逆 擴歐

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

階乘 組合數

• \(O(n)\) 初始化，\(O(1)\) 查詢

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,1,N)inv[i-1]=inv[i]*i%mod;
	}
	ll operator()(ll a,ll b){ //a>=b
		if(a<b || b<0)return 0;
		return fac[a]*inv[a-b]%mod*inv[b]%mod;
	}
	ll A(ll a,ll b){ //a>=b
		if(a<b || b<0)return 0;
		return fac[a]*inv[a-b]%mod;
	}
}C;

防爆模乘

//int128版本
ll mul(ll a,ll b,ll m=mod){return (__int128)a*b%m;}
//long double版本（欲防爆，先自爆）（注意在測驗的時候不知道為什么有鍋）
ll mul(ll a,ll b,ll m=mod){return (a*b-ll((long double)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
}

• 實數gcd

lf fgcd(lf a,lf b){return abs(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

• 求 \(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[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;
}

階與原根

• 判斷是否有原根：若 \(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(n\log\log n)\) 實際遠遠不到

ll getG(ll n){ //求n最小的原根
	static vector<ll> a; a.clear();
	ll 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;
	}
	return -1; 
}

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=mul(now,ps,mod))
		ans.push_back(now);
	sort(ans.begin(),ans.end());
}

數論函式的生成

單個歐拉函式

• \(\varphi(n)=\) 小于 n 且與 n 互質的正整數個數
• 令 n 的唯一分解式 \(n=Π({p_k}^{a_k})\)，則 \(\varphi(n)=n\cdot Π(1-\dfrac 1 {p_k})\)
• \(O(\sqrt n)\)

int getphi(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;
	}
}

線性篩

• 定理：求出 \(f(p)\)（\(p\) 為質數）的復雜度不超過 \(O(\log p)\) 的積性函式可以被線性篩

篩素數

• a[i] 表示第 \(i+1\) 個質數，vis[i]==0 表示 \(i\) 是素數，rec[i] 為 \(i\) 的最小質因數
• \(O(n)\)

bool vis[N]; int rec[N]; vector<int> a;
void get_prime(){
	vis[1]=1;
	repeat(i,2,N){
		if(!vis[i])a.push_back(i),rec[i]=i;
		for(auto j:a){
			if(i*j>=N)break;
			vis[i*j]=1; rec[i*j]=j;
			if(i%j==0)break;
		}
	}
}

篩歐拉函式

• 線性版，\(O(n)\)

bool vis[N]; int phi[N]; vector<int> a;
void get_phi(){
	vis[1]=1; phi[1]=1;
	repeat(i,2,N){
		if(!vis[i])a.push_back(i),phi[i]=i-1;
		for(auto j:a){
			if(i*j>=N)break;
			vis[i*j]=1;
			if(i%j==0){phi[i*j]=phi[i]*j; break;}
			phi[i*j]=phi[i]*(j-1);
		}
	}
}

• 不是線性但節省力氣和空間版，\(O(n\log\log n)\)

void get_phi(){
	phi[1]=1; //其他的值初始化為0
	repeat(i,2,N)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)\)

bool vis[N]; int mu[N]; vector<int> a;
void get_mu(){
	vis[1]=1; mu[1]=1;
	repeat(i,2,N){
		if(!vis[i])a.push_back(i),mu[i]=-1;
		for(auto j:a){
			if(i*j>=N)break;
			vis[i*j]=1;
			if(i%j==0){mu[i*j]=0; break;}
			mu[i*j]=-mu[i];
		}
	}
}

篩其他函式

• 篩約數個數

bool vis[N]; int d[N]; vector<int> a;
void get_d(){
	vector<int> c(N); vis[1]=1; d[1]=1,c[1]=0;
	repeat(i,2,N){
		if(!vis[i])a.push_back(i),d[i]=2,c[i]=1;
		for(auto j:a){
			if(i*j>=N)break;
			vis[i*j]=1;
			if(i%j==0){
				d[i*j]=d[i]/(c[i]+1)*(c[i]+2);
				c[i*j]=c[i]+1;
				break;
			}
			d[i*j]=d[i]*2,c[i*j]=1;
		}
	}
}

• 篩gcd

int gcd[N][N];
void get_gcd(int n,int m){
	repeat(i,1,n+1)
	repeat(j,1,m+1)
	if(!gcd[i][j])
	repeat(k,1,min(n/i,m/j)+1)
		gcd[k*i][k*j]=k;
}

min_25篩

• 求 \([1,n]\) 內的素數個數

#include<cstdio>
#include<math.h>
#define ll long long
const int N = 316300;
ll n, g[N<<1], a[N<<1];
int id, cnt, sn, prime[N];
inline int Id(ll x){return x<=sn?x:id-n/x+1;}
int main() {
	scanf("%lld", &n), sn=sqrt(n);
	for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=a[id]-1;
	for(int i=2; i<=sn; ++i) if(g[i]!=g[i-1]){
		// 這里 i 必然是質數，因為 g[] 是前綴質數個數
		// 當 <i 的質數的倍數都被篩去，讓 g[] 發生改變的位置只能是下一個質數
		// 別忘了 i<=sn 時，ID(i) 就是 i，
		prime[++cnt]=i;
		ll sq=(ll)i*i;
		for(int j=id; a[j]>=sq; --j) g[j]-=g[Id(a[j]/i)]-(cnt-1);
	}
	return printf("%lld\n", g[id]), 0;
}

素數約數相關

唯一分解 質因數分解

• 用陣串列示數字唯一分解式的素數的指數，如 \(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; //乘法就是multiset
	fac(){mst(a,0); s.clear();}
	void lcm(ll n){ //self=lcm(self,n)
		repeat(i,2,facN)
		if(n%i==0){
			ll 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(){ //return self%mod
		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

• 樸素演算法，\(O(\sqrt n)\)

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

• Miller-Rabin素性測驗，\(O(10\cdot\log^3 n)\)

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

• \(O(n^{\tfrac 1 4})\)，基于MR素性測驗（很遺憾的是，我不擅長卡常因此這個板子過不了洛谷P4718）

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); //記錄約數
}

反素數生成

• 求因數最多的數（因數個數一樣則取最小）
• 性質：\(M = {p_1}^{k_1}{p_2}^{k_2}...\) 其中，\(p_i\) 是從 \(2\) 開始的連續質數，\(k_i-k_{i+1}∈\{0,1\}\)
• 先打出質數表再 \(dfs\)，列舉 \(k_n\)，\(O(\exp)\)

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=r-l+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;
}

二次剩余

• 對于奇素數模數 \(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}\) 的符號為 \((\dfrac p q)\) ，則對奇素數 \(p,q\) 有 \((\dfrac p q)\cdot(\dfrac q p)=(-1)^{\tfrac{p-1}2\cdot\tfrac{q-1}2}\)
• 求二次剩余，要求 mod 是質數，sqrtmod() 回傳其中一個 sqrt，另一個為 mod 減這個回傳值（如果 mod=2 就沒有第二個）；回傳 \(-1\) 表示無解

ll w;
struct vec{ //x+y*sqrt(w)
	ll x,y;
	vec operator*(vec b){
		return {(x*b.x+y*b.y%mod*w)%mod,(x*b.y+y*b.x)%mod};
	}
};
vec qpow(vec a,ll b){
	vec ans={1,0};
	for(;b;a=a*a,b>>=1)
		if(b&1)ans=ans*a;
	return ans;
}
ll Leg(ll a){return qpow(a,(mod-1)>>1,mod)!=mod-1;}
ll sqrtmod(ll b){
	if(mod==2)return 1;
	if(!Leg(b))return -1;
	ll a;
	do{a=rnd()%mod; w=((a*a-b)%mod+mod)%mod;}while(Leg(w));
	return qpow({a,1},(mod+1)>>1).x;
}

莫比烏斯反演

• 引理1：\(\lfloor \dfrac{a}{bc}\rfloor=\lfloor \dfrac{\lfloor \dfrac{a}{b}\rfloor}{c}\rfloor\)；引理2：\(n\) 的因數個數 \(≤\lfloor 2\sqrt n \rfloor\)
• 狄利克雷卷積：\((f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac n d)\)，有交換律、結合律、對加法的分配律
• 積性函式：\(\{f(n)|\gcd(n,m)=1\Rightarrow f(nm)=f(n)f(m)\}\)
• 單位函式：\(\varepsilon(n)=[n=1]\) 為狄利克雷卷積的單位元
• 恒等函式：\(id(n)=n\)
• 約數個數：\(d(n)=1*1\)
• 約數之和：\(\sigma(n)=1*id\)
• 莫比烏斯函式性質：\(\mu(n)=\begin{cases} 1&n=1\\0&n含有平方因子\\(-1)^k&k為n的質因數個數\end{cases}\)
• 結論：\((\forall f)(f*\varepsilon=f),\mu*1=\varepsilon,\varphi*1=id,d*\mu=id\)
• 莫比烏斯反演：若\(f=g*1\)，則\(g=f*\mu\)；或者，若\(f(n)=\sum\limits_{d|n}g(d)\)，則\(g(n)=\sum\limits_{d|n}\mu(d)f(\dfrac n d)\)

---

• 例題：求模意義下的 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^m \dfrac{i\cdot j}{\gcd(i,j)}\)
• \(ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j,\gcd(\frac i d,\frac j d)=1}\dfrac{i\cdot j}d\)
• 非常經典的化法：
• \(ans=\sum\limits_{d=1}^n d\cdot\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1]i\cdot j\)
• 設 \(sum(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]i\cdot j\)
• \(sum(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{c|i,c|j}{\mu(c)}\cdot i\cdot j\)
• 設 \(i'=\dfrac i c,j'=\dfrac j c\)
• \(sum(n,m)=\sum\limits_{c=1}^n\mu(c)\cdot c^2\cdot\sum\limits_{i'=1}^{\lfloor\frac nc\rfloor}\sum\limits_{j'=1}^{\lfloor\frac mc\rfloor} i'\cdot j'\)
• 易得 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} i\cdot j=\dfrac 1 4 n(n+1) m(m+1)\)

杜教篩

• \(g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^n g(i)S(\lfloor\dfrac n i \rfloor),S(n)=\sum\limits_{i=1}^nf(i)\)
• 如果能找到合適的 \(g(n)\)，能快速計算 \(\sum\limits_{i=1}^n(f*g)(i)\)，就能快速計算 \(S(n)\)
• \(f(n)=\mu(n),g(n)=1,(f*g)(n)=[n=1]\)
• \(f(n)=\varphi(n),g(n)=1,(f*g)(n)=n\)
• \(f(n)=n\cdot\varphi(n),g(n)=n,(f*g)(n)=n^2\)
• \(f(n)=d(n),g(n)=\mu(n),(f*g)(n)=1\)
• \(f(n)=\sigma(n),g(n)=\mu(n),(f*g)(n)=n\)（但是用公式 \(\sum\limits_{i=1}^{n}\sigma(n)=\sum\limits_{i=1}^{n}i\cdot\lfloor\dfrac n i\rfloor\) 更好）
• \(O(n^{\tfrac 2 3})\)，注意有遞回的操作就要記憶化

struct DU{
	static const int N=2000010;
	int sum[N];
	DU(){
		vector<int> a,mu(N,1),vis(N,0);
		repeat(i,2,N){
			if(!vis[i])a.push_back(i),mu[i]=-1;
			for(auto j:a){
				if(i*j>=N)break;
				vis[i*j]=1;
				if(i%j==0){mu[i*j]=0; break;}
				mu[i*j]=-mu[i];
			}
		}
		repeat(i,1,N)sum[i]=sum[i-1]+mu[i];
	}
	ll sum_mu(ll n){
		if(n<N)return sum[n];
		static map<ll,ll> rec; if(rec.count(n))return rec[n];
		ll ans=1;
		for(ll l=2,r;l<=n;l=r+1){
			r=n/(n/l);
			ans-=sum_mu(n/l)*(r-l+1);
		}
		return rec[n]=ans;
	}
	ll sum_phi(ll n){
		ll ans=0;
		for(ll l=1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans+=(sum_mu(r)-sum_mu(l-1))*(n/l)*(n/l);
		}
		return ((ans-1)>>1)+1;
	}
	ll sum_d(ll n){
		static map<ll,ll> rec; if(rec.count(n))return rec[n];
		ll ans=n;
		for(ll l=2,r;l<=n;l=r+1){
			r=n/(n/l);
			ans-=(sum_mu(r)-sum_mu(l-1))*sum_d(n/l);
		}
		return rec[n]=ans;
	}
	ll sum_sigma(ll n){
		ll ans=0;
		for(ll l=1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans+=(l+r)*(r-l+1)/2*(n/l);
		}
		return ans;
	}
}du;

斐波那契數列

• 定義：\(F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}\)
• \(F_n=\dfrac 1 {\sqrt{5}} [(\dfrac{1+\sqrt 5}2)^n-(\dfrac{1-\sqrt 5}2)^n)]\) （公式中若 \(5\) 是二次剩余則可以化簡，比如 \(\sqrt 5\equiv 383008016\pmod {1000000009}\)）
• \(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\) 型素數時，\(\begin{cases} F_{p-1}\equiv 0\pmod p \\ F_p\equiv 1\pmod p \\ F_{p+1}\equiv 1\pmod p \end{cases}\)
• 當 \(p\) 為 \(5k\pm 2\) 型素數時，\(\begin{cases} F_{p-1}\equiv 1\pmod p \\ F_p\equiv -1\pmod p \\ F_{p+1}\equiv 0\pmod p \end{cases}\)
• \(F_{n+2}\) 為集合 {1,2,3,...,n-2} 中不包含相鄰正整數的子集個數（包括空集）
• F(n)%m 的周期 \(\le 6m\)（\(m=2\times 5^k\) 取等號）
• 齊肯多夫定理：任何正整數都可以表示成若干個不連續的斐波那契數（\(F_2\) 開始）可以用貪心實作

快速倍增法求\(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};
}

佩爾方程×Pell

• \(x^2-dy^2=1\)，\(d\) 是正整數
• 若 \(d\) 是完全平方數，只有平凡解 \((\pm 1,0)\)，其余情況總有非平凡解
• 若最小正整數解 \((x_1,y_1)\)，則遞推公式
• \(\begin{cases}x_n=x_1x_{n-1}+dy_1y_{n-1}\\y_n=y_1x_{n-1}+x_1y_{n-1}\end{cases}\)
• \(\left[\begin{array}{c}x_n\\y_n\end{array}\right]=\left[\begin{array}{cc}x_1 & dy_1\\y_1 & x_1\end{array}\right]\left[\begin{array}{c}x_{n-1}\\y_{n-1}\end{array}\right]\)
• 最小解（可能溢位）

bool PQA(ll D, ll &x, ll &y){
	ll d=llround(sqrt(D));
	if(d*d==D)return 0;
	ll u=0,v=1,a=int(sqrt(D)),a0=a,lastx=1,lasty=0;
	x=a,y=1;
	do{
		u=a*v-u; v=(D-u*u)/v;
		a=(a0+u)/v;
		ll thisx=x,thisy=y;
		x=a*x+lastx; y=a*y+lasty;
		lastx=thisx; lasty=thisy;
	}while(v!=1 &&a<=a0);
	x=lastx; y=lasty;
	if(x*x-D*y*y==-1){
		x=lastx*lastx+D*lasty*lasty;
		y=2*lastx*lasty;
	}
	return 1;
}

組合數學

組合數取模 | 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
• \(qfac.A(x),qfac.B(x)\) 滿足 \(A\equiv \dfrac{x!}{p^B}\pmod {p^k}\)
• \(qfac.C(a,b)\equiv C_a^b \pmod {p^k}\)
• \(exlucas(a,b,m)\equiv C_a^b \pmod m\)，函式內嵌中國剩余定理

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

康托展開+逆 編碼與解碼

康托展開+逆

• 康托展開即排列到整數的映射
• 排列里的元素都是從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;
}

編碼與解碼問題

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

• 給定編號求字串，對每一位進行嘗試即可

置換群計數

Polya定理

• 例：立方體 \(n=6\) 個面，每個面染上 \(m=3\) 種顏色中的一種
• 兩個染色方案相同意味著兩個立方體經過旋轉可以重合
• 其染色方案數為：\(\dfrac{\sum m^{k_i}}{|k|}\)（\(k_i\) 為某一置換可以拆分的回圈置換數，\(|k|\) 為所有置換數）

不旋轉，{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個

• 因此 \(\dfrac{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;

組合數學的一些結論

---

組合數

• C(n,k)=(n-k+1)*C(n,k-1)/k?

const int N=20;
repeat(i,0,N){
	C[i][0]=C[i][i]=1;
	repeat(j,1,i)C[i][j]=C[i-1][j]+C[i-1][j-1];
}

• 二項式反演
• \(\displaystyle f_n=\sum_{i=0}^n{n\choose i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}f_i\)
• \(\displaystyle f_k=\sum_{i=k}^n{i\choose k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}{i\choose k}f_i\)

---

• 卡塔蘭/卡特蘭數×Catalan，\(H_n=\dfrac{\binom{2n}n}{n+1}\)，\(H_n=\dfrac{H_{n-1}(4n-2)}{n+1}\)

---

• 貝爾數×Bell，劃分n個元素的集合的方案數

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

---

• 錯排數，\(D_n=n![\dfrac 1{0!}-\dfrac 1{1!}+\dfrac 1{2!}-...+\dfrac{(-1)^n}{n!}]\)

D[0]=1;
repeat(i,0,N-1){
	D[i+1]=D[i]+(i&1?C.inv[i+1]:mod-C.inv[i+1]);
	D[i]=1ll*D[i]*fac[i]%mod;
}

---

第一類斯特林數×Stirling

• 多項式 \(x(x-1)(x-2) \cdots (x-n+1)\) 展開后 \(x^r\) 的系數絕對值記作 \(s(n,r)\) （系數符號 \((-1)^{n+r}\)）
• 也可以表示 \(n\) 個元素分成 \(r\) 個環的方案數
• 遞推式 \(s(n,r) = (n-1)s(n-1,r)+s(n-1,r-1)\)
• \(\displaystyle n!=\sum_{i=0}^n s(n,i)\)
• \(\displaystyle A_x^n=\sum_{i=0}^n s(n,i)(-1)^{n-i}x^i\)
• \(\displaystyle A_{x+n-1}^n=\sum_{i=0}^n s(n,i)x^i\)

---

第二類斯特林數×Stirling

• \(n\) 個不同的球放入 \(r\) 個相同的盒子且無空盒的方案數，記作 \(S(n,r)\) 或 \(S_n^r\)
• 遞推式 \(S(n,r) = r S(n-1,r) + S(n-1,r-1)\)
• 通項公式 \(\displaystyle S(n,r)=\frac{1}{r!}\sum_{i=0}^r(-1)^i{r\choose i}(r-i)^n\)
• \(\displaystyle m^n=\sum_{i=0}^mS(n,i)A_m^i\)
• \(\displaystyle \sum_{i=1}^n i^k=\sum_{i=0}^kS(k,i)i!{n+1\choose i+1}\)
• 斯特林反演
• \(\displaystyle f(n)=\sum_{i=1}^n S(n,i)g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}s(n,i)f(i)\)

---

• \(a\) 個相同的球放入 \(b\) 個不同的盒子，方案數為 \(C_{a+b-1}^{b-1}\)（隔板法）

---

• 一個長為 \(n+m\) 的陣列，\(n\) 個 \(1\)，\(m\) 個 \(-1\)，限制前綴和最大為 \(k\)，則方案數為 \(C_{n+m}^{m+k}-C_{n+m}^{m+k+1}\)

---

• \(2n\) 個帶標號的點兩兩匹配，方案數為 \((2n-1)!!=\dfrac{(2n)!}{2^nn!}\)
• \(1,2,...,n\) 中無序地選擇 \(r\) 個互不相同且互不相鄰的數字，則這 \(r\) 個數字之積對所有方案求和的結果為 \(C_{n+1}^{2r}(2r-1)!!=\dfrac{C_{n+1}^{2r}(2r)!}{2^rr!}\)（問題可以轉換為，\((n+1)\) 個點無序匹配 \(r\) 對點的方案數）

int M(int a,int b){
	static const int inv2=qpow(2,mod-2);
	return C(a+1,2*b)*C.fac[2*b]%mod*qpow(inv2,b)%mod*C.inv[b]%mod;
}

---

博弈論

SG函式 SG定理

• 有向無環圖中，兩個玩家輪流推多顆棋子，不能走的判負
• 假設 \(x\) 的后繼狀態為 \(y_1,y_2,...,y_k\)
• 則 \(SG[x]=mex\{SG[y_i]\}\)，\(mex(S)\) 表示不屬于集合 \(S\) 的最小自然數
• 當且僅當所有起點SG值的異或和為 \(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游戲

---

Nim

• \(n\) 堆石子 \(a_1,a_2,...,a_n\)，每次選擇 \(1\) 堆石子拿任意非空的石子，拿不了的人失敗
• \(SG_i=a_i,NimSum=\oplus\{SG_i\}\)，先手必敗當且僅當 \(NimSum=0\)
• 注：先手必勝策略是找到滿足 (a[i]>>(63-__builtin_clzll(NimSum)))&1 的 \(a[i]\)，并取走 \(a[i]-a[i]\oplus NimSum\) 個石子
• Bash Game：一堆石子 \(n\)，最多取 \(k\) 個，\(SG=n\%(k+1)\)

---

Moore's Nimk

• \(n\) 堆石子，每次最多選取 \(k\) 堆石子，選中的每一堆都取走任意非空的石子
• 先手必勝當且僅當
  • 存在 \(t\) 使得 sum{(a[i]>>t)&1}%(k+1)!=0

---

擴展威佐夫博弈×Extra Wythoff's Game

• 兩堆石子，分別為 \(a,b\)，每次取一堆的任意非空的石子或者取兩堆數量之差的絕對值小于等于 \(k\) 的石子
• 解：假設 \(a\le b\)，當且僅當存在自然數 \(n\) 使得 \(a=\lfloor n\dfrac{\sqrt{(k+1)^2+4}-(k-1)}2\rfloor,b=a+n(k+1)\)，先手必敗
• Betty定理與Betty數列：\(\alpha,\beta\) 為正無理數且 \(\dfrac 1 {\alpha}+\dfrac 1 {\beta}=1\)，數列 \(\{\lfloor \alpha n\rfloor\},\{\lfloor \beta n\rfloor\},n=1,2,...\) 無交集且覆寫正整數集合

---

斐波那契博弈×Fibonacci Nim

• 一堆石子 \(n,n\ge 2\)，先手第一次只能取 \([1,n-1]\)，之后每次取的石子數不多于對手剛取的石子數的 \(2\) 倍且非空
• 先手必敗當且僅當 \(n\) 是Fibonacci數

---

階梯Nim×Staircase Nim

• \(n\) 堆石子，每次選擇一堆取任意非空的石子放到前一堆，第 \(1\) 堆的石子可以放到第 \(0\) 堆
• 先手必敗當且僅當奇數堆的石子數異或和為 \(0\)

---

Lasker's Nim

• \(n\) 堆石子，每次可以選擇一堆取任意非空石子，或者選擇某堆至少為 \(2\)，分成兩堆非空石子
• \(SG(0)=0,SG(4k+1)=4k+1,SG(4k+2)=4k+2,SG(4k+3)=4k+4,SG(4k+4)=4k+3\)

---

k倍動態減法博弈

• 一堆石子 \(n,n\ge 2\)，先手第一次只能取 \([1,n-1]\)，之后每次取的石子數不多于對手剛取的石子數的 \(k\) 倍且非空

int calc(ll n,int k){ //n<=1e8,k<=1e5
	static ll a[N],b[N],ans; //N=750010
	int t=1;
	a[1]=b[1]=1;
	for(int j=0;;){
		t++,a[t]=b[t-1]+1;
		if(a[t]>=n)break;
		while(a[j+1]*k<a[t])j++;
		b[t]=a[t]+b[j];
	}
	while(a[t]>n)t--;
	if(a[t]==n)return -1;
	while(n){
		while(a[t]>n)t--;
		n-=a[t]; ans=a[t];
	}
	return ans;
}

---

Anti-SG | SJ定理

• \(n\) 個游戲，移動不了的人獲勝
• 先手必勝當且僅當
  • \((\forall i)SG_i\le 1\) 且 \(NimSum=0\)
  • \((\exist i)SG_i>1\) 且 \(NimSum\not=0\)

---

Every-SG

• \(n\) 個游戲，每次都要移動所有可移動的游戲
• 對于先手來說，必勝態的游戲要越長越好，必敗態的游戲要越短越好
• u是終止態，step(u)=0
• u->v,SG(u)=0,SG(v)>0，step(u)=max(step(v))+1
• u->v,SG(v)=0，step(u)=min(step(v))+1
• 先手必勝當且僅當所有游戲的step的最大值為奇數

刪邊游戲×Green Hachenbush

• 樹上刪邊游戲
  • 一棵有根樹，每次可以洗掉一條邊并移除不和根連接的部分
  • 葉子的 \(SG\) 為 \(0\)，非葉子的 \(SG\) 為(所有兒子的 \(SG\) 值 \(+1\))的異或和
• 無向圖刪邊游戲
  • 奇環可以縮為一個點加一條邊，偶環可以縮為一點，變為樹上刪邊游戲

翻硬幣游戲

• \(n\) 枚硬幣排成一排，玩家的操作有一定約束，并且翻動的硬幣中，最右邊的必須是從正面翻到反面，不能操作的玩家失敗
• 定理：局面的 \(SG\) 值等于所有正面朝上的硬幣單一存在時的 \(SG\) 值的異或和（把這個硬幣以外的所有硬幣翻到反面后的局面的 \(SG\) 值）
• 編號從 \(1\) 開始
  • 每次翻一枚或兩枚硬幣 \(SG(n)=n\)
  • 每次翻轉連續的 \(k\) 個硬幣 \(SG(n)=[n\%k=0]\)
  • Ruler Game，每次翻轉一個區間的硬幣，\(SG(n)=lowbit(n)\)
  • Mock Turtles Game，每次翻轉不多于 \(3\) 枚硬幣 \(SG(n)=2n-1-popcount(n-1)\%2\)

高維組合游戲 | Nim積

• Nim和與Nim積的關系類似加法與乘法
• Tartan定理：對于一個高維的游戲（多個維度的笛卡爾積），玩家的操作也是笛卡爾積的形式，那么對每一維度單獨計算SG值，最終的SG值為它們的Nim積
• 比如，在 \(n\times m\) 硬幣中翻轉 \(4\) 個硬幣，\(4\) 個硬幣構成一個矩形，這個矩形是每一維度（翻轉兩個硬幣）的笛卡爾積
• \(O(\log^2 n)\)

struct Nim{
	ll rec[256][256];
	ll f(ll x,ll y,int len=32) {
		if(x==0 || y==0) return 0;
		if(x==1 || y==1) return x*y;
		if(len<=4 && rec[x][y]) return rec[x][y];
		ll xa=x>>len,xb=x^(xa<<len),ya=y>>len,yb=y^(ya<<len);
		ll a=f(xb,yb,len>>1),b=f(xa^xb,ya^yb,len>>1),c=f(xa,ya,len>>1),d=f(c,1ll<<(len-1),len>>1);
		ll ans=((b^a)<<len)^a^d;
		if(len<=4)rec[x][y]=ans;
		return ans;
	}
}nim;
//int x=read(),y=read(),z=read();
//ans^=nim.f(SG(x),nim.f(SG(y),SG(z)));

不平等博弈 | 超現實數

---

• 超現實數(Surreal Number)
• 超現實數由左右集合構成，是最大的兼容四則運算的全序集合，包含實數集和“無窮大”
• 博弈局面的值可以看作左玩家比右玩家多進行的次數，獨立的局面可以相加
• 如果值 \(>0\) 則左玩家必勝，\(<0\) 則右玩家必勝，\(=0\) 則后手必勝
• 一個博弈局面，\(L\) 為左玩家操作一次后的博弈局面的最大值，\(R\) 為右玩家操作一次后的博弈局面的最小值，那么該博弈局面的值 \(G=\dfrac A {2^B},L<G<R\)，并且 \(B\) 盡可能小（\(B=0\) 則 \(|A|\) 盡可能小）
• 如果存在 \(L=R\) 需要引入Irregular surreal number就不討論了（比如兩個玩家能進行同一操作即Nim）

---

• Blue-Red Hackenbush string
• 若干個 BW 串，player-W 只能拿 W，player-B 只能拿 B，每次拿走一個字符后其后綴也會消失，最先不能操作者輸
• 對于每個串計算超現實數(Surreal Number)并求和，若 \(> 0\) 則 W 必勝；若 \(= 0\) 則后手必勝；若 \(< 0\) 則 B 必勝

ll calc(char s[]){
	int n=strlen(s);
	ll ans=0,k=1LL<<50; int i;
	for(i=0;i<n && s[i]==s[0];i++)
		ans+=(s[i]=='W'?k:-k);
	for(;i<n;i++)
		k>>=1,ans+=(s[i]=='W'?k:-k);
	return ans;
}

int ans[N];
void calc(char s[]){
	int n=strlen(s);
	int p=0; while(s[p]==s[0])p++;
	ans[0]+=(s[0]=='W'?p:-p);
	repeat(i,p,n)ans[i-p+1]+=(s[i]=='W'?1:-1);
}
void adjust(){
	repeat_back(i,1,N)
		ans[i-1]+=ans[i]/2,ans[i]%=2;
}

---

• Blue-Red Hackenbush tree
• 若干棵樹，點權為 W 或 B，player-W 只能刪 W，player-B 只能刪 B，每次刪點后與根不相連部分也移除
• 對于 W 點，先求所有兒子的值之和 \(x\)，如果 \(x \ge 0\)，那么直接加一即可，否則 \(x\) 變為 \(x\) 的小數部分加一，乘以 \(2^{-\lfloor|x|\rfloor}\)

---

• Alice's Game
• \(x\times y\) 方格，如果 \(x>1\) Alice可以水平切，如果 \(y>1\) Bob可以垂直切，超現實數計算如下

ll calc(int x,int y){ //get surreal number
	while(x>1 && y>1)x>>=1,y>>=1;
	return x-y;
}

---

其他博弈結論

---

歐幾里得的游戲

• 兩個數 \(a,b\)，每次對一個數刪去另一個數的整數倍，出現 \(0\) 則失敗
• \(a\ge 2b\) 則先手必勝，否則遞回處理

---

無向點地理問題×Undirected vertex geography problem

• 二分圖上移動棋子，不能經過重復點
• 先手必敗當且僅當存在一個不包含起點的最大匹配

---

• 1到n，每次拿一個數或差值為1的兩個數
  • 先手必勝，第一步拿最中間的1/2個數，之后對稱操作
• \(n\times m\) 棋盤上兩個棋子，每次雙方可以操控自己的棋子移動到同一行/列的位置，不能經過對方棋子所在行/列
  • 后手必勝當且僅當兩個棋子的橫坐標之差等于縱坐標之差
• 2個數字，每次把一個數字減少，最小1，但是不能出現重復數字
  • \(SG(a,b)=((a-1)\oplus(b-1))-1\)
• 3個數字，每次把一個數字減少，最小1，但是不能出現重復數字
  • 后手必勝當且僅當 \(a\oplus b\oplus c=0\)

---

代數結構

置換群

• 求 \(A^x\)，編號從 \(0\) 開始，\(O(n)\)

void qpow(int a[],int n,int x){
	static int rec[N],c[N];
	static bool vis[N];
	fill(vis,vis+n,0);
	repeat(i,0,n)if(!vis[i]){
		int cnt=0; rec[cnt++]=i;
		for(int p=a[i];p!=i;p=a[p])
			rec[cnt++]=p,vis[p]=1;
		repeat(J,0,cnt)
			c[rec[J]]=a[rec[(J+x-1)%cnt]];
		repeat(J,0,cnt)
			a[rec[J]]=c[rec[J]];
	}
}

• \(A^k=B\) 求任一 \(A\)，編號從 \(0\) 開始，\(O(n)\)（暫無判斷有解操作）

repeat(i,0,n){
	a[read()-1]=i;
	vis[i]=0;
}
repeat(i,0,n)if(!vis[i]){
	int cnt=0; rec[cnt++]=i;
	for(int p=a[i];p!=i;p=a[p])
		rec[cnt++]=p,vis[p]=1;
	repeat(J,0,cnt)
		c[1ll*J*k%cnt]=rec[J];
	repeat(J,0,cnt)
		ans[c[(J+1)%cnt]]=c[J];
}

多項式

拉格朗日插值

• 函式曲線通過n個點 \((x_i,y_i)\)，求 \(f(k)\)
• 拉格朗日插值：\(f(x)=\sum\limits_{i=1}^n[y_i\Pi_{j!=i}\dfrac{x-x_j}{x_i-x_j}]\)
• \(O(n^2)\)

ll solve(int n,int x0){
	ll ans=0; x0%=mod;
	repeat(i,0,n)x[i]%=mod,y[i]%=mod;
	repeat(i,0,n){
		int s1=y[i],s2=1;
		repeat(j,0,n)
		if(i!=j){
			s1=s1*(x0-x[j])%mod;
			s2=s2*(x[i]-x[j])%mod;
		}
		ans=(ans+s1*qpow(s2,mod-2)%mod+mod)%mod;
	}
	return ans;
}

ll solve(int n,int x0){ //(i,y[i]),i=1..n的優化
	ll ans=0,up=1; x0%=mod;
	if(x0>=1 && x0<=n)return y[x0];
	repeat(i,1,n+1)
		up=up*(x0-i)%mod;
	repeat(i,1,n+1){
		ans+=y[i]*up%mod*qpow((x0-i)*((n+i)%2?-1:1)*C.fac[i-1]%mod*C.fac[n-i]%mod,mod-2)%mod;
	}
	return ans%mod;
}

快速傅里葉變換+任意模數

• 求兩個多項式的卷積，\(O(n\log n)\)

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;

多項式的一些概念

---

• 生成函式：\(A(x)=a_0+a_1x+a_2x^2+...\)
• 組合物件：x
• 組合物件的大小：x的指數i
• 方案數：系數
• 有 \(1+x+x^2+...=\dfrac{1}{1-x}\)

---

• 指數生成函式：無序排列
• 有 \(1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+...=e^x\)

---

• 嚴重空缺

---

矩陣

矩陣乘法 矩陣快速冪

矩乘 \(O(n^3)\)，矩快 \(O(n^3\log b)\)

struct mat{
	static const int N=110;
	ll a[N][N];
	explicit mat(ll 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;
	}
	ll *operator[](int x){return a[x];}
	const ll *operator[](int x)const{return a[x];}
};
mat qpow(mat a,ll b){ //矩陣快速冪
	mat ans(1); //mat ans; repeat(i,0,n)ans[i][i]=1;
	while(b){
		if(b&1)ans=ans*a;
		a=a*a; b>>=1;
	}
	return ans;
}

矩陣高級操作

• 行列式、逆矩陣（luogu P3389 && luogu P4783）
• \(O(n^3)\)

int n,m;
#define T ll
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=qpow(k,mod-2);
		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])>eps){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])>eps)
				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;
	}
	//vector<T> &operator[](int x){return a[x];}
	//const vector<T> &operator[](int x)const{return a[x];}
}a;

• 任意模數行列式（HDOJ 2827）
• \(O(n^3\log C)\)

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;

異或方程組

• 編號從 \(0\) 開始，高斯消元部分 \(O(n^3)\)（luogu P2962）

bitset<N> a[N]; bool l[N];
int n,ans;
bool gauss(){ //回傳是否有唯一解
	bool flag=1;
	repeat(i,0,n){
		int t=-1;
		repeat(j,i,n)if(a[j][i]){t=j; break;}
		if(t==-1){flag=0; continue;}
		if(t!=i)swap(a[i],a[t]);
		repeat(j,0,n)
		if(i!=j && a[j][i])
			a[j]^=a[i];
	}
	return flag;
}
void dfs(int x=n-1,int num=0){
	if(num>ans)return;
	if(x==-1){ans=num; return;}
	if(a[x][x]){
		bool v=a[x][n];
		repeat(i,x+1,n)
		if(a[x][i])
			v^=l[i];
		dfs(x-1,num+v);
	}
	else{
		dfs(x-1,num);
		l[x]=1;
		dfs(x-1,num+1);
		l[x]=0;
	}
}
int solve(){ //回傳滿足方程組的sum(xi)最小值
	ans=inf; gauss(); dfs(n-1,0);
	return ans;
}

線性基

• 線性基是一系列線性無關的基向量組成的集合

異或線性基

• 結論：\(basis.exist(a^b)\) 等價于 \(a,b\) 在 \(basis\) 里消去關鍵位后相等（要求是最簡線性基，即第一個板子）
• 插入、查詢 \(O(\log M)\)

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

• 這個版本中求kth需要rebuild \(O(\log^2 n)\)

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;

實數線性基

• 編號從 \(0\) 開始，插入、查詢 \(O(n^2)\)

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(abs(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;

線性規劃 | 單純形法

• 宣告：還沒學會
• \(\left[\begin{array}{ccccccc} a & a & a & a & a & a & b \\ a & a & a & a & a & a & b \\ a & a & a & a & a & a & b \\ c & c & c & c & c & c & v \end{array}\right]\)
• 每行表示一個約束，\(\sum ax\le b\)，并且所有 \(x\ge 0\)，求 \(\sum cx\) 的最大值
• 對偶問題：每串列示一個約束，\(\sum ax\ge c\)，并且所有 \(x\ge 0\)，求 \(\sum bx\) 的最小值
• 先找 \(c[y]>0\) 的 \(y\)，再找 \(b[x]>0\) 且 \(\dfrac {b[x]}{a[x][y]}\) 最小的x（找不到 \(y\) 則 \(v\)，找不到 \(x\) 則 INF），用行變換將 \(a[x][y]\) 置 \(1\)，將其他 \(a[i][y]\) 和 \(c[y]\) 置 \(0\)
• 編號從 \(1\) 開始，\(O(n^3)\)，缺init

const int M=1010; const lf eps=1e-6;
int n,m;
lf a[N][M],b[N],c[M],v; //a[1..n][1..m],b[1..n],c[1..m]
void pivot(int x,int y){
	b[x]/=a[x][y];
	repeat(j,1,m+1)if(j!=y)
		a[x][j]/=a[x][y];
	a[x][y]=1/a[x][y];
	repeat(i,1,n+1)
	if(i!=x && abs(a[i][y])>eps){
		b[i]-=a[i][y]*b[x];
		repeat(j,1,m+1)if(j!=y)
			a[i][j]-=a[i][y]*a[x][j];
		a[i][y]=-a[i][y]*a[x][y];
	}
	v+=c[y]*b[x];
	repeat(j,1,m+1)if(j!=y)
		c[j]-=c[y]*a[x][j];
	c[y]=-c[y]*a[x][y];
}
lf simplex(){ //回傳INF表示無限制，否則回傳答案
	while(1){
		int x,y;
		for(y=1;y<=m;y++)if(c[y]>eps)break;
		if(y==m+1)return v;
		lf mn=INF;
		repeat(i,1,n+1)
		if(a[i][y]>eps && mn>b[i]/a[i][y])
			mn=b[i]/a[i][y],x=i;
		if(mn==INF)return INF; //unbounded
		pivot(x,y);
	}
}
void init(){v=0;}

矩陣的一些結論

---

• \(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]\)

---

• 線性遞推轉矩快
• \(f_{n+3}=af_{n+2}+bf_{n+1}+cf_{n}\\\Leftrightarrow\left[\begin{array}{c}a&b&c\\1&0&0\\0&1&0\end{array}\right]^n \left[\begin{array}{c}f_2\\f_1\\f_0\end{array}\right]=\left[\begin{array}{c}f_{n+2}\\f_{n+1}\\f_{n}\end{array}\right]\)

---

數學雜項

主定理

• 對于 \(T(n)=aT(\dfrac nb)+n^k\) （要估算 \(n^k\) 的 \(k\) 值）
• 若 \(\log_ba>k\)，則 \(T(n)=O(n^{\log_ba})\)
• 若 \(\log_ba=k\)，則 \(T(n)=O(n^k\log n)\)
• 若 \(\log_ba<k\)（有省略），則 \(T(n)=O(n^k)\)

質數表

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

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 高精度

• 加、減、乘、單精度取模、小于號和等于號（其他不等號用rel_ops命名空間）
• 如果涉及除法，那就完蛋，用java吧；如果不想打這么多行也用java吧（一定要讓隊友會寫java）

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();
	}
	explicit 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;
}
void operator*=(big &a,ll b){ //有時被卡常
	big ans;
	repeat(i,0,a.size())a[i]*=b;
	a.adjust();
}
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();
}

一些數學結論

約瑟夫問題

• 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(k\log n)\)

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奇偶性不同）

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

• 4個柱子的漢諾塔情況：令 \(k=\lfloor n+1-\sqrt{2n+1}+0.5\rfloor\)，讓前k小的盤子用4個柱子的方法移到2號柱，其他盤子用3個柱子的方法移到4號柱，最后再移一次前k小，最短步數 \(f(n)=2f(k)+2^{n-k}-1\)

Stern-Brocot樹 Farey序列

• 分數序列：在 \([\dfrac 0 1,\dfrac 1 0]\) 中不斷在 \(\dfrac a b\) 和 \(\dfrac c d\) 之間插入 \(\dfrac {a+c}{b+d}\)
• 性質：所有數都是既約分數、可遍歷所有既約分數、保持單調遞增
• Stern-Brocot樹：二叉樹，其第 \(k\) 行是分數序列第 \(k\) 次操作新加的數
• Farey序列：\(F_n\) 是所有分子分母 \(\le n\) 的既約分數按照分數序列順序排列后的序列
• \(F_n\) 的長度 \(=1+\sum\limits_{i=1}^n\varphi(i)\)

浮點與近似計算

數值積分 | 自適應辛普森法

• 求 \(\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 eps,lf ans){
	lf m=(l+r)/2;
	lf x=raw(l,m),y=raw(m,r);
	if(abs(x+y-ans)<=15*eps)
		return x+y-(x+y-ans)/15;
	return asr(l,m,eps/2,x)+asr(m,r,eps/2,y);
}
//呼叫方法：asr(l,r,eps,raw(l,r))

牛頓迭代法

• 求 \(f(x)\) 的零點：\(x_{n+1}=x_n-\dfrac{f(x)}{f'(x)}\)
• 檢驗 \(x_{n+1}=g(x_n)\) 多次迭代可以收斂于 \(x_0\) 的方法：看 \(|g'(x_0)|\le1\) 是否成立

lf newton(lf n){ //sqrt
	lf x=1;
	while(1){
		lf y=(x+n/x)/2;
		if(abs(x-y)<eps)return x;
		x=y;
	}
}

• java高精度的整數平方根

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 浮點與近似計算

• \(\lim\limits_{n\rightarrow\infty}\dfrac{錯排(n)}{n!}=\dfrac 1 e,e\approx 2.718281828459045235360287471352\)
• \(\lim\limits_{n\rightarrow\infty}(\sum\frac 1 n-\ln n)=\gamma\approx 0.577215664901532860606\)

others of 數學雜項

---

• 埃及分數Engel展開
• 待展開的數為 \(x\)，令 \(u_1=x, u_{i+1}=u_i\times\lceil\dfrac 1 {u_i}\rceil-1\)（到0為止）
• 令 \(a_i=\lceil\dfrac 1 {u_i}\rceil\)
• 則 \(x=\dfrac 1{a_1}+\dfrac 1{a_1a_2}+\dfrac 1{a_1a_2a_3}+...\)

---

• 三個水杯容量為 \(a,b,c\)（正整數），\(a=b+c\)，初始 \(a\) 裝滿水，則得到容積為 \(\dfrac a 2\) 的水需要倒 \(\dfrac a{\gcd(b,c)}-1\) 次水

---

• 蘭頓螞蟻（白色異或右轉，黑色異或左轉），約一萬步后出現周期為104步的無限重復（高速公路）

---

• 任意勾股數能由復數 \((a+bi)^2\space(a,b∈\Z)\) 得到

---

• 任意正整數 \(a\) 都存在正整數 \(b,c\) 使得 \(a<b<c\) 且 \(a^2,b^2,c^2\) 成等引數列：構造 \(b=5a,c=7a\)

---

• 拉格朗日四平方和定理：每個正整數都能表示為4個整數平方和
• 對于偶素數 \(2\) 有 \(2=1^2+1^2+0^2+0^2\)
• 對于奇素數 \(p\) 有 \(p=a^2+b^2+1^2+0^2\) （容斥可證）
• 對于所有合數 \(n\) 有 \(n=z_1^2+z_2^2+z_3^2+z_4^2=(x_1^2+x_2^2+x_3^2+x_4^2)\cdot(y_1^2+y_2^2+y_3^2+y_4^2)\)
• 其中 \(\begin{cases} z_1=x_1y_1+x_2y_2+x_3y_3+x_4y_4 \\ z_2=x_1y_2-x_2y_1-x_3y_4+x_4y_3 \\ z_3=x_1y_3-x_3y_1+x_2y_4-x_4y_2 \\ z_4=x_1y_4-x_4y_1-x_2y_3+x_3y_2\end{cases}\)

---

• 雅可比四平方和定理：設 \(a^2+b^2+c^2+d^2=n\) 的整數解個數為 \(S(n)\)，有 \(S(2^k m)=\begin{cases}8d(m) & if\ k=0\\24d(m) & if\ k>0\end{cases}(m\ is\ odd)\)，\(d(n)\) 為 n 的約數和

---

• 基姆拉爾森公式
• 已知年月日，回傳星期幾

int week(int y,int m,int d){
	if(m<=2)m+=12,y--;
	return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7+1;
}

---

標準陽歷與儒略日轉換

int DateToInt(int y, int m, int d){
	return
	1461 * (y + 4800 + (m - 14) / 12) / 4 +
	367 * (m - 2 - (m - 14) / 12 * 12) / 12 -
	3 * ((y + 4900 + (m - 14) / 12) / 100) / 4 +
	d - 32075;
}
void IntToDate(int jd, int &y, int &m, int &d){
	int x, n, i, j;
	x = jd + 68569;
	n = 4 * x / 146097;
	x -= (146097 * n + 3) / 4;
	i = (4000 * (x + 1)) / 1461001;
	x -= 1461 * i / 4 - 31;
	j = 80 * x / 2447;
	d = x - 2447 * j / 80;
	x = j / 11;
	m = j + 2 - 12 * x;
	y = 100 * (n - 49) + i + x;
}

---

求 sum(n/i)

int f(int n){
	int ans=0;
	int t=sqrt(n);
	repeat(i,1,t+1)ans+=n/i;
	return ans*2-t*t;
}

---

n 維超立方體有 \(2^{n-i}×C(n, i)\) 個 i 維元素

---

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79565.html

標籤：其他

上一篇：Redis list實作原理 - 雙向回圈鏈表

下一篇：字符流中第一個不重復的字符