int fa[N];intgetfa(int x){if(fa[x]== x)return x;
fa[x]=getfa(fa[x]);return fa[x];}
生成树 Kruskal
structEdge{int u, v, w;} e[M];boolcmp(Edge a, Edge b){return a.w > b.w;}int tot;voidkruskal(){sort(e +1, e +1+ tot, cmp);for(int i =1; i <= tot; i++){int u = e[i].u, v = e[i].v;double w = e[i].w;if(w <10|| w >1000)continue;if(getfa(u)!=getfa(v)){
ans += w *100;
fa[getfa(u)]=getfa(v);}}}
LCA
倍增
//1<<18 = 262144//1<<19 = 524288//如果总的点数为1e6就选择19就好了//1<<20 = 1048576int dep[N], pos[N][20];inlinevoiddfs(int u,int fa){for(int i =1; i <=18; i++){if(dep[u]<(1<< i))break;
pos[u][i]= pos[pos[u][i -1]][i -1];}for(int i = head[u]; i; i = e[i].nt){int v = e[i].b;if(v == fa)continue;
pos[v][0]= u;
dep[v]= dep[u]+1;dfs(v, u);}}intlca(int x,int y){if(dep[x]< dep[y])swap(x, y);int t = dep[x]- dep[y];for(int i =0; i <=18&& t; i++, t >>=1)if(t &1) x = pos[x][i];if(x == y)return x;for(int i =18; i >=0; i--){if(pos[x][i]!= pos[y][i]){
x = pos[x][i];
y = pos[y][i];}}return pos[x][0];}
voidupdate(int x,int t){for(int i = x; i <= n; i += i &(-i)) c1[i]+= t, c2[i]+= t * x;}intquery(int x){int ret =0;for(int i = x; i; i -= i &(-i)) ret += c1[i]*(x +1)- c2[i];return ret;}voidbuild(){int mem =0;for(int i =1; i <= n; i++)update(i, val[i]- mem), mem = val[i];}//更新区间[l,r]update(l, k);update(r +1,-k);//求区间和[l,r]query(r)-query(l -1)
voidupdate(int x,int y,int t){for(int i = x; i <= n; i += i &(-i))for(int j = y; j <= m; j += j &(-j))
c[i][j]+= t;}intquery(int x,int y){int ret =0;for(int i = x; i; i -= i &(-i))for(int j = y; j; j -= j &(-j))
ret += c[i][j];return ret;}(a,b)为左上角(c,d)为右下角,ans=query(c,d)-query(a-1,d)-query(c,b-1)+query(a-1,b-1)
区间修改方法
初始时
0000000000000000
差分数组修改方法
00000 k 0-k
00000-k 0 k
原数组变化效果
00000 k k 00 k k 00000
左上角为(x,y)右下角为(a,b)的矩形区域都加上k
update(x, y, k);update(x, b +1,-k);update(a +1, y,-k);update(a +1, b +1, k);
voidupdate(int x,int y,int t){for(int i = x; i <= n; i += i &(-i))for(int j = y; j <= m; j += j &(-j)){
c1[i][j]+= t;
c2[i][j]+= t * x;
c3[i][j]+= t * y;
c4[i][j]+= t * x * y;}}intquery(int x,int y){int ret =0;for(int i = x; i; i -= i &(-i))for(int j = y; j; j -= j &(-j))
ret += c1[i][j]*(x +1)*(y +1)- c2[i][j]*(y +1)- c3[i][j]*(x +1)+ c4[i][j];return ret;}//更新和查询方法和上述两篇代码一样
线段树
基础
//以区间加,区间查询为例structnode{int l, r, tag, sum;}c[N*8];voidbuild(int p,int l,int r){//重置新开的点
c[p].l = l, c[p].r = r;
c[p].sum =0, c[p].tag =0;if(l == r){read(c[p].sum);return;}int m =(l + r)>>1;build(p <<1, l, m);build(p <<1|1, m +1, r);//标记上传pushup(p);}voidadd(int p,int l,int r,int k){if(c[p].l == l && c[p].r == r){//更新该区间
c[p].sum +=(r - l +1)* k;
c[p].tag += k;return;}//标记下移pushdown(p);//分区段讨论int m =(c[p].l + c[p].r)>>1;if(r <= m)add(p <<1, l, r, k);elseif(l > m)add(p <<1|1, l, r, k);else{add(p <<1, l, m, k);add(p <<1|1, m +1, r, k);}pushup(p);}//此处还有一种不用讨论的写法voidadd(int p,int l,int r,int k){int L = c[p].l, R = c[p].r;if(L > r || R < l)return;//在此处进行判断目标区间是否超出当前节点的区间范围if(L >= l && R <= r){
c[p].sum +=(R - L +1)* k;
c[p].addv += k;return;}pushdown(p);add(p <<1, l, r, k);add(p <<1|1, l, r, k);pushup(p);}//还可以这样写voidadd(int p,int l,int r,int k){int L = c[p].l, R = c[p].r;if(L >= l && R <= r){
c[p].sum +=(R - L +1)* k;
c[p].addv += k;return;}pushdown(p);int m =(c[p].l + c[p].r)>>1;if(l <= m)add(p <<1, l, r, k);//这说明左儿子中一定有目标区间的一部分if(r > m)add(p <<1|1, l, r, k);//同理这说明右儿子中有目标区间的一部分pushup(p);}intquery(int p,int l,int r){if(c[p].l == l && c[p].r == r)return c[p].sum;pushdown(p);int m =(c[p].l + c[p].r)>>1;if(r <= m)returnquery(p <<1, l, r);elseif(l > m)returnquery(p <<1|1, l, r);elsereturnquery(p <<1, l, m)+query(p <<1|1, m +1, r);}
非递归线段树
/*
* File : segment_tree.cpp
* Time : 2023/03/17 11:02:11
* Author : wty-yy
* Version : 1.0
* Blog : https://wty-yy.space/
* Desc : efficient segment tree, [模板]线段树 1: https://www.luogu.com.cn/problem/P3372
懒标记非递归线段树,支持区间修改,区间求和.
*/#include<iostream>#include<algorithm>#include<cstring>#include<math.h>#include<vector>#include<map>#definelllonglong#definevivector<int>#defineviivector<vi>#definepiipair<int,int>#definevipvi<pii>#definemkpmake_pair#definepbpush_backusingnamespace std;constint N =1e5;classlazy_segment{public:int n, h;
ll t[N<<1], lazy[N];lazy_segment(int n):n(n){memset(t,0,sizeof(t));memset(lazy,0,sizeof(lazy));
h =sizeof(int)*8-__builtin_clz(n);}voidcalc(int p,int k){// pushup更新父节点
t[p]= t[p<<1]+ t[p<<1|1]+ k * lazy[p];}voidapply(int p, ll value,int k){// pushdown中下传懒标记
t[p]+= value * k;if(p < n) lazy[p]+= value;}voidbuild(int l,int r){// pushup区间[l,r)int k =2;for(l += n, r += n-1; l >1; k <<=1){
l >>=1, r >>=1;for(int i = r; i >= l; i--)calc(i, k);}}voidpush(int l,int r){// pushdown区间[l,r)int s = h, k =1<<(h-1);for(l += n, r += n-1; s >0;--s, k >>=1){for(int i = l >> s; i <= r >> s;++i){if(lazy[i]!=0){apply(i<<1, lazy[i], k);apply(i<<1|1, lazy[i], k);
lazy[i]=0;}}}}voidmodify(int l,int r, ll value){// 区间[l,r)同时增加valuepush(l, l +1);push(r -1, r);int l0 = l, r0 = r, k =1;for(l += n, r += n; l < r; l >>=1, r >>=1, k <<=1){if(l&1)apply(l++, value, k);if(r&1)apply(--r, value, k);}build(l0, l0 +1);build(r0 -1, r0);}
ll query(int l,int r){// 区间[l,r)求和push(l, l +1);push(r -1, r);
ll ret =0;for(l += n, r += n; l < r; l >>=1, r >>=1){if(l&1) ret += t[l++];if(r&1) ret += t[--r];}return ret;}voidprint(){// 输出全部数组for(int i =0; i < n <<1; i++) cout << t[i]<<' ';
cout <<'\n';}};signedmain(){
cin.tie(0);
ios::sync_with_stdio(0);int n, m;
cin >> n >> m;
lazy_segment seg(n);for(int i =0; i < n; i++) cin >> seg.t[n + i];
seg.build(0, n);while(m--){int opt, x, y;
ll value;
cin >> opt >> x >> y;if(opt ==1){
cin >> value;
seg.modify(x-1, y, value);}else cout << seg.query(x-1, y)<<'\n';}return0;}
//根据题意建好有向边for(int i =1; i <= n; i++)if(idx[i]== idx[get(i)]){//get(x)用于获取x'的序号printf("IMPOSSIBLE");return0;}for(int i =1; i <= n; i++){if(idx[i]< idx[get(i)])printf("%d\n", i);elseprintf("%d\n",get(i));}
structSAM{int cnt, last, ch[N][26], mx[N], prt[N];int sz[N];//统计该节点right集合大小,就是在母串中出现的次数SAM(){cnt = last =1;}//记得初始化voidadd(int c){int p = last, np =++cnt; last = np;
mx[np]= mx[p]+1; sz[np]=1;for(; p &&!ch[p][c]; p = prt[p]) ch[p][c]= np;if(!p) prt[np]=1;else{int q = ch[p][c];if(mx[q]== mx[p]+1) prt[np]= q;else{int nq =++cnt; mx[nq]= mx[p]+1;
prt[nq]= prt[q]; prt[q]= prt[np]= nq;memcpy(ch[nq], ch[q],sizeof(ch[q]));for(; ch[p][c]== q; p = prt[p]) ch[p][c]= nq;}}}//进行拓扑排序voiddp(){for(int i = cnt; i; i--){
sz[prt[c[i]]]+= sz[c[i]];}}} sam;
桶排序(简化拓扑排序)
//桶排序,按照mx[]的从小到大排序在c[]中int t[N], c[N];voidtsort(){for(int i =1; i <= cnt; i++) t[mx[i]]++;//入桶for(int i =1; i <= cnt; i++) t[i]+= t[i -1];//记录排名for(int i =1; i <= cnt; i++) c[t[mx[i]]--]= i;//排名对应序号for(int i = cnt; i >=1; i--) sz[prt[c[i]]]+= sz[c[i]];//对sz数组进行累加,求出一个节点中的endpos出现次数,即拓扑排序后的DP}
倍增
在parent树上进行倍增,可以快速O(logn)求出子串属于SAM中的哪个节点
int pos[N][20];voidinit(){for(int i =1; i <= cnt; i++) pos[i][0]= prt[i];for(int j =1; j <20; j++)//从小到大for(int i =1; i <= cnt; i++) pos[i][j]= pos[pos[i][j -1]][j -1];}intfind(int p,int len){//p为当前子串右端点在SAM上对应的位置//从大到小for(int i =19; i >=0; i--)if(mxl[pos[p][i]]>= len) p = pos[p][i];}
voidadd(int c){if(ch[last][c]&& mxl[ch[last][c]]== mxl[last]+1){
last = ch[last][c];return;}///...其他部分与标程一致...}voidinit(){
last =1;for(int i =1; i <= len; i++)add(s[i]-'a');
}
char A[N <<1];int len, rad[N <<1];//rad[i]表示(以i为对称中心的最长回文串的长度+1)/2//len保存处理后的总数组长度voidinit(){char c =getchar();//对0做一个特殊的标记,保证不会与后面的符号重复
A[0]='~'; A[++len]='#';//'#'作为分隔符号while(c <'a'|| c >'z') c =getchar();while(c >='a'&& c <='z'){A[++len]= c; A[++len]='#'; c =getchar();}}voidManacher(){init();for(int i =1, r =0, mid =0; i <= len; i++){//如果i在已经处理过的长度之内,则可以对称找到现有可以处理到的最长长度rad[i],但绝对不可能处理到还未处理过的长度(就是r的右侧)if(i <= r) rad[i]=min(rad[(mid <<1)- i], r - i +1);//开始尝试向外拓展while(A[i - rad[i]]== A[i + rad[i]])++rad[i];//如果当前拓展的长度大于了已有的扫描范围,就更新右端端点r和对称中心midif(i + rad[i]> r) r = i + rad[i]-1, mid = i;}}
#definevivector<int>
vi z_function(string &s){int n = s.size();
vi z(n);//注意z[0]定义为0for(int i =1, l =0, r =0; i < n; i++){if(i <= r && z[i-l]< r - i +1) z[i]= z[i-l];else{
z[i]=max(0, r-i+1);while(i + z[i]< n && s[z[i]]== s[i+z[i]]) z[i]++;}if(i + z[i]-1> r) l = i, r = i + z[i]-1;}return z;}
数论
快速乘
当模数的阶接近264时,两数相乘可能会导致溢出。即a⋅b(modm)
1.0
类比快速幂的思路,复杂度为O(logn)
intmul(int a,int b,int mod){int ret =0;while(b){if(b &1)(ret += a)%= mod;(a += a)%= mod;
b >>=1;}return ret;}
2.0
优化版,速度可以快到O(1)
intmul(int a,int b,int mod){if(mod <=1e9)return a * b % mod;elseif(mod <=1e12)return(((a *(b >>20)% mod)<<20)+ a *(b &((1<<20)-1)))% mod;else{
ul c =(ld)a / mod * b;int ret =(ul)a * b - c * mod;return(ret + mod)% mod;}}
intexgcd(int a,int c,int m){if(!a)return0;return(c - m *exgcd(m % a, c, a))/ a;//return (((c - m * exgcd(m % a, c, a)) / a) % m + m) % m;//若想返回最小正剩余就先模m再加m再模m}exgcd((71,2019,2018)+2019)%2019;//由于最后的结果不一定能保证是最小非负剩余故最后要对结果+m%mexgcd((71,2019,1)+2019)%2019;\\那么对于a的在模m意义下的逆元也就是c=1时的解
2.0
由于1.0版本的Exgcd会去计算一个m * exgcd(m % a, c, a),如果m为1018那么就会爆掉long long,这是十分令人不开心的。于是改进方法,变为直接去思考ax+by=(a,b)中x,y的特解。
int n, m =1;int A[N], B[N], ans;signedmain(){read(n);for(int i =1; i <= n; i++){read(A[i]),read(B[i]);
m *= A[i];}for(int i =1; i <= n; i++)(ans +=(m / A[i])*exgcd(m / A[i],1, A[i])* B[i])%= m;//这里用的exgcd是1.0版本的printf("%lld\n", ans);return0;}
signedmain(){read(n);int b, m;read(m),read(b);for(int i =2; i <= n; i++){int bb, mm;read(mm),read(bb);
b +=exgcd(m, bb - b, mm)* m;//这里用的exgcd是1.0版本的
m =lcm(m, mm);
b %= m;}printf("%lld\n", b);system("pause");return0;}
//计算x^2=n(mod p)int p, n, w;//w为i^2所对应的数structnum{//建立一个"复数域"int a, b;num(int a =0,int b =0):a(a),b(b){}//初始化函数
num operator*=(num &x){int aa = a * x.a % p + b * x.b % p * w % p;int bb = a * x.b % p + b * x.a % p;
a = aa;
b = bb;}};
num ksm(num x,int a){//既可以做整数,也可以做复数的ksm
num ret =1;while(a){if(a &1)(ret *= x);
x *= x;
a >>=1;}return ret;}boolcheck(int x){//判断x是否是模p的二次剩余returnksm(x,(p -1)>>1).a ==1;}signedmain(){srand(time(NULL));read(n),read(p);if(!check(n)){printf("无解\n");return0;}int a =rand()% p;while(!a ||check(((a * a % p - n)% p + p)% p)){//如果a^2-n为二次剩余就继续找
a =rand()% p;}
w =((a * a % p - n)% p + p)% p;//计算i^2所对应的数int ans1 =(ksm(num(a,1),(p +1)>>1).a % p + p)% p;int ans2 = p - ans1;printf("%lld %lld\n", ans1, ans2);return0;}
intbsgs(int a,int b,int p){//solve a^x=b (mod p)
unordered_map<int,int> hsh;//系统自带哈希表,O(1)查询速度int m =sqrt(p)+1, w = b * a % p;for(int i =1; i <= m; i++,(w *= a)%= p) hsh[w]= i;//先枚举Bint wn =ksm(a, m, p); w = wn;for(int i =1; i < m; i++,(w *= wn)%= p)if(hsh[w])return i * m - hsh[w];//再枚举Areturn-1;}
由于 m=⌊pm⌋p+mmodp。左侧求和中 x 的次幂均为 p 的倍数,右侧求和中 x 的次幂均在 0∼p−1,由带余数除法知,当且仅当 i=⌊pm⌋,j=mmodp 时, x 的次幂为 m,其系数为 (⌊pm⌋⌊pn⌋)(mmodpnmodp)。QED
时间复杂度为 f(p)+logpn ,f(p)=plogp 为预处理组合数复杂度。
voidinit(int p){//预处理组合数,算出1~(p-1)中数的阶乘和对应的逆
jie[0]= ni[0]=1;for(int i =1; i < p; i++) jie[i]= jie[i -1]* i % p, ni[i]=ksm(jie[i], p -2, p);}intC(int n,int m,int p){//计算组合数if(n < m)return0;return jie[n]* ni[m]% p * ni[n - m]% p;}intC(int n,int m,int p){//当然也可以直接计算,不用预处理,不同模数时效率更高if(n < m)return0;int a =1, b =1;for(int i = n - m +1; i <= n; i++)(a *= i)%= p;for(int i =1; i <= m; i++)(b *= i)%= p;return a *ksm(b, p -2, p)% p;}intlucas(int n,int m,int p){//Lucas定理if(m ==0)return1;returnlucas(n / p, m / p, p)*C(n % p, m % p, p)% p;}
exLucas
用于求解 x≡(mn)(modM) 其中 M 为合数。
记 M 的标准分解为 M=p1α1p2α2⋯psαs=i=1∏spiαi,于是原方程等价于求解:(最后用CRT合并)
int con, sum;//con为常数,就是上述n!公式中的第三项的底数。sum就是顺便求出来的x-y-z。intF(int n,int p,int pp,int fg){//递归求解n!/p^alpha在模pp下的值if(n ==0)return1;int tmp =1; sum += fg * n / p;//计算beta(n,p)for(int i =1; i <= n % pp; i++)if(i % p)(tmp *= i)%= pp;returnF(n / p, p, pp, fg)*ksm(con, n / pp, pp)% pp * tmp % pp;}intC_pp(int n,int m,int p,int pp){//计算组合数nm在模pp下的值
con =1; sum =0;for(int i =1; i <= pp; i++)if(i % p)(con *= i)%= pp;int nn =F(n, p, pp,1), mm =inv(F(m, p, pp,-1), pp), nm =inv(F(n - m, p, pp,-1), pp);return nn * mm % pp * nm % pp *ksm(p, sum, pp)% pp;}intexLucas(int n,int m,int p){int tmp = p, ret =0;for(int i =2; i * i <= p; i++){//对p做标准分解if(tmp % i)continue;
P[++pcnt]=1;while(tmp % i ==0) tmp /= i, P[pcnt]*= i;
A[pcnt]=C_pp(n, m, i, P[pcnt]);}if(tmp !=1) P[++pcnt]= tmp, A[pcnt]=C_pp(n, m, tmp, tmp);for(int i =1; i <= pcnt; i++){//CRTint M = p / P[i];
ret += A[i]* M % p *inv(M, P[i])% p;}return ret % p;}
莫比乌斯反演
数论分块
用于求解 i≥1∑⌊in⌋。
记 j=⌊⌊in⌋n⌋。
则 ∀k∈[i,j],有 ⌊kn⌋=⌊in⌋。
所以可以把 [i,j] 看成一个块,他们 ⌊kn⌋ 的值相同。
for(int i =1, j; i <= k; i = j +1){
j =min(k /(k / i), n);//一定要和n取min
ans += k / i;}
//递归版本voidDFT(comp *f,int n){if(n ==1)return;for(int i =0; i < n; i++) tmp[i]= f[i];for(int i =0; i < n; i++){if(i &1) f[(n >>1)+(i >>1)]= tmp[i];else f[i >>1]= tmp[i];}
comp *p = f,*q = f +(n >>1);DFT(p, n >>1),DFT(q, n >>1);
comp w =comp(1,0), step =exp(I *(2* PI / n));for(int i =0; i < n >>1; i++, w *= step){
tmp[i]= p[i]+ w * q[i];
tmp[i +(n >>1)]= p[i]- w * q[i];}for(int i =0; i < n; i++) f[i]= tmp[i];}
for(len =1, l =0; len <= n + m; len <<=1,++l);、
//注意这个位置len大于两个相乘的多项式长度之和//len为上述的n//(1<<l)=len,l为len二进制下的长度for(int i =0; i < len; i++) rev[i]=(rev[i >>1]>>1)|((i &1)<<(l -1));//求rev[]对于一个len可以只做一次for(int i =0; i < len; i++)if(i < rev[i])swap(f[i], f[rev[i]]);//保证只翻转一次,每次做DFT或IDFT都要做一次
由Euler定理有:e(x−k)=ex−2πki=cos(x2πk)−i⋅sin(x2πk),所以就是修改 sin 前的正负号即可。
完整版FFT
voidfft(comp *f,int fg){//fg=1为DFT,fg=-1为IDFT//蝴蝶变换只需要在主函数执行fft之前对长度len做一次就行了for(int i =0; i < len; i++)if(i < rev[i])swap(f[i], f[rev[i]]);for(int i =2; i <= len; i <<=1){//i为当前多项式长度
comp wn(cos(2* PI / i),sin(2* fg * PI / i));//步长for(int j =0; j < len; j += i){//j为当前多项式起始点
comp w(1,0);//单位//k枚举一半当前多项式长度,即可求出当前多项式对应的函数值for(int k = j; k < j +(i >>1); k++, w = w * wn){
comp p = f[k], q = w * f[k +(i >>1)];
f[k]= p + q;
f[k +(i >>1)]= p - q;}}}if(fg ==-1){for(int i =0; i < len; i++){
f[i].x /= len;//如果是IDFT还要都除总长}}}
voidntt(int*f,int fg){for(int i =0; i < n; i++)if(i < rev[i])swp(f[i], f[rev[i]]);for(int i =2; i <= n; i <<=1){int wn =ksm(3,(MOD -1)/ i, MOD);if(fg ==-1) wn =ksm(wn, MOD -2, MOD);//如果求IDFT就求wn的逆for(int j =0; j < n; j += i){int w =1;for(int k = j; k < j +(i >>1); k++,(w *= wn)%= MOD){int u = f[k], v =(w * f[k +(i >>1)])% MOD;
f[k]=(u + v)% MOD;
f[k +(i >>1)]=((u - v)% MOD + MOD)% MOD;}}}if(fg ==-1){int inv =ksm(n, MOD -2, MOD);for(int i =0; i < n; i++)(f[i]*= inv)%= MOD;}}
应用
卷积:ck=i+j=k∑aibj=i=0∑kaibk−i
回文子序列(只有两种字符a和b)P4199 万径人踪灭:构建两个多项式 f 和 g ,令 f 所有原串中a的位置系数为1,b的位置系数为0。g 反之。然后 f 自乘,i 位置的结果就是以 2i 为对称中心,两个a的字符对称的组数两倍。g 同理。然后把 f 和 g 对应的每一位都加起来再减去((i&1)^1)(对称中心在某个字符上),求2次幂再减1。