有些地方写英语是因为懒得把输入法调回中文（
_
general
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using std::vector;
using std::sort;
template<class T> inline T max(const T x,const T y){ return x>y?x:y; }
template<class T> inline T min(const T x,const T y){ return x<y?x:y; }
inline void swap(int &x,int &y){ x^=y^=x^=y; }
int main()
{
return 0;
}
for modular counting problems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using std::vector;
using std::sort;
const int P=;
inline int pow(int a,int n){ int c=1; for(;n;n>>=1,a=(long long)a*a%P) if(n&1) c=(long long)c*a%P; return c; }
inline void mod(int &x){ (x>=P)&&(x-=P); }
template<class T> inline T max(const T x,const T y){ return x>y?x:y; }
template<class T> inline T min(const T x,const T y){ return x<y?x:y; }
inline void swap(int &x,int &y){ x^=y^=x^=y; }
int fac[100002],inv_fac[100002],inv_n[100002];
inline void init(int n)
{
fac[0]=inv_fac[0]=inv_n[1]=1;
for(int i=1;i<=n;i++) fac[i]=(long long)fac[i-1]*i%P;
inv_fac[n]=pow(fac[n],P-2);
for(int i=n-1;i>=1;i--) inv_fac[i]=(long long)inv_fac[i+1]*(i+1)%P;
for(int i=2;i<=n;i++) inv_n[i]=(long long)(P-P/i)*inv_n[P%i]%P;
}
inline int binom(int n,int k){ return (long long)fac[n]*inv_fac[k]%P*inv_fac[n-k]%P; }
int main()
{
return 0;
}
fac in 1e9
1
2
3
4
5
6
7
8
inline Z calc(int n)
{
static int t[102]={1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116};
const int K=1e7;
Z c=t[n/K];
for(int i=n/K+1;i<=n;i++) c*=i;
return c;
}
logger
1
2
#define log(...) (fprintf(stderr,"log at %s %d: ",__FUNCTION__,__LINE__),fprintf(stderr,__VA_ARGS__))
for cf Div.2 ABC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using std::vector;
using std::sort;
template<class T> inline T max(const T x,const T y){ return x>y?x:y; }
template<class T> inline T min(const T x,const T y){ return x<y?x:y; }
inline void swap(int &x,int &y){ x^=y^=x^=y; }
int n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
}
return 0;
}
01-Trie for Maximum Xor Sum
ACAM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N=200002;
int tr[N][26],fail[N],fa[N],sum[N];
int cnt;
inline int insert(int len,char *s)
{
int c,u=0;
for(int i=1;i<=len;i++)
{
c=s[i]-'a';
if(!tr[u][c]) tr[u][c]=++cnt,fa[tr[u][c]]=u;
u=tr[u][c];
}
return u;
}
struct Queue{ int head,tail,q[N]; inline void clear(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
inline void ACAM()
{
q.clear();
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
else tr[u][i]=tr[fail[u]][i];
}
}
Better Function Names for Builtin Binary Operators
1
2
3
4
5
6
7
#define popcnt(x) __builtin_popcount(x)
#define popcnt_ll(x) __builtin__popcountll(x)
#define lowbit_pos(x) __builtin_ffs(x)
#define lowbit_pos_ll(x) __builtin_ffsll(x)
#define lg(x) (31-__builtin_clz(x))//same as highbit
#define lg_ll(x) (63-__builtin_clzll(x))
BIT
1
2
3
4
const int N=2000020;
#define lowbit(x) ((x)&(-(x)))
struct BIT{ int c[N]; inline void add(int x,int v){ x+=5; for(;x<=N;x+=lowbit(x)) c[x]+=v; } inline int sum(int x){ x+=5; int ans=0; for(;x;x-=lowbit(x)) ans+=c[x]; return ans; } };
完整版(附带倍增)
1
2
3
4
5
6
7
8
9
10
11
12
const int N=2000020;
#define lowbit(x) ((x)&(-(x)))
struct BIT
{
int c[N];
inline void clear(int n=N){ memset(c,0,sizeof(int)*N); }
inline void add(int x,int v){ x+=5; for(;x<=N;x+=lowbit(x)) c[x]+=v; }
inline int sum(int x){ x+=5; int ans=0; for(;x;x-=lowbit(x)) ans+=c[x]; return ans; }
inline int lower_bound(int x){ int p=0,s=0; for(int k=21;k;k--) if(p+(1<<k)<N&&s+c[p+(1<<k)]<x) p+=(1<<k),s+=c[p]; return p+1; }
inline int upper_bound(int x){ int p=0,s=0; for(int k=21;k;k--) if(p+(1<<k)<N&&s+c[p+(1<<k)]<=x) p+=(1<<k),s+=c[p]; return p+1; }
};
Bitset
Boruvka
Chain intersection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Chain{ int u,v; };
inline int dep_max(int u,int v){ return dep[u]>dep[v]?u:v; }
#define swap(x,y) (x^=y^=x^=y)
inline Chain intersection(Chain c1,Chain c2)
{
if(!c1.u) return c2;
if(!c2.u) return c1;
int l[4]={lca(c1.u,c2.u),lca(c1.u,c2.v),lca(c1.v,c2.u),lca(c1.v,c2.v)};
for(int i=0;i<=2;i++) if(dep[l[i+1]]>dep[l[i]]) swap(l[i+1],l[i]);
for(int i=1;i<=2;i++) if(dep[l[i+1]]>dep[l[i]]) swap(l[i+1],l[i]);
if(l[0]==l[1]) return (lca(c1.u,c2.u)==l[0]||lca(c1.v,c2.v)==l[0])?(Chain){l[0],l[0]}:(Chain){0,0};
return {l[0],l[1]};
}
Cipolla
1
2
3
4
5
6
7
8
9
10
11
12
13
int w;
struct N{ int a,b; };
inline N operator * (const N &x,const N &y){ return {((long long)x.a*y.a+(long long)w*x.b%P*y.b)%P,((long long)x.a*y.b+(long long)x.b*y.a)%P}; }
inline int pow(N a,int n){ N c={1,0}; for(;n;n>>=1,a=a*a) if(n&1) c=c*a; return c; }
inline bool check(int x){ return pow({x,0},(P-1)>>1)==1; }
inline unsigned long long xor64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
inline int sqrt(int n)
{
if(!n) return 0;
int a=xor64()%P,ans; while(!a||check(((long long)a*a-n+P)%P)) a=xor64%P;
w=((long long)a*a-n+P)%P,ans=pow({a,1},(P+1)>>1); return min(ans,P-ans);
}
Closest Point Pair
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n,a[100002];
struct P{ int x,y; inline bool operator < (P b) const { return y<b.y; } }p[100002];
inline bool cmpx(P a,P b){ return a.x<b.x; }
multiset<P> s;
#define sq(x) ((long long)(x)*(x))
inline long long dist2(P a,P b){ return sq(a.x-b.x)+sq(a.y-b.y); }
inline int closest_pair_dist2(int n,P *p)
{
int d=0x3f3f3f3f;
sort(p+1,p+n+1,cmpx);
for(int i=1,j=0;i<=n;i++)
{
while(p[i].x-p[j+1].x>=sqrt(d)) j++,s.erase(s.find({j,a[j]}));
for(auto it=s.upper_bound({i,a[i]-sqrt(d)});it!=s.end()&&it->y<a[i]+sqrt(d);it++)
d=min(d,dist2(p[i],*it));
s.insert(p[i]);
}
return d;
}
我本机是sublime text4，这个代码块用c的话markdown extended渲染这个是正常的，但是用cpp则会炸掉整个渲染。
Computional Geometry Basic
Cost Flow
Successive Shortest Path(Maximum Cost Maximum Flow)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N=502,M=100002;
int s,t,cnt,n;
struct Edge{ int v,w,f,next; }e[2*M];
int h[N],ecnt=1;
inline void add_edge(int u,int v,int w,int f){ e[++ecnt]={v,w,f,h[u]},h[u]=ecnt;e[++ecnt]={u,-w,0,h[v]},h[v]=ecnt; }
struct Queue{ int head,tail,q[500002]; inline void clear(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
long long dis[N];
bool inque[N];
int pre[N];
inline bool spfa(int s,int t)
{
memset(pre,0,sizeof(pre)),memset(dis,0x3f,sizeof(dis));
q.clear();
dis[s]=0,inque[s]=1,q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].next)
if(e[i].f&&dis[u]+e[i].w>dis[e[i].v]) dis[e[i].v]=dis[u]+e[i].w,pre[e[i].v]=i^1,(inque[e[i].v]?(void)0:q.push(e[i].v));
inque[u]=0;
}
return dis[t]!=0x3f3f3f3f3f3f3f3fll;
}
inline long long add_flow(int s,int t,long long &ans)
{
int f=0x3f3f3f3f;
for(int u=t;u!=s;u=e[pre[u]].v) f=min(f,e[pre[u]^1].f);
for(int u=t;u!=s;u=e[pre[u]].v) e[pre[u]].f+=f,e[pre[u]^1].f-=f;
return ans+=dis[t]*f,f;
}
inline long long ssp(int s,int t,long long &ans){ ans=0; long long sum=0; while(spfa(s,t,ans)) sum+=add_flow(s,t,ans); return sum; }
Capacity Scaling
Cost Scaling
Network Simplex
D&C on Tree
Deque
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Deque
{
int q[10002],head,tail;
Deque(){ head=5001,tail=5000; }
inline void push_front(int x){ q[--head]=x; }
inline void pop_front(){ head++; }
inline void push_back(int x){ q[++tail]=x; }
inline void pop_back(){ tail--; }
inline int front(){ return q[head]; }
inline int back(){ return q[tail]; }
inline bool empty(){ return head>tail; }
}q;
DFA Minimization
for xix open cup, gp of gomel J. Ten Ranges.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
inline void dfa_minimize()
{
static vector<vector<int> > S,T,TT,v;
vector<int> t;
for(int i=1;i<=acnt;i++) t.push_back(i),belong[i]=0;
for(int i=0;i<=acnt;i++) v.push_back(vector<int>());
belong[0]=1;
S.push_back(t),S.push_back(vector<int>{0});
for(int time=0;;time++)
{
//printf("begin %d, %d\n",time,S.size());
T=S;
for(int i=0;i<S.size();i++)
for(int u:S[i]) belong[u]=i;
for(int c=0;c<10;c++)
{
TT.clear();
for(vector<int> &now:T)
{
for(int u:now) v[belong[trans[u][c]]].push_back(u);
for(int u:now) if(v[belong[trans[u][c]]].size()) TT.push_back(vector<int>()),TT[TT.size()-1].swap(v[belong[trans[u][c]]]);
}
T.swap(TT);
}
if(T==S) break;
S=T;
}
static int new_trans[150000][10];
for(int i=0;i<S.size();i++)
for(int u=S[i][0],c=0;c<10;c++)
new_trans[i][c]=belong[trans[u][c]];
memcpy(trans,new_trans,sizeof(trans));
}
Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Edge{ int v,w,next; }e[1000002];
int ecnt,h[300002];
inline void add_edge(int u,int v,int w){ e[++ecnt]={v,w,h[u]},h[u]=ecnt; }
long long dis[300002];
bool vis[300002];
struct DijRadixHeap
{
#define highbit(x) ((x)?64-__builtin_clzll(x):0)
vector<int> b[60],temp[60];
int cur,c[60],c0p;
int p[300002];
inline void build(int n,int s)
{
cur=s;
for(int i=0;i<=50;i++) temp[i].reserve(10000),b[i].reserve(10000);
for(int i=1;i<=n;i++) c[highbit(dis[i]^dis[s])]++,b[highbit(dis[i]^dis[s])].push_back(i),p[i]=b[highbit(dis[i]^dis[s])].size()-1;
}
inline int top(){ return cur; }
inline void pop()
{
static int _c[60];
int last=cur;c[0]--,p[cur]=-1,cur=0;
if(c[0]){ while(p[b[0][c0p]]==-1) c0p++; cur=b[0][c0p]; return; }
for(int i=1;i<=50;i++) if(c[i])
{
for(int j=0;j<b[i].size();j++)
if(highbit(dis[b[i][j]]^dis[last])==i&&p[b[i][j]]==j&&dis[b[i][j]]<dis[cur]) cur=b[i][j];
for(int j=0;j<=i;j++) c[j]=0;
for(int j=0;j<=i;j++) temp[j].reserve(c[j]),temp[j].resize(0);
for(int j=0,t;j<=i;j++)
for(int k=0;k<b[j].size();k++)
if(highbit(dis[b[j][k]]^dis[last])==j&&p[b[j][k]]==k)
t=highbit(dis[b[j][k]]^dis[cur]),temp[t].push_back(b[j][k]),c[t]++,p[b[j][k]]=temp[t].size()-1;
for(int j=0;j<=i;j++) swap(temp[j],b[j]);
c0p=0;
break;
}
}
inline void decrease(int u,long long new_d){ c[highbit(dis[u]^dis[cur])]--,c[highbit(new_d^dis[cur])]++,b[highbit(new_d^dis[cur])].push_back(u),p[u]=b[highbit(new_d^dis[cur])].size()-1; }
}q;
inline void dij(int s)
{
dis[0]=3e14;
for(int i=1;i<=n;i++) dis[i]=3e14-1e9;
dis[s]=0,q.build(n,s);
for(int T=1;T<=n;T++)
{
int u=q.top();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];i;i=e[i].next)
if(dis[u]+e[i].w<dis[e[i].v]) q.decrease(e[i].v,dis[u]+e[i].w),dis[e[i].v]=dis[u]+e[i].w;
q.pop();
}
}
01bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Deque
{
int q[800008],head,tail;
inline void clear(){ head=400002,tail=400001; }
inline void push_front(int x){ q[--head]=x; }
inline void pop_front(){ head++; }
inline void push_back(int x){ q[++tail]=x; }
inline void pop_back(){ tail--; }
inline int front(){ return q[head]; }
inline int back(){ return q[tail]; }
inline bool empty(){ return head>tail; }
}q;
int dis[400004],last[400004];
inline void bfs(int s,int t)
{
q.clear(),q.push_back(s);
memset(dis,0x3f,sizeof(dis)),memset(last,0,sizeof(last));
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop_front();
for(E p:e[u])
if(dis[p.v]>dis[u]+p.w) dis[p.v]=dis[u]+p.w,last[p.v]=u,p.w?q.push_back(p.v):q.push_front(p.v);
}
}
Dinic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct Edge{ int v,f,next; }e[5000002];
int ecnt=1,h[500002],cur[500002];
inline void add_edge(int u,int v,int f){ e[++ecnt]={v,f,h[u]},h[u]=ecnt;e[++ecnt]={u,0,h[v]},h[v]=ecnt; }
int dis[500002];
struct Queue{ int head,tail,q[500002]; inline void clear(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
inline bool bfs(int s,int t)
{
memset(dis,0x3f,sizeof(dis));
q.clear(),q.push(t),dis[t]=0;
while(!q.empty())
{
int u=q.front();q.pop();
cur[u]=h[u];
if(u==s) return 1;
for(int i=h[u];i;i=e[i].next)
if(e[i^1].f&&dis[e[i].v]==inf) dis[e[i].v]=dis[u]+1,q.push(e[i].v);
}
return 0;
}
int dfs(int u,int f,int t)
{
if(u==t) return f;
int sum=0,temp;
for(int i=cur[u];i&&f;i=e[i].next)
{
cur[u]=i;
if(e[i].f&&dis[e[i].v]==dis[u]-1)
temp=dfs(e[i].v,min(f,e[i].f),t),sum+=temp,f-=temp,e[i].f-=temp,e[i^1].f+=temp;
}
return sum;
}
inline int dinic(int s,int t){ int ans=0; while(bfs(s,t)) ans+=dfs(s,inf,t); return ans; }
Discretization
1
2
3
using std::lower_bound;
inline void discretize(int n,int m,int *a,int *t){ for(int i=1;i<=n;i++) a[i]=lower_bound(t+1,t+m+1,a[i])-t; }
Divcnt1
随机贺了一个xyix的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct V{ long long x,y; inline V operator + (const V &b) { return {x+b.x,y+b.y}; } };
inline bool in(long long n,V a){ return n<(__int128)a.x*a.y; }
inline bool steep(long long n,long long x,V a){ return (__int128)n*a.x<=(__int128)x*x*a.y; }
inline __int128 sumd(long long n)
{
if(n==0) return 0;
static V s[1000002];
V p,l,r;
int top=0;
long long cbr=cbrt(n),sqr=sqrt(n);
p.x=n/sqr,p.y=sqr+1;
__int128 ans=0;
s[++top]={1,0},s[++top]={1,1};
while(1)
{
l=s[top--];
while(in(n,{p.x+l.x,p.y-l.y})) ans+=(__int128)p.x*l.y+(__int128)(l.y+1)*(l.x-1)/2,p.x+=l.x,p.y-=l.y;
if(p.y<=cbr) break;
r=s[top];
while(!in(n,{p.x+r.x,p.y-r.y})) l=r,r=s[--top];
while(1)
{
V mid=l+r;
if(in(n,{p.x+mid.x,p.y-mid.y})) r=s[++top]=mid;
else if(steep(n,p.x+mid.x,r)) break;
else l=mid;
}
}
for(int i=1;i<p.y;i++) ans=ans+n/i;
return ans*2-sqr*sqr;
}
Dominator Tree
Euclid
类欧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
M euclid(long long p,long long q,long long r,long long n,M U,M R)
{
long long m=((__int128)p*n+r)/q-1;
return ~m?r=q-r-1,(pow(R,r/p))*U*euclid(q%p,p,r%p,m,R,pow(R,q/p)*U)*pow(R,n-((__int128)q*m+r)/p):pow(R,n);
}
//generate a string, used to check if your modify sequence is correct
inline string pow(string a,int n){ string c; while(n>0) c+=a,n--; return c; }
string seuclid(long long p,long long q,long long r,long long n,string U,string R)
{
long long m=((__int128)p*n+r)/q-1;
return ~m?r=q-r-1,(pow(R,r/p))+U+seuclid(q%p,p,r%p,m,R,pow(R,q/p)+U)+pow(R,n-((__int128)q*m+r)/p):pow(R,n);
}
ExCRT
without __int128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long exgcd(long long a,long long b,long long &x,long long &y){ if(!b){ x=1,y=0;return a; } long long g=exgcd(b,a%b,y,x); y=y-a/b*x; return g; }
inline void mod(long long &x,const long long &m){ (x>=m)&&(x-=m); }
inline long long mul(long long a,long long b,long long m){ long long c=0; a%=m,b%=m,mod(a+=m,m),mod(b+=m,m); for(;b;b>>=1,mod(a+=a,m)) if(b&1) mod(c+=a,m); return c; }
inline int excrt(long long a1,long long m1,long long a2,long long m2,long long &a,long long &m)//merge equations x=a1(mod m1), x=a2(mod m2), put the answer in x=a(mod m)
{
long long x1,x2,c=a2-a1;
long long g=exgcd(m1,m2,x1,x2);
if(c%g) return 1;
m=m1/g*m2;
x1=mul(x1,c/g,m);
mod(a=(a1+mul(m1,x1,m)),m);
return 0;
}
with __int128
1
2
3
4
5
6
7
8
9
10
11
12
13
long long exgcd(long long a,long long b,long long &x,long long &y){ if(!b){ x=1,y=0;return a; } long long g=exgcd(b,a%b,y,x); y=y-a/b*x; return g; }
inline void mod(long long &x,const long long &m){ (x>=m)&&(x-=m); }
inline int excrt(long long a1,long long m1,long long a2,long long m2,long long &a,long long &m)//merge equations x=a1(mod m1), x=a2(mod m2), put the answer in x=a(mod m)
{
long long x1,x2,c=a2-a1;
long long g=exgcd(m1,m2,x1,x2);
if(c%g) return 1;
m=m1/g*m2;
x1=(__int128)x1*(c/g)%m;
mod(a=a1+(__int128)m1*x1%m,m);
return 0;
}
Fast IO
partially form mrsrz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct istream{
static const int L=1<<20;
char buf[L],*s;
inline istream(){ s=buf+L; }
inline char get(){ if(s==buf+L) fread(s=buf,1,1<<20,stdin); return *s++; }
inline istream & operator >> (int &rhs)
{
rhs=0;
char c=get();
for(;!isdigit(c);) c=get();
for(;isdigit(c);) rhs=(rhs<<3)+(rhs<<1)+(c^'0'),c=get();
return *this;
}
inline istream & operator >> (long long &rhs)
{
rhs=0;
char c=get();
for(;!isdigit(c);) c=get();
for(;isdigit(c);) rhs=(rhs<<3)+(rhs<<1)+(c^'0'),c=get();
return *this;
}
}cin;
struct ostream{
char buf[1<<24],*s;
inline ostream(){ s=buf; }
inline ostream& operator << (int rhs)
{
if(rhs<0) *s++='-',rhs=-rhs;
if(rhs==0) return *s++='0',*this;
static int w;
for(w=1;w<=rhs;w*=10);
for(w/=10;w;w/=10)*s++=(rhs/w)^'0',rhs%=w;
return *this;
}
inline ostream& operator << (const char&rhs){ *s++=rhs;return*this; }
inline ~ostream(){ freopen(".out","w",stdout),fwrite(buf,1,s-buf,stdout); }
}cout;
FFT
FMT
subset prefix sum/delta
1
2
3
4
5
6
7
8
9
10
11
inline void fmt(int n,int *A,int type)
{
for(int l=2;l<=(1<<n);l<<=1)
{
int mid=l>>1;
for(int p=0;p<(1<<n);p+=l)
for(int i=0;i<mid;i++)
A[p+mid+i]=A[p+mid+i]+type*A[p+i];//+ can be replaced by the operator you want
}
}
subset suffix sum/delta
1
2
3
4
5
6
7
8
9
10
11
inline void fmt(int n,int *A,int type)
{
for(int l=2;l<=(1<<n);l<<=1)
{
int mid=l>>1;
for(int p=0;p<(1<<n);p+=l)
for(int i=0;i<mid;i++)
A[p+i]=A[p+i]+type*A[p+mid+i];//+ can be replaced by the operator you want
}
}
for maximum and/or sum
for minimum and/or sum
Gauss-Jordan Elimination
liner equations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N=502;
const double eps=1e-4;//maybe you should change this
inline double abs(double x){ return x<0?-x:x; }
inline void swap(double &x,double &y){ double t=x;x=y;y=t; }
inline void swap(bool &x,bool &y){ x^=y^=x^=y; }
inline int Gauss(int n,double a[N][N])//0: exactly one solution, 1: infinity solutions, 2: no solution; the solution is {x_i=a[i][0]/a[i][i]} for i=1 to n
{
static bool used[N];
memset(used,0,sizeof(bool)*(n+2));
for(int k=1;k<=n;k++)
{
int p=0;
for(int i=1;i<=n;i++) if(!used[i]&&abs(a[i][k])>eps&&(!p||a[i][k]>a[p][k])) p=i;
if(!p) continue;
used[p]=1;
double coe=1/a[p][k];
swap(used[p],used[k]);
for(int i=0;i<=n;i++) a[p][i]*=coe,swap(a[p][i],a[k][i]);
for(int i=1;i<=n;i++)
{
if(i==k||abs(a[i][k])<eps) continue;
coe=1/a[i][k];
for(int j=0;j<=n;j++) a[i][j]=a[i][j]*coe-a[k][j];
}
}
bool flag=0;
for(int i=1;i<=n;i++) if(abs(a[i][i])<eps){ flag=1; if(abs(a[i][0])>eps) return 2; }
return flag;
}
matrix inversion(modulo composition)
1
2
determinant(modulo prime)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int P=;
inline int pow(int a,int n){ int c=1; for(;n;n>>=1,a=(long long)a*a%P) if(n&1) c=(long long)c*a%P; return c; }
const int N=502;
inline void swap(int &x,int &y){ x^=y^=x^=y; }
inline int det(int n,int a[N][N])//0: exactly one solution, 1: infinity solutions, 2: no solution; the solution is {x_i=a[i][0]/a[i][i]} for i=1 to n
{
int ans=1;
for(int k=1;k<=n;k++)
{
int p=0;
for(int i=1;i<=n;i++) if(a[i][k]){ p=i;break; }
if(!p) return 0;
ans=(long long)ans*a[p][k]%P;
int coe=pow(a[p][k],P-2);
for(int i=0;i<=n;i++) a[p][i]=(long long)a[p][i]*coe%P,swap(a[p][i],a[k][i]);
for(int i=1;i<=n;i++)
{
if(i==k||!a[i][k]) continue;
coe=pow(a[i][k],P-2);
for(int j=0;j<=n;j++) a[i][j]=((long long)a[i][j]*coe-a[k][j]+P)%P;
}
}
return ans;
}
determinant(modulo composite)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N=602;
inline int det(int n,int a[N][N])
{
int ans=1;
for(int k=1;k<=n&&ans;ans=(long long)ans*a[k][k]%P,k++)
for(int i=k+1;i<=n;i++)
{
int x=k,y=i,coe,cnt=0;
while(a[y][k]){ coe=a[x][k]/a[y][k]; for(int j=1;j<=n;j++) a[x][j]=(a[x][j]+(long long)(P-coe)*a[y][j])%P; swap(x,y); }//a[i][j]<P must be held
if(!a[k][k]){ ans=P-ans; for(int j=1;j<=n;j++) swap(a[x][j],a[y][j]); }
}
return ans;
}
Generator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<algorithm>
using std::string;
using std::to_string;
inline unsigned long long randi64(){ static unsigned long long x=ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
const int _tc=,_ex_tc=;
int main()
{
string name="";
for(int t=1;t<=_tc+_ex_tc;t++)
{
string in,out;
if(t<=_tc) in=name+to_string(t)+".in",out=name+to_string(t)+".out";
else in="ex_"+name+to_string(t-_tc)+".in",out="ex_"+name+to_string(t-_tc)+".out";
freopen(in.c_str(),"w",stdout);
remake:
fclose(stdout);
if(system(("./std < "+in+" > "+out).c_str())) goto remake;
fprintf(stderr,"%d done!\n",t);
}
return 0;
}
Hash Table
simple
1
2
3
4
5
6
7
8
9
10
11
#include<unordered_map>
struct Hash
{
static inline unsigned long long xorshift64(unsigned long long x){ return x += 0x0123456789abcdef,x^=(x<<13),x^=(x>>7),x^=(x<<17); }
inline size_t operator () (unsigned long long x) const
{
static const uint64_t t=std::random_device{}();
return xorshift64(x+t);
}
};
using umap=std::unordered_map<unsigned long long,int,Hash>;
or
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct Hash
{
const unsigned long long salt=std::random_device{}();
static unsigned long long hash(unsigned long long x)
{
x+=0x9e3779b97f4a7c15;
x=(x^(x>>30))*0xbf58476d1ce4e5b9;
x=(x^(x>>27))*0x94d049bb133111eb;
return x^(x>>31);
}
unsigned long long operator () (unsigned long long x) const { return hash(x)^salt; }
};
using umap=gp_hash_table<unsigned long long,int,Hash>;
static
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct HashTable//map int to T
{
#define T int//int can be replaced by the class you want
#define T_0 0//0 can be replaced by the zero item of T
inline unsigned long long xor64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
inline int abs(int x){ return x<0?-x:x; }
static const int M=1000003;//good primes: 1009, 10007, 100003, 1000003, 10000019
int a[M];bool used[M];
T b[M];
int m,c1,c2,c3,c4;
inline HashTable(){ c1=xor64()%(M-1)+1,c2=xor64()%(M-1)+1,c3=xor64()%(M-1)+1,c4=xor64()%(M-1)+1; }
inline int hash(const int &x,const int &t){ return ((long long)c1*x+c2+t*(((long long)c3*x%m+c4)%(m-1)+1))%m; }
//insert: negtive integer means key exists, and its abs is the position; find: -1 means key doesn't exist; erase: 0 means successful erased, -1 means key doesn't exist
inline int insert(int x,T y){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y; return p; }
inline int find(int x){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return p; return -1; }
inline int erase(int p){ return find(p)==-1?-1:used[find(p)]=0; }
inline int& operator [] (int x){ return b[abs(insert(x,T_0))]; }
#undef T
#undef T_0
}h;
dynamic(i think it is hard to use :( )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct HashTable//map int to T
{
#define T int//int can be replaced by the class you want
#define T_0 0//0 can be replaced by the zero item of T
inline void swap(int *&x,int *&y){ int *t=x;x=y;y=t; }
inline void swap(bool *&x,bool *&y){ bool *t=x;x=y;y=t; }
inline unsigned long long xor64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
inline bool is_prime(int x){ if(x==1) return 0; for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; }
inline int abs(int x){ return x<0?-x:x; }
//inline void swap(T *&x,T *&y){ T *t=x;x=y;y=t; }//if T is not int, this should be used
int *a;bool *used;
T *b;
int m,c1,c2,c3,c4;
int size;
inline HashTable(){ a=NULL,b=NULL,used=NULL; }
inline int hash(const int &x,const int &t){ return ((long long)c1*x+c2+t*(((long long)c3*x%m+c4)%(m-1)+1))%m; }
inline int _insert(int x,T y){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y; return p; }
inline void resize(int n){ int last=m;m=n+!(n&1); while(!is_prime(m)) m+=2; int *ta=new int[m];T *tb=new T[m];bool *tused=new bool[m]; memset(tused,0,sizeof(bool)*m);swap(ta,a),swap(tb,b),swap(tused,used); c1=xor64()%(m-1)+1,c2=xor64()%(m-1)+1,c3=xor64()%(m-1)+1,c4=xor64()%(m-1)+1; for(int i=0;i<last;i++) if(tused[i]) _insert(ta[i],tb[i]); if(ta!=NULL) delete []ta,delete []tb,delete []tused; }
//insert: negtive integer means key exists, and its abs is the position; find: -1 means key doesn't exist; erase: 0 means successful erased, -1 means key doesn't exist
inline int insert(int x,T y){ if((size+1)*2+1>m) resize((size*2+1)*2+1); int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y,size++; return p; }
inline int find(int x){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return p; return -1; }
inline int erase(int p){ return find(p)==-1?-1:used[find(p)]=0; }
inline int& operator [] (int x){ return b[abs(insert(x,T_0))]; }
#undef T
#undef T_0
}h;
Maybe in OI contests, I should use std::vector for hash tables.
Heaps
All heaps here are minimum heaps. Want maximum heap? Overload operator <.
Binary Heap: push, pop, top.
1
2
3
4
5
6
7
8
9
10
11
struct Heap
{
priority_queue<int> q1,q2;
inline void push(int x){ q1.push(x); }
inline void erase(int x){ q2.push(x); }
inline void reduce(){ while(q1.top()==q2.top()) q1.pop(),q2.pop();/*assert(q2.empty());*/ }
inline int top(){ return reduce(),q1.top(); }
inline void pop(){ erase(top()); }
inline bool empty(){ return reduce(),q1.empty(); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template<class T>
struct BinaryHeap
{
inline void swap(int &x,int &y){ x^=y^=x^=y; }
const int N=1000002;
T a[N];
int cnt=0;
#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)
#define fa(u) ((u)>>1)
Heap(){ cnt=0; }
inline T top(){ return a[1]; }
inline void up(int u){ for(;u>1&&a[u]<a[fa(u)];u=fa(u)) swap(a[fa(u)],a[u]); }
inline void down(int u){ for(;lq(u)<=cnt&&(a[lq(u)]<a[u]||(rq(u)<=cnt&&a[rq(u)]<a[u]));) (rq(u)<=cnt&&a[rq(u)]<a[lq(u)])?(swap(a[u],a[rq(u)]),u=rq(u)):(swap(a[u],a[lq(u)]),u=lq(u)); }
inline void push(T x){ a[++cnt]=x; up(cnt); }
inline void pop(){ swap(a[1],a[cnt]),cnt--; down(1); }
inline bool empty(){ return !cnt; }
#undef lq
#undef rq
#undef fa
};
template<class T>
struct EraseableBinaryHeap
{
BinaryHeap<T> h1,h2;
inline void push(T x){ h1.push(x); }
inline void erase(T x){ h2.push(x); }
inline T top(){ while(h1.top()==h2.top()) h1.pop(),h2.pop(); return h1.top(); }
inline void pop(){ top(),h1.pop(); }
inline bool empty(){ return top(),h1.empty(); }
};
Min-Max Heap: push, pop-min, pop-max, top-min, top-max.
Maybe in OI contests, I should use std::set.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template<class T>
struct MinMaxHeap
{
static const int N=2000002;
T a[N];
int cnt;
#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)
#define fa(u) ((u)>>1)
#define gfa(u) ((u)>>2)
MinMaxHeap(){ cnt=0; }
inline int min_pos(int u,int v){ return (v>cnt||a[u]<a[v])?u:v; }
inline int max_pos(int u,int v){ return (v>cnt||a[v]<a[u])?u:v; }
inline void swap(T &x,T &y){ T t=x;x=y;y=t; }
#define dep(u) (30-__builtin_clz(u))
inline void down_min(int u){ for(int t1,t2;lq(u)<=cnt;u=t2) t1=min_pos(lq(u),rq(u)),t2=min_pos(min_pos(lq(lq(u)),rq(lq(u))),min_pos(lq(rq(u)),rq(rq(u)))),t2<=cnt&&a[t2]<a[t1]?(a[t2]<a[u]?(swap(a[t2],a[u]),a[fa(t2)]<a[t2]?swap(a[t2],a[fa(t2)]):(void)0):(void)0):(a[t1]<a[u]?(swap(a[t1],a[u]),(void)(u=N)):(void)0); }
inline void down_max(int u){ for(int t1,t2;lq(u)<=cnt;u=t2) t1=max_pos(lq(u),rq(u)),t2=max_pos(max_pos(lq(lq(u)),rq(lq(u))),max_pos(lq(rq(u)),rq(rq(u)))),t2<=cnt&&a[t1]<a[t2]?(a[u]<a[t2]?(swap(a[t2],a[u]),a[t2]<a[fa(t2)]?swap(a[t2],a[fa(t2)]):(void)0):(void)0):(a[u]<a[t1]?(swap(a[t1],a[u]),(void)(u=N)):(void)0); }
inline void up_min(int u){ for(;gfa(u)&&a[u]<a[gfa(u)];u=gfa(u)) swap(a[u],a[gfa(u)]); }
inline void up_max(int u){ for(;gfa(u)&&a[gfa(u)]<a[u];u=gfa(u)) swap(a[u],a[gfa(u)]); }
inline void up(int u){ if(u==1) return; if(dep(u)&1) a[fa(u)]<a[u]?swap(a[fa(u)],a[u]),up_max(fa(u)):up_min(u); else a[u]<a[fa(u)]?swap(a[fa(u)],a[u]),up_min(fa(u)):up_max(u); }
inline int size(){ return cnt; }
inline bool empty(){ return !cnt; }
inline T top_min(){ return a[1]; }
inline T top_max(){ return cnt>=3?a[max_pos(2,3)]:(cnt>=2?a[2]:a[1]); }
inline int top_max_pos(){ return cnt>=3?max_pos(2,3):cnt>=2?2:1; }
inline void push(T x){ a[++cnt]=x,up(cnt); }
inline void pop_min(){ a[1]=a[cnt--],down_min(1); }
inline void pop_max(){ int p=top_max_pos(); a[p]=a[cnt--]; if(p<=cnt) down_max(p); }
#undef lq
#undef rq
#undef fa
#undef gfa
#undef dep
};
Skew Heap/Randomized Skew Heap: merge, push, erase(iterator), pop, top. Never used, maybe correct?
随机斜堆可以可持久化!但是这里的版本不行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template<class T>
struct SkewHeap
{
const int N=1000002;
struct Node{ T v;int lq,rq;bool del; Node(){ v=0x3f3f3f3f,lq=rq=0,del=0; } }t[N];
int ncnt;
inline int new_node(int _v=0x3f3f3f3f){ return t[++ncnt]={_v,0,0,0},ncnt; }
#define lq(u) t[u].lq
#define rq(u) t[u].rq
inline int merge(int u,int v)
{
if(!u||!v) return u|v;
if(t[u].v>t[v].v) swap(u,v);
return rq(u)=merge(rq(u),v),swap(lq(u),rq(u)),u;
}
inline int push(int rt,T v){ int p=new_node(v); return merge(rt,p),p; }
inline void erase(int u){ t[u].del=1; }
inline T top(int &rt){ while(t[rt].del) rt=merge(lq(rt),rq(rt)); return t[rt].v; }
inline void pop(int &rt){ top(rt),rt=merge(lq(rt),rq(rt)); }
#undef lq
#undef rq
};
//maybe you want an array to find roots of your heap?
template<class T>
struct RandomizedSkewHeap
{
const int N=1000002;
struct Node{ T v;int lq,rq;bool del; Node(){ v=0x3f3f3f3f,lq=rq=0,del=0; } }t[N];
int ncnt;
inline int new_node(int _v=0x3f3f3f3f){ return t[++ncnt]={_v,0,0,0},ncnt; }
#define lq(u) t[u].lq
#define rq(u) t[u].rq
inline int merge(int u,int v)
{
if(!u||!v) return u|v;
if(t[u].v>t[v].v) swap(u,v);
return rq(u)=merge(rq(u),v),((randi64()&1)?swap(lq(u),rq(u)):(void)0),u;
}
inline int push(int rt,T v){ int p=new_node(v); return merge(rt,p),p; }
inline void erase(int u){ t[u].del=1; }
inline T top(int &rt){ while(t[rt].del) rt=merge(lq(rt),rq(rt)); return t[rt].v; }
inline void pop(int &rt){ top(rt),rt=merge(lq(rt),rq(rt)); }
#undef lq
#undef rq
};
Leftist Tree(just some modify on function merge). Never used, maybe correct?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class T>
struct LeftistTree
{
const int N=1000002;
struct Node{ T v;int lq,rq,dis;bool del; Node(){ v=0x3f3f3f3f,lq=rq=0,dis=1,del=0; } }t[N];
int ncnt;
inline int new_node(int _v=0x3f3f3f3f){ return t[++ncnt]={_v,0,0,1,0},ncnt; }
#define lq(u) t[u].lq
#define rq(u) t[u].rq
inline int merge(int u,int v)
{
if(!u||!v) return u|v;
if(t[u].v>t[v].v) swap(u,v);
rq(u)=merge(rq(u),v);
if(t[lq(u)].dis<t[rq(u)].dis) swap(lq(u),rq(u));
return t[u].dis=t[rq(u)].dis+1,u;
}
inline int push(int rt,T v){ int p=new_node(v); return merge(rt,p),p; }
inline void erase(int u){ t[u].del=1; }
inline T top(int &rt){ while(t[rt].del) rt=merge(lq(rt),rq(rt)); return t[rt].v; }
inline void pop(int &rt){ top(rt),rt=merge(lq(rt),rq(rt)); }
#undef lq
#undef rq
};
//maybe you want an array to find roots of your heap?
Input&Output
Input/Outopt for __int128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void read(__int128 &x)
{
x=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+(c-'0'),c=getchar();
}
inline void write(__int128 x)
{
static char s[40];
int i=0;
for(;x;i++,x/=10) s[i]=x%10+'0';
for(int t=0;t<i;t++) putchar(s[i]);
}
Inv(Number Theory) in Liner Time
1
2
3
4
5
6
7
8
9
10
11
12
const int N=1000002;
inline void inv(int n,int *a,int *inv_a)
{
static int pre[N],suf[N];
pre[0]=suf[n+1]=1;
for(int i=1;i<=n;i++) pre[i]=(long long)pre[i-1]*a[i]%P;
for(int i=n;i;i--) suf[i]=(long long)suf[i+1]*a[i]%P;
int t=pow(pre[n],P-2);
for(int i=1;i<=n;i++) inv_a[i]=(long long)t*pre[i-1]%P*suf[i+1]%P;
}
K-d Tree
2-dt for static 2d range sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline int max(const int x,const int y){ return x>y?x:y; }
inline int min(const int x,const int y){ return x<y?x:y; }
struct Point{ int x,y,val; }p[500002];
inline bool cmpx(Point x,Point y){ return x.x<y.x; }
inline bool cmpy(Point x,Point y){ return x.y<y.y; }
struct Node{ int xl,xr,yl,yr,sum; }t[1000002];
#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)
inline void push_up(int u){ t[u].sum=t[lq(u)].sum+t[rq(u)].sum; }
void build(int l,int r,int u,bool d)
{
if(l==r){ t[u].xl=t[u].xr=p[l].x,t[u].yl=t[u].yr=p[l].y,t[u].sum=p[l].val;return; }
int mid=l+r>>1;
nth_element(p+l,p+mid,p+r+1,d?cmpx:cmpy);
build(l,mid,lq(u),!d),build(mid+1,r,rq(u),!d);
t[u].xl=min(t[lq(u)].xl,t[rq(u)].xl);
t[u].yl=min(t[lq(u)].yl,t[rq(u)].yl);
t[u].xr=max(t[lq(u)].xr,t[rq(u)].xr);
t[u].yr=max(t[lq(u)].yr,t[rq(u)].yr);
push_up(u);
}
int query(const int xl,const int xr,const int yl,const int yr,int u)
{
if(xr<t[u].xl||t[u].xr<xl||yr<t[u].yl||t[u].yr<yl) return 0;
if(xl<=t[u].xl&&t[u].xr<=xr&&yl<=t[u].yl&&t[u].yr<=yr) return t[u].sum;
return query(xl,xr,yl,yr,lq(u))+query(xl,xr,yl,yr,rq(u));
}
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void kmp(int n,char *s,int *fail)
{
for(int i=2,j=0;i<=n;i++)
{
while(j&&s[i]!=s[j+1]) j=fail[j];
if(s[i]==s[j+1]) j++;
fail[i]=j;
}
}
inline void match(int n,int m,char *t,char *s,int *fail,int *ans)//find t in s
{
for(int i=1,j=0;i<=n;i++)
{
while(j&&t[i]!=s[j+1]) j=fail[j];
if(t[i]==s[j+1]) j++;
ans[i]=j;
}
}
Kosaraju
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N=10002,M=100002;
struct Edge{ int v,next; bool type; }e[M<<1];
int ecnt,h[N];
inline void add_edge(int u,int v){ e[++ecnt]={v,h[u],1},h[u]=ecnt;e[++ecnt]={u,h[v],0},h[v]=ecnt; }
int dfa[N],dcnt,c[N],ccnt;//dfa: dfs array, c: SCC which the node belongs to
bool vis[N];
vector<int> v[N];//nodes of each SCC
void dfs1(int u){ vis[u]=1; for(int i=h[u];i;i=e[i].next) if(e[i].type&&!vis[e[i].v]) dfs1(e[i].v); dfa[++dcnt]=u; }
void dfs2(int u,int _c){ c[u]=_c,v[_c].push_back(u); for(int i=h[u];i;i=e[i].next) if(!e[i].type&&!c[e[i].v]) dfs2(e[i].v,_c); }
inline void kosaraju(int n)
{
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
for(int i=n;i>=1;i--) if(!c[dfa[i]]) dfs2(dfa[i],++ccnt);
}
Kruskal
If you want to do something on the MST, try Kruskal Reconstruction Tree or just add a add_edge() to this code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=100002,M=1000002;
struct Tuple{ int u,v,w; }t[M];
int tcnt;
inline void add_tuple(int u,int v,int w){ t[++tcnt]={u,v,w}; }
inline bool cmp(const Tuple &x,const Tuple &y){ return x.w>y.w; }
int f[N];
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int x,int y){ f[find(x)]=find(y); }
inline void init(){ for(int i=1;i<=(n<<1)-1;i++) f[i]=i; }
inline long long kru(int n,int m,Tuple *t)//get weight sum of the mst
{
init();
sort(t+1,t+tcnt+1,cmp);
long long ans=0;
for(int i=1,cnt=0;i<=m&&cnt<n;i++)
if(find(t[i].u)!=find(t[i].v)) merge(t[i].u,t[i].v),ans+=t[i].w;
return ans;
}
Kruskal Reconstruction Tree
Maybe you should put this in a namespace named Kru.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N=100002,M=1000002;
struct Tuple{ int u,v,w; }t[M];
int tcnt;
inline void add_tuple(int u,int v,int w){ t[++tcnt]={u,v,w}; }
inline bool cmp(const Tuple &x,const Tuple &y){ return x.w>y.w; }
int f[N<<1];
int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int x,int y){ f[find(x)]=find(y); }
inline void init(){ for(int i=1;i<=(n<<1)-1;i++) f[i]=i; }
int lq[N<<1],rq[N<<1],w[N<<1];
inline void kru(int n,int m,Tuple *t)
{
init();
sort(t+1,t+tcnt+1,cmp);
for(int i=1,cnt=0;i<=m&&cnt<n;i++)
if(find(t[i].u)!=find(t[i].v))
{
cnt++;
int now=n+ncnt;
w[now]=t[i].w;
lq[now]=find(t[i].u),rq[now]=find(t[i].v);
fa[0][find(t[i].u)]=fa[0][find(t[i].v)]=now;
merge(t[i].u,now),merge(t[i].v,now);
}
}
Lagrange Interpolation
liner interpolation(input a poly with degree L-1 described by point value at 1,2,…,L and n, return the point value at n)
1
2
3
4
5
6
7
8
9
10
11
inline int calc(int L,int *a,int n)//get f(n), where f is a poly of length at most L
{
static int pre[1000004],suf[1000004];
pre[0]=suf[L+1]=1;
for(int i=1;i<=L;i++) pre[i]=(long long)pre[i-1]*(n-i+P)%P;
for(int i=L;i>=1;i--) suf[i]=(long long)suf[i+1]*(n-i+P)%P;
int ans=0;
for(int i=1;i<=L;i++) ans=(ans+(long long)f[i]*pre[i-1]%P*suf[i+1]%P*inv_fac[i-1]%P*inv_fac[k+2-i]%P*((k+2-i)&1?P-1:1))%P;
return ans;
}
get the coefficients
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
inline void calc(int n,int *x,int *y,int *a)
{
static int b[N+1],tb[N+1];
memset(a,0,sizeof(int)*(n+1)),memset(b,0,sizeof(int)*(n+1));
b[0]=1;
for(int i=0;i<=n;i++)
for(int j=i;j>=0;j--) mod(b[j+1]+=b[j]),b[j]=(long long)b[j]*(P-x[i])%P;
for(int i=0;i<=n;i++)
{
int c=1;
for(int j=0;j<=n;j++) if(j!=i) c=(long long)c*(x[i]-x[j]+P)%P;
for(int j=n;j>=0;j--) tb[j]=(b[j]+(long long)tb[j+1]*(P-x[i]))%P,a[j]=(a[j]+(long long)y[i]*tb[j+1])%P;
}
}
inline void calc(int n,int *y,int *a)//x[i]=0,...,n
{
static int b[N+1],tb[N+1];
memset(a,0,sizeof(int)*(n+1)),memset(b,0,sizeof(int)*(n+1));
b[0]=1;
for(int i=0;i<=n;i++)
for(int j=i;j>=0;j--) mod(b[j+1]+=b[j]),b[j]=(long long)b[j]*(P-i)%P;
for(int i=0;i<=n;i++)
{
int c=1;
for(int j=0;j<=n;j++) if(j!=i) c=(long long)c*(i-j+P)%P;
for(int j=n;j>=0;j--) tb[j]=(b[j]+(long long)tb[j+1]*(P-i))%P,a[j]=(a[j]+(long long)y[i]*tb[j+1])%P;
}
}
LCA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int f[18][100002],id[100002],dep[100002],dcnt;
void predfs(int u,int fa)
{
f[0][++dcnt]=u,id[u]=dcnt;
dep[u]=dep[fa]+1;
for(int v:e[u]) if(v!=fa)
predfs(G.e[i].v,u),f[0][++dcnt]=u;
}
inline void st_init()
{
for(int k=1;k<=17;k++)
for(int i=1;i<=n-(1<<k)+1;i++)
f[k][i]=(dep[f[k-1][i]]<dep[f[k-1][i+(1<<(k-1))]]?f[k-1][i]:f[k-1][i+(1<<(k-1))]);
}
inline int lca(int u,int v)
{
u=id[u],v=id[v];
if(u>v) u^=v^=u^=v;
int l=31-__builtin_clz(v-u+1);
return dep[f[l][u]]<dep[f[l][v-(1<<l)+1]]?f[l][u]:f[l][v-(1<<l)+1];
}
LCT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int N=100002;
struct LCT
{
struct Node{ int q[2],fa,val,rev; }t[N];
#define q(u,x) t[u].q[x]
#define fa(u) t[u].fa
//push_up and push_down should be changed in different problems
inline void push_up(int u){ t[u].val=t[q(u,0)].val^t[q(u,1)].val^v[u]; }
inline void add_rev(int u){ swap(q(u,0),q(u,1)),t[u].rev^=1; }
inline void push_down(int u){ if(t[u].rev) add_rev(q(u,0)),add_rev(q(u,1)),t[u].rev=0; }
inline bool is_top(int u){ return q(fa(u),0)!=u&&q(fa(u),1)!=u; }
void push_downs(int u){ if(!is_top(u)) push_downs(fa(u));push_down(u); }
inline int get(int u){ return q(fa(u),1)==u; }
inline void rotate(int u)
{
int v=fa(u),w=fa(v),a=get(u),b=get(v);
if(!is_top(v)) q(w,b)=u;
fa(u)=w;
q(v,a)=q(u,!a),fa(q(u,!a))=v;
q(u,!a)=v,fa(v)=u;
push_up(v),push_up(u);
}
inline void splay(int u)
{
push_downs(u);
for(int v;!is_top(u);)
{
v=fa(u);
if(!is_top(v))
if(get(u)!=get(v)) rotate(u);
else rotate(v);
rotate(u);
}
}
inline int access(int u)
{
int v=0;
for(;u;v=u,u=fa(u)) splay(u),q(u,1)=v,push_up(u);
return v;
}
inline void make_root(int u){ access(u),splay(u),add_rev(u); }
inline int find_root(int u){ access(u),splay(u);while(q(u,0)) u=q(u,0);return splay(u),u; }
inline void split(int u,int v){ make_root(u),access(v),splay(v); }
inline void link(int u,int v){ make_root(u),fa(u)=v; }
inline void cut(int u,int v){ split(u,v);if(q(v,0)==u&&q(u,1)==0) q(v,0)=fa(u)=0; }
inline void change(int u,int val){ splay(u),v[u]=val,push_up(u); }//change node u's value
inline int query(int u,int v){ split(u,v);return t[v].val; }//chain query
};
Li-Chao Tree
minimum
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Function{ long long k,b; inline long long operator () (int x){ return k*x+b; } }null;
inline void swap(Function &x,Function &y){ Function t=x;x=y;y=t; }
inline long long min(long long x,long long y){ return x<y?x:y; }
const int N=1000002;
struct Node{ int l,r; Function f; }t[4*N];
#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)
inline void build(int l,int r,int u){ t[u].l=l,t[u].r=r,t[u].f=null; if(l==r) return; int mid=(l+r)>>1; build(l,mid,lq(u)),build(mid+1,r,rq(u)); }
void change(Function f,int u){ int mid=(t[u].l+t[u].r)>>1; if(f(mid)<t[u].f(mid)) swap(f,t[u].f); if(t[u].l==t[u].r) return; if(f(t[u].l)<t[u].f(t[u].l)) change(f,lq(u)); if(f(t[u].r)<t[u].f(t[u].r)) change(f,rq(u)); }
long long query(int x,int u){ if(!u) return 0x3f3f3f3f3f3f3f3f; if(t[u].l==t[u].r) return t[u].f(x); int mid=(t[u].l+t[u].r)>>1; return min(t[u].f(x),query(x,(x<=mid)?lq(u):rq(u))); }
for maximum, just change < to > and min to max, or overload operator <.
LIS
这段代码用于求最小非严格下降子序列划分，也就是最长严格上升子序列长度。
1
2
3
4
5
6
7
8
9
10
inline int lis(int n,int *a)
{
static int b[100002];
int cnt=0;
for(int i=1;i<=n;i++)
if(b[cnt]<a[i]) b[++cnt]=a[i];
else *lower_bound(b+1,b+cnt+1,a[i])=a[i];
return cnt;
}
List
1
2
#define List std::list
But std::list is hard to use, there is my code, never used, maybe correct?
1
2
3
4
5
6
7
8
9
10
11
struct List
{
struct Node{ T v; Node *pre,*nxt; };
Node *head,*tail;
List(){ head=tail=new Node(); tail->v=T_0,head->nxt=tail,tail->pre=head; }
inline Node* begin(){ return head; }
inline Node* end(){ return tail; }
inline Node* insert(T _v,Node *p){ Node* u=new Node(); u->v=_v,u->pre=p,u->nxt=p->nxt,p->nxt->pre=u,p->nxt=u; return u; }
inline void erase(Node *u){ u->pre->nxt=u->nxt,u->nxt->pre=u->pre; delete u; }
};
Lyndon Array/Runs Enumeration
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int n;
char s[1000002];
unsigned long long h[1000002],pow_B[1000002];
const unsigned long long B=283;
inline void init()
{
for(int i=1;i<=n;i++) h[i]=h[i-1]*B+s[i]-'a'+1;
pow_B[0]=1;
for(int i=1;i<=n;i++) pow_B[i]=pow_B[i-1]*B;
}
inline unsigned long long hash(int l,int r){ return h[r]-pow_B[r-l+1]*h[l-1]; }
inline int lcp(int i,int j)
{
int l=0,r=min(n-i+1,n-j+1),mid;
while(l<r)
if(mid=l+r+1>>1,hash(i,i+mid-1)==hash(j,j+mid-1)) l=mid;
else r=mid-1;
return l;
}
inline int lcs(int i,int j)
{
int l=0,r=min(i,j),mid;
while(l<r)
if(mid=l+r+1>>1,hash(i-mid+1,i)==hash(j-mid+1,j)) l=mid;
else r=mid-1;
return l;
}
inline bool less(int i,int j){ int p=lcp(i,j); return s[i+p]<s[j+p]; }
struct Run{ int l,r,p; inline bool operator < (Run b) const { return l==b.l?r==b.r?p<b.p:r<b.r:l<b.l; } }runs[2000002];
int rcnt;
inline void get_run(int l,int r){ int tl=l-lcs(l-1,r),tr=r+lcp(l,r+1); if(tr-tl+1>=2*(r-l+1)) runs[++rcnt]={tl,tr,r-l+1}; }
inline void la(bool p)//lyndon array
{
static int s[1000002];
int top=0;
s[0]=n+1;
for(int i=n;i>=1;i--)
{
while(top&&less(i,s[top])==p) --top;
get_run(i,s[top]-1),s[++top]=i;
}
}
inline void solve()
{
init(),la(0),la(1),std::sort(runs+1,runs+rcnt+1);
int rrcnt=0;
for(int i=1;i<=rcnt;i++) if(runs[i].l!=runs[i-1].l||runs[i].r!=runs[i-1].r) rrcnt++;
printf("%d\n",rrcnt);
for(int i=1;i<=rcnt;i++) if(runs[i].l!=runs[i-1].l||runs[i].r!=runs[i-1].r) printf("%d %d %d\n",runs[i].l,runs[i].r,runs[i].p);
}
Manacher
Matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
template<int N>
struct V
{
int a[N];
inline V(){ memset(a,0,sizeof(a)); }
inline int& operator [] (const int i){ return a[i]; }
inline V operator + (V &b)
{
V c;
for(int i=0;i<N;i++) mod(c[i]=a[i]+b[i]);
return c;
}
};
template<int N>
struct M
{
int a[N][N];
inline M(){ memset(a,0,sizeof(a)); }
inline int* operator [] (const int i){ return a[i]; }
inline M operator * (M &b)
{
M c;
for(int i=0;i<N;i++)
for(int k=0;k<N;k++)
for(int j=0;j<N;j++)
c[i][j]=(c[i][j]+(long long)a[i][k]*b[k][j])%P;
return c;
}
inline M operator + (M &b)
{
M c;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
mod(c[i][j]=a[i][j]+b[i][j]);
return c;
}
inline V operator * (V<N> &b)
{
V c;
for(int i=0;i<N;i++)
for(int k=0;k<N;k++)
c[i]=(c[i]+(long long)a[i][k]*b[k])%P;
return c;
}
};
扔掉无用位置，生成矩阵乘法的循环展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
bool flag[L][L],_c[L][L];
//in C=A*B: flag[i][j]=[c[i][j] is a const], _c[i][j] is the value
void test()
{
const int K=10,T=100;
static M t[K];
for(int i=0;i<K;i++)
for(int j=1;j<=T;j++) t[i]=t[i]*;//some matrix selected randomized
for(int i=0;i<L;i++)
for(int j=0;j<L;j++)
{
bool f=1;
for(int k=1;k<K;k++)
if(t[k][i][j]!=t[0][i][j]) f=0;
if(f) flag[i][j]=1,_c[i][j]=t[0][i][j];
}
}
void output()
{
for(int i=0;i<L;i++,printf("\n"))
for(int j=0;j<L;j++)
if(flag[i][j]) printf("%d ",_c[i][j]);
else printf("? ");
printf("\nstruct M{ int ");
for(int i=0;i<L;i++,printf("\n"))
for(int j=0;j<L;j++)
if(flag[i][j]) printf("i%dj%d,",i,j);
printf("empty; };\n\n");
for(int i=0;i<L;i++)
for(int j=0;j<L;j++) if(!flag[i][j])
{
printf("c.i%dj%d=",i,j);
for(int k=0;k<L;k++)
{
if((flag[i][k]&&!_c[i][k])||(flag[k][j]&&!_c[k][j])) continue;
k&&printf("+");
if(!flag[i][k]) printf("%d",_c[i][k]);
else printf("a.i%dj%d",i,k);
printf("*");
if(!flag[k][j]) printf("%d",_c[k][j]);
else printf("b.i%dj%d",k,j);
}
printf(";\n");
}
}
Matroid Intersection
这是带权的，如果不带权的话把spfa换成bfs就行了，没写过所以就不放了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
const int M=104;
int m;
bool I[M];//current ans
struct Matroid1
{
inline bool check(int x,int y)//check if I-x+y is independence
{
}
}M1;
struct Matroid2
{
inline bool check(int x,int y)
{
}
}M2;
vector<int> e[M];
int w[M],pre[M];
int dis[M],len[M];
struct Queue{ int head,tail,q[M*M]; inline void clear(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
bool inque[M];
inline void spfa(int s)
{
memset(pre,0,sizeof(pre)),memset(dis,0x3f,sizeof(dis)),memset(len,0,sizeof(len));
q.clear(),q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
inque[u]=0;
for(int v:e[u])
if(dis[u]+w[v]<dis[v]||(dis[u]+w[v]==dis[v]&&len[u]+1<len[v]))
dis[v]=dis[u]+w[v],len[v]=len[u]+1,pre[v]=u,inque[v]?0:(q.push(v),inque[v]=1);
}
}
inline bool argument(int &ans)
{
int s=m+1,t=m+2;
for(int i=1;i<=m+2;i++) e[i].clear();
for(int i=1;i<=m;i++) if(I[i])
for(int j=1;j<=m;j++) if(!I[j])
M1.check(i,j)?e[i].push_back(j):(void)0,M2.check(i,j)?e[j].push_back(i):(void)0;
for(int i=1;i<=m;i++) if(!I[i])
M1.check(0,i)?e[s].push_back(i):(void)0,M2.check(0,i)?e[i].push_back(t):(void)0;
for(int i=1;i<=m;i++) w[i]=(I[i]?a[i].w:-a[i].w);
spfa(s);
if(!pre[t]) return 0;
for(int u=pre[t];u!=s;u=pre[u]) I[u]^=1,ans+=w[u];
return 1;
}
Merge Sort
Miller-Rabin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline long long pow(long long a,long long n,long long m){ long long c=1; for(;n;n>>=1,a=(__int128)a*a%m) if(n&1) c=(__int128)c*a%m; return c; }
inline bool is_prime(long long n)
{
static const long long bases[7]={2,325,9375,28178,450775,9780504,1795265022};
if(!(n&1)||n<3) return n==2;
long long m=n-1;
int k=0;
while(!(m&1)) m>>=1,k++;
for(long long a:bases)
{
if(a%n==0) continue;
long long t=pow(a%n,m,n);
if(t==1) continue;
int i=1;
for(;i<=k;i++)
if(t==n-1) break;
else t=(__int128)t*t%n;
if(i==k+1) return 0;
}
return 1;
}
Min_25 Sieve
要用这个，需要先调用init预处理，然后用G算素数，然后用S算总和。
这是一个示例，求\(f=\mathrm{id}\)的前缀和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int P=1e9+7;
inline void mod(int &x){ (x>=P)&&(x-=P); }
int prime[100002],pcnt,h[100002];
bool b[100002];
int K;
long long N,a[200002];
int _g[200002],id1[100002],id2[100002],cnt;
#define id(x) ((x)<=K?id1[x]:id2[N/(x)])
#define g(x) ((_g[id(x)]+P)%P)
#define t(x) ((x)%P)
#define sum_t(x) ((long long)(x)%P*((x)%P+1)%P*inv_2%P)
#define f(x) ((x)%P)
inline void sieve(int n)
{
for(int i=2;i<=n;i++)
{
if(!b[i]) prime[++pcnt]=i,h[pcnt]=t(i);
for(int j=1;j<=pcnt&&i*prime[j]<=n;j++)
{
b[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
for(int i=1;i<=pcnt;i++) mod(h[i]+=h[i-1]);
}
inline void init(long long n)
{
sieve(K=(int)sqrt(n));
for(long long l=1,r;l<=n;l=r+1)
r=n/(n/l),
cnt++,a[cnt]=n/l,id(a[cnt])=cnt,_g[cnt]=(sum_t(a[cnt])-1+P)%P;
}
inline void G()
{
for(int i=1,k;i<=pcnt;i++)
for(int j=1;j<=cnt&&(long long)prime[i]*prime[i]<=a[j];j++)
k=id(a[j]/prime[i]),
_g[j]=(_g[j]-(long long)t1(prime[i])*(_g[k]-h[i-1]+P)%P+P)%P;
}
int S(long long n,int k)
{
if(prime[k]>=n) return 0;
int ans=(g(n)-h[k]+P)%P;
for(int i=k+1;i<=pcnt&&(long long)prime[i]*prime[i]<=n;i++)
for(long long c=prime[i],e=1;c<=n;e++,c=c*prime[i])
ans=(ans+f(c)*(S(n/c,i)+(e!=1))%P)%P;
return ans;
}
Minimal Circle Covering
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<algorithm>
#include<math.h>
#include<random>
using std::shuffle;
const double eps=1e-8;
struct P{ double x,y; }a[100002];
#define sq(x) ((x)*(x))
inline double dist2(P a,P b){ return sq(a.x-b.x)+sq(a.y-b.y); }
inline double det(double a,double b,double c,double d,double e,double f,double g,double h,double i){ return a*e*i-a*h*f-d*b*i+d*h*c+g*b*f-g*e*c; }
//a b c
//d e f
//g h i
inline P circum_center(P a,P b,P c)
{
double t=2*det(a.x,b.x,c.x,a.y,b.y,c.y,1,1,1);
return{det(sq(a.x)+sq(a.y),sq(b.x)+sq(b.y),sq(c.x)+sq(c.y),a.y,b.y,c.y,1,1,1)/t,-det(sq(a.x)+sq(a.y),sq(b.x)+sq(b.y),sq(c.x)+sq(c.y),a.x,b.x,c.x,1,1,1)/t};
}
struct C{ P o; double r2; };
inline C circum_circle(P a,P b,P c){ P t=circum_center(a,b,c); return {t,dist2(t,a)}; }
inline P mid(P a,P b){ return {(a.x+b.x)/2,(a.y+b.y)/2}; }
inline C solve(int n,P *a)
{
std::mt19937 _r(std::random_device{}());
shuffle(a+1,a+n+1,_r);
C c={ {0,0},0};
for(int i=1;i<=n;i++)
if(dist2(a[i],c.o)>c.r2+eps)
{
c={a[i],0};
for(int j=1;j<i;j++)
if(dist2(a[j],c.o)>c.r2+eps)
{
c={mid(a[i],a[j]),dist2(a[i],mid(a[i],a[j]))};
for(int k=1;k<j;k++)
if(dist2(a[k],c.o)>c.r2+eps)
c=circum_circle(a[i],a[j],a[k]);
}
}
return c;
}
Modular Integer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Z
{
int a;
Z(int _a=0):a(_a){}
Z operator + (Z r){ return Z(a+r.a>=P?a+r.a-P:a+r.a); }
Z operator - (Z r){ return Z(a-r.a<0?a-r.a+P:a-r.a); }
Z operator * (Z r){ return Z((long long)a*r.a%P); }
Z& operator += (Z r){ a+=r.a,(a>=P)&&(a-=P); return *this; }
Z& operator -= (Z r){ a-=r.a,(a<0)&&(a+=P); return *this; }
Z& operator *= (Z r){ a=(long long)a*r.a%P; return *this; }
inline Z pow(int n){ Z c=1,t=a; for(;n;n>>=1,t*=t) if(n&1) c*=t; return c; }
inline Z inv(){ return pow(P-2); }
};
Z operator + (int a,Z b){ return Z(a)+b; }
Z operator - (int a,Z b){ return Z(a)-b; }
Z operator * (int a,Z b){ return Z(a)*b; }
MT19937
1
std::mt19937 r(std::random_device{}());
NTT
我一看，为什么现在的法法塔不用rev了?
哦原来是什么转置原理。懂了。
1
2
3
4
5
6
7
8
9
10
11
const int P=998244353,g=3;
inline int pow(int a,int n){ int c=1; for(;n;n>>=1,a=(long long)a*a%P) if(n&1) c=(long long)c*a%P; return c; }
const int inv_g=pow(g,P-2);
inline void mod(int &x){ if(x>=P) x-=P; }
const int N=1<<21;
int W[N],inv_W[N];
struct PolyInit{ inline PolyInit(int n=N){ for(int i=1,c=1,Wn,inv_Wn;i<n;i<<=1,c++){ W[i]=inv_W[i]=1,Wn=pow(g,(P-1)>>c),inv_Wn=pow(inv_g,(P-1)>>c); for(int j=1;j<i;j++) W[i+j]=(long long)W[i+j-1]*Wn%P,inv_W[i+j]=(long long)inv_W[i+j-1]*inv_Wn%P; } } }_poly_init;
inline void dft(int n,int *A){ for(int l=n>>1,x,y;l;l>>=1) for(int p=0;p<n;p+=(l<<1)) for(int i=0;i<l;i++) x=A[p+i],y=A[p+l+i],mod(A[p+i]=x+y),A[p+l+i]=(long long)(x-y+P)*W[l+i]%P; }
inline void idft(int n,int *A){ for(int l=1,x,y;l<n;l<<=1) for(int p=0;p<n;p+=(l<<1)) for(int i=0;i<l;i++) x=A[p+i],y=(long long)inv_W[l+i]*A[p+l+i]%P,mod(A[p+i]=x+y),mod(A[p+l+i]=x-y+P); for(int i=0,inv_n=pow(n,P-2);i<n;i++) A[i]=(long long)A[i]*inv_n%P; }
PAM
Partition Numbers
EI在loj6268的提交。f就是分拆数。
1
2
3
4
5
6
7
f[0]=g[0]=1;
for(int i=1,t=i*i;t<=n;i++,t=i*i)
{
for(int j=i;j<=n;j++) mod(g[j]+=g[j-i]);
for(int j=i;j<=n;j++) mod(g[j]+=g[j-i]);
for(int j=t;j<=n;j++) mod(f[j]+=g[j-t]);
}
Poly
反正OI又用不到这个，不需要背，我就写能写出来的最快的了（
loj #150 挑战多项式，提交时rk21(直接飞了，为什么他们常数那么小)，现在好像直接飞到第三页，可能又有新的带项式加速trick了。dft/idft 1E(n)(废话), mul 6E(n), inv 10E(n), ln/div 13E(n), sqrt 11E(n), inv_sqrt 12E(n), exp 18E(n), pow 31E(n)。
inv是贺的，所以码风不太一样（
命名规范大概是，数组名前面加T表示是用于dft的，0表示来自上一轮迭代。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
const int N=262144;//N should be twice of your max poly length
const int P=998244353,g=3,inv_2=(P+1)/2;
inline void mod(int &x){ (x>=P)&&(x-=P); }
inline void mod2(int &x){ (x>=(P<<1))&&(x-=(P<<1)),(x>=P)&&(x-=P); }
inline void mod_(int &x){ (x<0)&&(x+=P); }
inline int pow(int a,int n){ int c=1; for(;n;n>>=1,a=(long long)a*a%P) if(n&1) c=(long long)c*a%P; return c; }
const int inv_g=pow(g,P-2);
namespace Cipolla//modular square root
{
int w;
struct N{ int a,b; };
inline N operator * (const N &x,const N &y){ return {((long long)x.a*y.a+(long long)w*x.b%P*y.b)%P,((long long)x.a*y.b+(long long)x.b*y.a)%P}; }
inline int pow(N a,int n){ N c={1,0}; for(;n;n>>=1,a=a*a) if(n&1) c=c*a; return c.a; }
inline bool check(int x){ return pow({x,0},(P-1)>>1)==1; }
inline unsigned long long xor64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
inline int sqrt(int n)
{
if(!n) return 0;
int a=xor64()%P,ans; while(!a||check(((long long)a*a-n+P)%P)) a=xor64()%P;
w=((long long)a*a-n+P)%P,ans=pow({a,1},(P+1)>>1); return min(ans,P-ans);
}
}
namespace Poly
{
//include dft/idft, deriv/integ, 6E(n) mul, 10E(n) inv, 13E(n) div/ln, 11E(n) sqrt, 12E(n) inv_sqrt 18E(n) exp, 31E(n) pow
//input and output array can be the same because I will copy input at first?
int fac[N],inv_i[N<<1];
int W[N<<1],inv_W[N<<1];
struct Init{
inline Init(int n=N<<1)
{
for(int i=1,c=1,Wn,inv_Wn;i<n;i<<=1,c++)
{
W[i]=inv_W[i]=1,Wn=pow(g,(P-1)>>c),inv_Wn=pow(inv_g,(P-1)>>c);
for(int j=1;j<i;j++)
W[i+j]=(long long)W[i+j-1]*Wn%P,inv_W[i+j]=(long long)inv_W[i+j-1]*inv_Wn%P;
}
inv_i[1]=1;
for(int i=2;i<n;i++) inv_i[i]=(long long)(P-P/i)*inv_i[P%i]%P;
}
}_poly_init;
//dif-dit fft
inline void dft(int n,int *A)
{
for(int l=n>>1,x,y;l;l>>=1)
for(int p=0;p<n;p+=(l<<1))
for(int i=0;i<l;i++)
x=A[p+i],y=A[p+l+i],mod(A[p+i]=x+y),A[p+l+i]=(long long)(x-y+P)*W[l+i]%P;
}//A[n] means F(w_{bitrev(n)})
inline void idft(int n,int *A)
{
for(int l=1,x,y;l<n;l<<=1)
for(int p=0;p<n;p+=(l<<1))
for(int i=0;i<l;i++)
x=A[p+i],y=(long long)inv_W[l+i]*A[p+l+i]%P,mod(A[p+i]=x+y),mod(A[p+l+i]=x-y+P);
for(int i=0,inv_n=inv_i[n];i<n;i++) A[i]=(long long)A[i]*inv_n%P;
}
inline void mul(int n,int *A,int *B,int *C){ static int T1[N],T2[N]; memcpy(T1,A,sizeof(int)*n),memcpy(T2,B,sizeof(int)*n),dft(n,T1),dft(n,T2); for(int i=0;i<n;i++) C[i]=(long long)T1[i]*T2[i]%P; idft(n,C); }
inline void inv(int n,int *_F,int *G)//10E(n), calc G=1/F
{
static int F[N],T[N],TG[N];
memcpy(F,_F,sizeof(int)*n);
memset(G,0,sizeof(int)*n),memset(TG,0,sizeof(int)*n),G[0]=pow(F[0],P-2);
for(int l=2,mid=1;l<=n;l<<=1,mid<<=1)
{
memcpy(T,F,sizeof(int)*l);
memcpy(TG,G,sizeof(int)*mid);
memset(G+mid,0,sizeof(int)*mid);
dft(l,G),dft(l,T);
for(int i=0;i<l;i++) T[i]=(long long)G[i]*T[i]%P;
idft(l,T);
memset(T,0,sizeof(int)*mid);
dft(l,T);
for(int i=0;i<l;i++) T[i]=(long long)G[i]*T[i]%P;
idft(l,T);
memcpy(G,TG,sizeof(int)*l);
for(int i=mid;i<l;i++) G[i]=T[i]?P-T[i]:0;
}
}
inline void deriv(int n,int *A){ for(int i=0;i<n;i++) A[i]=(long long)A[i+1]*(i+1)%P; A[n-1]=0; }
inline void integ(int n,int *A){ for(int i=n-1;i>0;i--) A[i]=(long long)A[i-1]*inv_i[i]%P; A[0]=0; }
inline void div(int n,int *_H,int *_F,int *Q)//13E(n), calc Q=H/F
{
static int F[N],H[N],G0[N],Q0[N],TG0[N],TH0[N],TF[N],TQ0[N],T[N];
memset(G0,0,sizeof(int)*n),memset(Q0,0,sizeof(int)*n),memset(TG0,0,sizeof(int)*n),memset(TH0,0,sizeof(int)*n),memset(TF,0,sizeof(int)*n),memset(TQ0,0,sizeof(int)*n),memset(T,0,sizeof(int)*n);
memcpy(F,_F,sizeof(int)*n),memcpy(H,_H,sizeof(int)*n);
if(n==1){ Q[0]=F[0]*pow(H[0],P-2); return; }
int mid=n>>1;
inv(mid,F,G0);
memcpy(TG0,G0,sizeof(int)*mid),memcpy(TH0,H,sizeof(int)*mid),dft(n,TG0),dft(n,TH0);
for(int i=0;i<n;i++) Q0[i]=(long long)TG0[i]*TH0[i]%P;
idft(n,Q0);
memset(Q0+mid,0,sizeof(int)*mid),memcpy(Q,Q0,sizeof(int)*mid);
memcpy(TF,F,sizeof(int)*n),memcpy(TQ0,Q0,sizeof(int)*mid),dft(n,TF),dft(n,TQ0);
for(int i=0;i<n;i++) T[i]=(long long)TF[i]*TQ0[i]%P;
idft(n,T),memset(T,0,sizeof(int)*mid);
for(int i=mid;i<n;i++) mod(T[i]+=P-H[i]);
dft(n,T);
for(int i=0;i<n;i++) T[i]=(long long)T[i]*TG0[i]%P;
idft(n,T);
for(int i=mid;i<n;i++) Q[i]=T[i]?P-T[i]:0;
}
inline void ln(int n,int *F,int *G){ static int T[N]; memcpy(T,F,sizeof(int)*n),deriv(n,T),div(n,T,F,G),integ(n,G); }
inline void half_dft(int n,int *TF,int *TF0)
{
static int rev_n[N],rev_2n[N];
for(int i=0;i<(n<<1);i++) rev_2n[i]=(rev_2n[i>>1]>>1)|((i&1)?n:0);
for(int i=0;i<n;i++) rev_n[i]=(rev_n[i>>1]>>1)|((i&1)?(n>>1):0);
for(int i=0;i<n;i++) TF0[rev_n[i]]=TF[rev_2n[i<<1]];
}
inline void exp(int n,int *_F,int *G)//18E(n)
{
static int F[N],T[N],H[N],H0[N],G0[N],TH0[N],TH[N],TG0[N],TG00[N],FP[N],TFP[N],GP0[N];
memset(T,0,sizeof(int)*n),memset(H,0,sizeof(int)*n),memset(H0,0,sizeof(int)*n),memset(G0,0,sizeof(int)*n),memset(TH0,0,sizeof(int)*n),memset(TH,0,sizeof(int)*n),memset(TG0,0,sizeof(int)*n),memset(TG00,0,sizeof(int)*n),memset(TFP,0,sizeof(int)*n),memset(GP0,0,sizeof(int)*n);
memcpy(F,_F,sizeof(int)*n),memcpy(FP,F,sizeof(int)*n),deriv(n,FP);
G[0]=1,H[0]=1;
if(n>1) G[1]=F[1],TG0[0]=1,dft(2,TG0);
for(int l=2,mid=1;l<n;l<<=1,mid<<=1)
{
memcpy(H0,H,sizeof(int)*mid),memcpy(G0,G,sizeof(int)*l);
memcpy(TH0,H0,sizeof(int)*mid),memset(TH0+mid,0,sizeof(int)*(mid+l)),dft(l<<1,TH0);
memcpy(TG0,G0,sizeof(int)*l),memset(TG0+l,0,sizeof(int)*l),dft(l<<1,TG0);
for(int i=0;i<(l<<1);i++) H[i]=(long long)TH0[i]*TH0[i]%P*TG0[i]%P;
idft(l<<1,H),memset(H+l,0,sizeof(int)*l);
for(int i=0;i<l;i++) mod_(H[i]=(H0[i]<<1)-H[i]),mod(H[i]);
memcpy(TFP,FP,sizeof(int)*(l-1)),dft(l,TFP);
half_dft(l,TG0,TG00);
for(int i=0;i<l;i++) T[i]=(long long)TG00[i]*TFP[i]%P;
idft(l,T);
memcpy(GP0,G0,sizeof(int)*l),deriv(l,GP0);
for(int i=0;i<(l<<1);i++) mod(T[i]=GP0[i]+P-T[i]);
memcpy(T+l,T,sizeof(int)*(l-1)),memset(T,0,sizeof(int)*(l-1));
memcpy(TH,H,sizeof(int)*l),memset(TH+l,0,sizeof(int)*l),dft(l<<1,TH);
dft(l<<1,T);
for(int i=0;i<(l<<1);i++) T[i]=(long long)T[i]*TH[i]%P;
idft(l<<1,T);
memcpy(T+(l<<1),T,sizeof(int)*(l-1)),memset(T,0,sizeof(int)*(l-1));
for(int i=0;i<l-1;i++) mod(T[i]+=FP[i]);
integ(l<<1,T);
for(int i=0;i<(l<<1);i++) mod(T[i]=F[i]+P-T[i]);
dft(l<<1,T);
for(int i=0;i<(l<<1);i++) T[i]=(long long)T[i]*TG0[i]%P;
idft(l<<1,T);
memcpy(T+(l<<1),T,sizeof(int)*l),memset(T,0,sizeof(int)*l);
for(int i=0;i<(l<<1);i++) mod(G[i]=G0[i]+T[i]);
}
}
inline void inv_sqrt(int n,int *_F,int *_H,int *_TF=NULL)//12E(n)
{
static int F[N],TF[N<<1],T[N<<1],H[N];
memcpy(F,_F,sizeof(int)*n);
H[0]=pow(Cipolla::sqrt(F[0]),P-2);
for(int l=1;l<n;l<<=1)
{
memcpy(TF,F,sizeof(int)*(l<<1)),memset(TF+(l<<1),0,sizeof(int)*(l<<1)),dft(l<<2,TF);
memcpy(T,H,sizeof(int)*l),memset(T+l,0,sizeof(int)*((l<<1)+l)),dft(l<<2,T);
for(int i=0;i<(l<<2);i++) T[i]=(long long)T[i]*T[i]%P*T[i]%P*TF[i]%P;
idft(l<<2,T),memset(T+(l<<1),0,sizeof(int)*(l<<1));
for(int i=0;i<(l<<1);i++) T[i]=(long long)(T[i]+P-H[i])*inv_2%P;
memset(T,0,sizeof(int)*l);
for(int i=0;i<(l<<1);i++) mod(H[i]=H[i]+P-T[i]);
}
memcpy(_H,H,sizeof(int)*n);
if(_TF!=NULL) memcpy(_TF,TF,sizeof(int)*(n<<1));
}
inline void sqrt(int n,int *_F,int *G)//11E(n)
{
static int H0[N],TH0[N],F[N],TF[N],G0[N],TG0[N],T[N];
memcpy(F,_F,sizeof(int)*n);
if(n==1){ G[0]=Cipolla::sqrt(F[0]); return; }
inv_sqrt(n>>1,_F,H0,TF);
memcpy(TH0,H0,sizeof(int)*(n>>1)),dft(n,TH0);
for(int i=0;i<n;i++) G0[i]=(long long)TH0[i]*TF[i]%P;
idft(n,G0),memset(G0+(n>>1),0,sizeof(int)*(n>>1));
memcpy(TG0,G0,sizeof(int)*(n>>1)),dft(n>>1,TG0);
for(int i=0;i<(n>>1);i++) T[i]=(long long)TG0[i]*TG0[i]%P;
idft(n>>1,T);
for(int i=0;i<n;i++) mod(T[i]=T[i]+P-F[i]);
for(int i=0;i<(n>>1);i++) mod(T[i+(n>>1)]+=T[i]),T[i]=0;
dft(n,T);
for(int i=0;i<n;i++) T[i]=(long long)T[i]*TH0[i]%P;
idft(n,T);
memset(T,0,sizeof(int)*(n>>1));
for(int i=0;i<n;i++) G[i]=(G0[i]+(long long)(P-T[i])*inv_2)%P;
}
inline void pow(int n,int *_F,int k,int *G)
{
static int F[N],T[N];
memcpy(F,_F,sizeof(int)*n);
int p=0,coe,inv_0;
while(p<n&&!F[p]) p++;
if(p==n){ memset(G,0,sizeof(int)*n); return; }
long long shift=(long long)k*p;
if(shift>=n){ memset(G,0,sizeof(int)*n); return; }
coe=::pow(F[p],k),inv_0=::pow(F[p],P-2);
for(int i=0;i<n;i++) F[i]=(long long)F[i]*inv_0%P;
memcpy(T,F+p,sizeof(int)*(n-p));
memset(T+(n-p),0,sizeof(int)*p);
ln(n,T,T);
for(int i=0;i<n;i++) T[i]=(long long)T[i]*k%P;
exp(n,T,T);
memset(G,0,sizeof(int)*shift);
for(int i=shift;i<n;i++) G[i]=(long long)T[i-shift]*coe%P;
}
}
Prime Sieves
只筛质数
1
2
3
4
5
const int N=10000002;
bool _b[N];
int prime[N/10],pcnt;
inline void sieve(int n){ for(int i=2;i<=n;i++){ if(!_b[i]) prime[++pcnt]=i; for(int j=1;j<=pcnt&&i*prime[j]<=n;j++){ _b[i*prime[j]]=1; if(!(i%prime[j])) break; } } }
1
2
3
4
5
6
7
inline int get_random_prime(int l,int r)
{
l=lower_bound(prime+1,prime+pcnt+1,l)-prime,r=upper_bound(prime+1,prime+pcnt+1,r)-prime-1;
static std::mt19937 r(std::random_device{}());
return prime[r()%(r-l+1)+l];
}
常见积性函数(\(\varphi,\mu,d,\mathrm{id}_k\))。其中minp表示最小素因子，而cnt表示这个素因子的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N=1000002;
bool _b[N];
int prime[N/10],pcnt;
int minp[N],cnt[N];
int mu[N],phi[N],d[N];
inline void sieve(int n)
{
mu[1]=phi[1]=d[1]=1,minp[1]=cnt[1]=0;
for(int i=2;i<=n;i++)
{
if(!_b[i]) prime[++pcnt]=i,minp[i]=i,cnt[i]=1,d[i]=2,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=pcnt&&i*prime[j]<=n;j++)
{
_b[i*prime[j]]=1,minp[i*prime[j]]=prime[j];
if(!(i%prime[j]))
{
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j];
cnt[i*prime[j]]=cnt[i]+1;
d[i*prime[j]]=d[i]/cnt[i]*(cnt[i]+1);
break;
}
mu[i*prime[j]]=-mu[i];
phi[i*prime[j]]=phi[i]*(prime[j]-1);
cnt[i*prime[j]]=1;
d[i*prime[j]]=d[i]*2;
}
}
}
分段埃筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int N=1000002;
bool b[N];
int prime[N/10],pcnt;
inline void sieve(int n){ for(int i=2;i<=n;i++){ if(!b[i]) prime[++pcnt]=i; for(int j=1;j<=pcnt&&i*prime[j]<=n;j++){ b[i*prime[j]]=1; if(!(i%prime[j])) break; } } }
const int K=1e7,C=1e3;//en this means maxn is 1e10
inline long long max(long long x,long long y){ return x>y?x:y; }
inline long long sieve(long long l,long long r)//count p in [l,r]
{
static bool _b[K+10];
#define b(i) _b[i-l]
for(long long i=l;i<=r;i++) b(i)=0;
for(int i=1;(long long)prime[i]*prime[i]<=r;i++)
for(long long j=max(prime[i]<<1,(l+prime[i]-1)/prime[i]*prime[i]);j<=r;j+=prime[i]) b(j)=1;
long long ans=0;
for(long long i=l,temp;i<=r;i++) if(!b(i)) ans++;
return ans;
}
long long table[C+2];
inline void calc_table()
{
freopen("t.out","w",stdout);
sieve(1000000),printf("0,");
for(int i=1;i<=C;i++)
table[i]=table[i-1]+sieve(max(1,(long long)(i-1)*K),(long long)i*K-1),printf("%lld,",table[i]),fprintf(stderr,"%d\n",i);
}
inline long long query(long long n){ return table[n/K]+sieve(max(n/K*K,1),n); }
Queue
1
2
3
const int N=2000002;
struct Queue{ int head,tail,q[N]; inline void clear(){ head=1,tail=0; } inline Queue(){ head=1,tail=0; } inline void push(int x){ q[++tail]=x; } inline void pop(){ head++; } inline int front(){ return q[head]; } inline bool empty(){ return head>tail; } };
Quick Sort
1
2
#define quick_sort sort
牛逼!
Radix Sort
给a[1]到a[n]排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void radix_sort(int n,int *a)
{
const int N=100002;
static unsigned int b[256];
static int t[N];
#define _RADIX_SORT(a,t,n,B)\
{\
memset(b,0,sizeof(b));\
for(int *it=a+n;it!=a;it--) ++b[(*it>>B)&255];\
for(unsigned int *it=b;it!=b+255;it++) *(it+1)+=*it;\
for(int *it=a+n;it!=a;it--) t[b[(*it>>B)&255]--]=*it;\
}
_RADIX_SORT(a,t,n,0)
_RADIX_SORT(t,a,n,8)
_RADIX_SORT(a,t,n,16)
_RADIX_SORT(t,a,n,24)
}
SA
SAM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int trans[2000002][26],link[2000002],maxlen[2000002],ncnt=1,last=1;
inline void insert(int c)
{
int cur=++ncnt,u;
maxlen[cur]=maxlen[last]+1;
for(u=last;u&&!trans[u][c];u=link[u])
trans[u][c]=cur;
if(!u)
link[cur]=1;
else
{
int v=trans[u][c];
if(maxlen[v]==maxlen[u]+1) link[cur]=v;
else
{
int w=++ncnt;
for(int i=0;i<26;i++) trans[w][i]=trans[v][i];
link[w]=link[v];
maxlen[w]=maxlen[u]+1;
for(;u&&trans[u][c]==v;u=link[u])
trans[u][c]=w;
link[cur]=link[v]=w;
}
}
last=cur;
}
inline int insert(int c)
{
int u=++ncnt,p;
maxlen[u]=maxlen[last]+1;
for(p=last;p&&!trans[p][c];p=link[p]) trans[p][c]=u;
if(!p) return link[u]=1,u;
int v=trans[p][c];
if(maxlen[v]==maxlen[p]+1) return link[u]=v,u;
int w=++ncnt;
memcpy(trans[w],trans[v],sizeof(int)*26);
link[w]=link[v],maxlen[w]=maxlen[p]+1,link[u]=link[v]=w;
for(;p&&trans[p][c]==v;p=link[p]) trans[p][c]=u;
return u;
}
multi-string sam
when the char set is big
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
map<int,int> ch[200002];
int maxlen[200002],parent[200002],cnt=1;
inline int sam_insert(int last,int c)
{
int cur=ch[last][c];
if(maxlen[cur]) return cur;
maxlen[cur]=maxlen[last]+1;
int p=parent[last];
for(;p&&!ch[p][c];p=parent[p]) ch[p][c]=cur;
if(!p){ parent[cur]=1;return cur; }
int q=ch[p][c];
if(maxlen[p]+1==maxlen[q]){ parent[cur]=q;return cur; }
int clone=++cnt;
for(auto it:ch[q]) ch[clone][it.first]=maxlen[it.second]?it.second:0;
maxlen[clone]=maxlen[p]+1;
for(;p&&ch[p][c]==q;p=parent[p]) ch[p][c]=clone;
parent[clone]=parent[q],parent[cur]=parent[q]=clone;
return cur;
}
struct Pair{ int last,c; };
struct Queue{ int head,tail; Pair q[200002]; inline void clear(){ head=1,tail=0; } inline void push(Pair x){ q[++tail]=x; } inline void pop(){ head++; } inline Pair front(){ return q[head]; } inline bool empty(){ return head>tail; } }q;
inline void build()
{
parent[1]=0;
q.clear();
for(auto it:ch[1]) q.push({1,it.first});
while(!q.empty())
{
Pair now=q.front();q.pop();
int last=sam_insert(now.last,now.c);
for(auto it:ch[last]) q.push((Pair){last,it.first});
}
}
如何背诵sam?只需要记住多串sam插入的流程。
我们需要知道trie上的父亲last和父亲到当前点的转移字符c。当前点是cur。
从父亲开始跳parent，直到跳到一个存在转移c的点p，这之前的点的转移c都连到cur，而设这个存在的转移从p指向q。
如果maxlen[p]+1=maxlen[q]，称这个转移为连续的，它不会被修改，此时我们让cur的parent连向q并结束。
否则复制q得到新点clone，让p->clone是连续的转移，并用clone替换q的地位(从p出发跳parent把极长的连到q的转移c改成连到clone)。让q和cur的parent连到clone。
Segment Tree
simple
1
2
3
4
5
6
7
8
9
10
11
const int N=200002;
struct Node{ int l,r; }t[4*N];
#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)
inline void push_up(int u){ }
inline void add_tag(int u){ }
inline void push_down(int u){ add_tag(lq(u),t[u].tag),add_tag(rq(u),t[u].tag),t[u].tag=0; }
void build(int l,int r,int u){ t[u].l=l,t[u].r=r;if(l==r){ ;return; }int mid=t[u].l+t[u].r>>1;build(l,mid,lq(u)),build(mid+1,r,rq(u)),push_down(u); }
void change(int l,int r,int u,int v){ if(l<=t[u].l&&t[u].r<=r){ add_tag(u,v);return; }int mid=t[u].l+t[u].r>>1;push_down(u);if(l<=mid) change(l,r,lq(u),v);if(mid+1<=r) change(l,r,rq(u),v);push_up(u); }
int query(int l,int r,int u){ if(l<=t[u].l&&t[u].r<=r) return;int mid=t[u].l+t[u].r>>1;push_down(u);return (l<=mid?query(l,r,lq(u):0))+(mid+1<=r?query(l,r,rq(u)):0); }
zkw’s segt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int L=2097152;
A t[L<<1];
inline void build()
{
for(int i=n+L;i>L;i--) t[i]=;
for(int i=L-1;i;i--) t[i]=t[i<<1]+t[i<<1|1];
}
inline A query(int l,int r)
{
A ansl,ansr;
l+=L-1,r+=L+1;
for(;l^r^1;l>>=1,r>>=1) (~l&1)&&(ansl=ansl+t[l^1],0),(r&1)&&(ansr=t[r^1]+ansr,0);
return ansl+ansr;
}
inline void push_ups(int p){ p+=L; while(p>>=1) t[p]=t[p<<1]+t[p<<1|1]; }
Simplex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#define float __float128
const float eps=1e-16,inf=1e9;
const int N=42;//max n+m
int n,m,t;
int id[N];
float a[N][N];
inline int sgn(float x){ return (-eps<x&&x<eps)?0:(x>0?1:-1); }
inline void pivot(int x,int y)
{
swap(id[n+x],id[y]);
float c=-a[x][y];
for(int i=0;i<=n;i++) a[x][i]/=c;
a[x][y]=-1/c;
for(int i=0;i<=m;i++)
if(i!=x&&sgn(a[i][y]))
for(int j=(c=a[i][y],a[i][y]=0,0);j<=n;j++) a[i][j]+=a[x][j]*c;
}
inline int simplex()
{
for(int i=1;i<=n+m;i++) id[i]=i;
while(1)
{
int x=1,y=0;
for(int i=1;i<=m;i++) if(a[i][0]<a[x][0]) x=i;
if(sgn(a[x][0])>=0) break;
for(int j=1;j<=n;j++) if(sgn(a[x][j])>0&&(!y||id[j]>id[y])) y=j;
if(!y) return 1;//Infeasible
pivot(x,y);
}
while(1)
{
int x=0,y=1;
float minn=inf;
for(int j=1;j<=n;j++) if(a[0][j]>a[0][y]) y=j;
if(sgn(a[0][y])<=0) break;
for(int i=1,temp;i<=m;i++)
if(sgn(a[i][y])<0&&(temp=sgn(-a[i][0]/a[i][y]-minn),temp<0||(temp==0&&(!x||id[i]>id[x])))) x=i,minn=-a[i][0]/a[i][y];
if(!x) return 2;//Unbounded
pivot(x,y);
}
return 0;
}
Simpson
1
2
3
4
5
6
7
8
9
10
11
12
inline double f(double x){ }
inline double calc(double l,double r){ return (f(l)+f(r)+4*f((l+r)/2))*(r-l)/6; }
inline double simpson(double l,double r,double A,double eps)
{
if(eps<1e-100){ fprintf(stderr,"Sorry, Simpson can't fuck it.\n");exit(0); }
if(r-l<eps) return A;
double mid=(l+r)/2;
double L=calc(l,mid),R=calc(mid,r);
if(fabs(L+R-A)<eps) return A;
return simpson(l,mid,L,eps/2)+simpson(mid,r,R,eps/2);
}
SPFA
Split-merge Treap
I know it is slow.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inline unsigned long long xor64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
struct Node{ int val,size; int lq,rq; }t[1100002];
#define lq(u) t[u].lq
#define rq(u) t[u].rq
int ncnt;
inline int new_node(int _val,int _size=1,int _lq=0,int _rq=0){ return t[++ncnt]={_val,_size,_lq,_rq},ncnt; }
inline void push_up(int u){ t[u].size=t[lq(u)].size+t[rq(u)].size+1; }
inline bool cmp(int u,int v){ return xor64()%(t[u].size+t[v].size)<t[u].size; }
void split(int u,int k,int &x,int &y)
{
if(!u){ x=y=0;return; }
if(t[u].val<=k) split(rq(u),k-t[lq(u)].size-1,rq(u),y),x=u;
//t[lq(u)].size+1<=k split by rank
else split(lq(u),k,x,lq(u)),y=u;
push_up(u);
}
int merge(int u,int v)
{
if(!u||!v) return u|v;
if(cmp(u,v)) return rq(u)=merge(rq(u),v),push_up(u),u;
else return lq(v)=merge(u,lq(v)),push_up(v),v;
}
inline void insert(int &rt,int x)
{
int u,v=new_node(x),w;
split(rt,x,u,w),rt=merge(u,merge(v,w));
}
inline void erase(int &rt,int x)
{
int u,v,w;
split(rt,x,rt,w),
split(rt,x-1,u,v),
v=merge(lq(v),rq(v)),
rt=merge(u,merge(v,w));
}
int rank(int u,int x){ if(!u) return 1;return t[u].val>=x?rank(lq(u),x):t[lq(u)].size+1+rank(rq(u),x); }
int kth(int u,int k){ if(t[lq(u)].size+1==k) return t[u].val;return t[lq(u)].size>=k?kth(lq(u),k):kth(rq(u),k-t[lq(u)].size-1); }
inline int pre(int u,int x){ return kth(u,rank(u,x)-1); }
inline int suc(int u,int x){ return kth(u,rank(u,x+1)); }
another version, maintaining father
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Node{ int size,first; int lq,rq,fa; }t[500002];
#define lq(u) t[u].lq
#define rq(u) t[u].rq
#define fa(u) t[u].fa
int ncnt;
inline int new_node(int _size=1,int _lq=0,int _rq=0,int _fa=0){ return ncnt++,t[ncnt]={_size,ncnt,_lq,_rq,_fa},ncnt; }
inline void push_up(int u){ t[u].size=t[lq(u)].size+t[rq(u)].size+1,t[u].first=min(min(t[lq(u)].first,t[rq(u)].first),u); }
inline bool cmp(int u,int v){ return randi64()%(t[u].size+t[v].size)<t[u].size; }
void split(int u,int k,int &x,int &y)
{
if(!u){ x=y=0;return; }
fa(u)=0;
if(t[u].val<=k) split(rq(u),k-t[lq(u)].size-1,rq(u),y),fa(rq(u))=u,x=u;
//t[lq(u)].size+1<=k split by rank
else split(lq(u),k,x,lq(u)),fa(lq(u))=u,y=u;
push_up(u);
}
int merge(int u,int v)
{
if(!u||!v) return u|v;
if(cmp(u,v)) return rq(u)=merge(rq(u),v),fa(rq(u))=u,push_up(u),u;
else return lq(v)=merge(u,lq(v)),fa(lq(v))=v,push_up(v),v;
}
inline int find_root(int u){ while(fa(u)) u=fa(u); return u; }
inline int rank(int u){ int ans=t[lq(u)].size+1; while(fa(u)) (u==rq(fa(u))&&(ans+=t[lq(fa(u))].size+1)),u=fa(u); return ans; }
inline int kth(int u,int k){ if(k==t[lq(u)].size+1) return u; return k<=t[lq(u)].size?kth(lq(u),k):kth(rq(u),k-t[lq(u)].size-1); }
ST Table
1
2
3
4
5
6
const int N=100002;
int f[20][N],g[20][N],lg[N];
inline void init(int n,int *a){ for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++) f[0][i]=a[i],g[0][i]=a[i]; for(int k=1;k<=lg[n];k++)for(int i=1;i<=n;i++) f[k][i]=min(f[k-1][i],f[k-1][i+(1<<k-1)]),g[k][i]=max(g[k-1][i],g[k-1][i+(1<<k-1)]); }
inline int query_min(int l,int r){ int k=lg[r-l+1]; return min(f[k][l],f[k][r-(1<<k)+1]); }
inline int query_max(int l,int r){ int k=lg[r-l+1]; return max(g[k][l],g[k][r-(1<<k)+1]); }
Stack
1
2
3
const int N=2000002;
struct Stack{ int cnt,s[N]; inline void clear(){ cnt=0; } inline Stack(){ clear(); } inline void push(int x){ s[++cnt]=x; } inline void pop(){ cnt--; } inline int top(){ return s[cnt]; } inline bool empty(){ return !cnt; } };
String Hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N=1000002;
const unsigned long long P=(1<<61)-1;
struct Z{ unsigned long long x; };
inline Z operator + (Z a,Z b){ return a.x+b.x&P; }
inline Z operator - (Z a,Z b){ return a.x<b.x?a.x+P-b.x&P:a.x-b.x&P; }
inline Z operator * (Z a,Z b)
{
unsigned long long a1=(unsigned int)a.x,a2=a.x>>32,b1=(unsigned int)b.x,b2=b.x>>32;
unsigned long long l=a1*b1,m=a1*b2*a2*b1,h=a2*b2;
unsigned long long c=(l&P)+(l>>61)+(h<<3)+(m>>29)+(m<<35>>3)+1;
return c=(c&P)+(c>>61),c=(c&P)+(c>>61),c-1;
}
const Z B=;
Z pow_B[N];
inline void init(int n){ pow_B[0]=1;for(int i=1;i<=n;i++) pow_B[i]=pow_B[i-1]*B; }
struct S{ int len; Z h; };
inline S operator + (S a,S b){ return {a.len+b.len,a.h*pow_B[b.len]+b.h}; }
struct R
{
Z h[N];
inline void build(int n,char *s){ for(int i=1;i<=n;i++) h[i]=h[i-1]+{1,s[i]}; }
inline void query(int l,int r){ return h[r]-h[l-1]*pow_B[r-l+1]; }
};
Subsequence AM
Tarjan for DCC
Timer
1
2
3
4
5
6
7
8
#include<time.h>
struct Timer
{
clock_t start;
inline Timer(){ start=clock(); }
inline void log(){ fprintf(stderr,"%.6lf\n",(double)(clock()-start)/CLOCKS_PER_SEC); }
};
Train Head
of Mr_Eight
1
2
3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
all optimizition
1
2
3
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
Union-find Set
路径压缩
1
2
3
4
5
int f[N];
inline void clear(int n){ for(int i=1;i<=n;i++) f[i]=i; }
int find(int x){ return f[x]==x?x:f[x]=find(f[x]); }
inline void merge(int x,int y){ f[find(x)]=find(y); }
wrong 1 times/hanx
启发式合并
1
2
3
4
5
6
const int N=2000002;
int f[N],size[N];
inline void clear(int n){ for(int i=1;i<=n;i++) f[i]=i,size[i]=1; }
inline int find(int x){ while(x!=f[x]) x=f[x]; return x; }
inline void merge(int x,int y){ if((x=find(x))!=(y=find(y))) size[x]>size[y]?f[y]=x:f[x]=y; }
Xor Liner Base
Xorshift
xorshift64 and xorshift128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
inline unsigned long long randi64(){ static unsigned long long x=88172645463325252ll; return x^=x<<13,x^=x>>7,x^=x<<17; }
inline unsigned __int128 randi128()
{
static unsigned long long s[2]={998244353,1004535809};
unsigned long long s0=s[1],s1=s[0]; unsigned __int128 res=((unsigned __int128)s0<<64)^s1;
s[0]=s0,s1^=s1<<23,s[1]=s1^s0^(s1>>18)^(s0>>5); return res;
}
inline unsigned long long randi64()
{
static unsigned long long s[2]={998244353,1004535809};
unsigned long long s0=s[1],s1=s[0]; unsigned __int128 res=s0+s1;
s[0]=s0,s1^=s1<<23,s[1]=s1^s0^(s1>>18)^(s0>>5); return res;
}
#define randf64() ((randi64()>>11)*(1.1102230246251565404236316680908203125e-16))
//a UniformRandomBitGenerator
struct Rand
{
using result_type=unsigned long long;
unsigned long long x;
inline Rand(unsigned long long _x=88172645463325252ll):x(_x){}
inline unsigned long long operator () () { return x^=x<<13,x^=x>>7,x^=x<<17; }
static constexpr unsigned long long min(){ return 0; }
static constexpr unsigned long long max(){ return 0xffffffffffffffffull; }
};
//xorshift128+
struct Rand
{
unsigned long long s[2];
inline Rand(unsigned long long _s0=1145141919810ll,unsigned long long _s1=1919810114514ll){ s[0]=_s0,s[1]=_s1; }
inline unsigned long long rotl(const unsigned long long x,const int k){ return (x<<k)|(x>>(64-k)); }
inline unsigned long long next()
{
const unsigned long long s0=s[0];
unsigend long long s1=s[1];
const uint64_t res=s0+s1;
s1^=s0,s[0]=rotl(s0,24)^s1^(s1<<16),s[1]=rotl(s1,37);
return result;
}
inline void jump()//not O(1) but O(log v=64)
{
static const unsigned long long JUMP[]={0xdf900294d8f554a5,0x170865df4b3201fc};
unsigned long long s0=0,s1=0;
for(int i=0;i<2;i++)
for(int b=0;b<64;b++)
{
if(JUMP[i]&UINT64_C(1)<<b) s0^=s[0],s1^=s[1];
next();
}
s[0]=s0,s[1]=s1;
}
}
the seed can be any number you like because the period is \(2^{64}-1,2^{128}-1\) so every number is in the loop.
xorshift128_lf gives a double in [0,…,1), maybe.
Y-center
1
2
#define y_center(u,v,w) (lca(u,v)^lca(u,w)^lca(v,w))
too much water!
Z Algo
1
2
3
4
5
6
7
8
9
10
11
inline void Z(int n,char *s,int *z)
{
z[1]=n;
for(int i=2,l=1,r=1;i<=n;i++)
{
if(i<=r) z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) z[i]++;
if(i+z[i]-1>r) r=i+z[i]-1,l=i;
}
}