zwq的模板

为了使zwq的编码习惯更规范方便与不同模板之间的配合特此开始这一项宏大的工程把各种模板综合起来并使用统一的变量名未来将会做很多修改可能比较混乱。每份代码都是笔者手敲的。目录一.代码模板0.O30.freopen0.快读二.数学和组合计数1.快速幂2.预处理fac和inv3.定义求组合数4.杨辉三角预处理组合数5.Lucas定理6.gcd和lcm7.自己实现的popcount8.lowbit9.线性筛素数10.埃氏筛11.拉格朗日插值法三.图论相关1.并查集2.Kruscal3.Prim4.Floyd5.Dijkstra6.SPFA7.ST表求LCA8.树剖求LCA9.拓扑排序四.数据结构Data Structure,DS五.字符串相关1.字符串双hash2.Trie六.杂项和基础算法1.离散化2.二分答案一.代码模板#include bits/stdc.h #define ll long long #define db(x) do{ cerrx ; }while(0) // #define linux using namespace std; #ifdef linux #define getchar getchar_unlocked #endif inline ll read(){ ll x0;int f1; char cgetchar(); while(c0||c9){ if(c-) f-1; cgetchar(); } while(c0c9){ xx*10c-0; cgetchar(); } return x*f; } void fre(){ freopen(a.in,r,stdin); freopen(a.out,w,stdout); } signed main(){ // fre(); return 0; }0.O3#pragma GCC optimize(O3) #pragma GCC optimize(Ofast) #pragma GCC target(avx,avx2,fma)0.freopenvoid fre(){ freopen(a.in,r,stdin); freopen(a.out,w,stdout); }0.快读// #define linux #ifdef linux #define getchar getchar_unlocked #endif inline ll read(){ ll x0;int f1; char cgetchar(); while(c0||c9){ if(c-) f-1; cgetchar(); } while(c0c9){ xx*10c-0; cgetchar(); } return x*f; }二.数学和组合计数1.快速幂ll ksm(ll a,int b){ ll ans1; while(b){ if(b1) (ansans*a)%mod; (a*a)%mod; b1; } return ans%mod; }2.预处理fac和invvoid init(){ fac[0]1; for(int i1;iN-1;i) fac[i](fac[i-1]*i)%mod; inv[N-1]ksm(fac[N-1],mod-2); for(int iN-2;i0;i--) inv[i](inv[i1]*(i1))%mod; }3.定义求组合数ll C(int n,int m){ if(nm||n0||m0) return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; }4.杨辉三角预处理组合数void init(){ for(int i0;in;i) C[i][i]C[i][0]1; for(int i0;in;i) for(int j1;jn;j) C[i][j](C[i-1][j-1]C[i-1][j])%mod; }5.Lucas定理ll lucas(int n,int m){ if(m0) return 1; if(nm) return 0; return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod; }6.gcd和lcmll gcd(ll a,ll b){ return b0?a:gcd(b,a%b); } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }7.自己实现的popcountint lowbit(int x){ return x(-x); } int popcount(int x){ int cnt0; while(x){ cnt; x-lowbit(x); } return cnt; }8.lowbitint lowbit(int x){ return x(-x); }9.线性筛素数vector int prime; bool is[N]; void Prime(){ prime.push_back(0); memset(is,1,sizeof(is)); is[1]0; for(int i2;in;i){ if(is[i]) prime.push_back(i); for(int j1;jprime.size()-1i*prime[j]n;j){ is[i*prime[j]]0; if(i%prime[j]0) break; } } }10.埃氏筛你都会线性筛了学埃氏筛干嘛11.拉格朗日插值法int x[2010],y[2010]; ll sum0; for(int i1;in;i){ ll fzy[i]%mod,fm1; for(int j1;jn;j){ if(ij) continue; fzfz*(k-x[j])%mod; fmfm*(x[i]-x[j])%mod; } sum(sumfz*inv(fm)%modmod)%mod; }三.图论相关1.并查集for(int i0;in;i) fa[i]i; int getfa(int x){ return fa[x]x?x:fa[x]getfa(fa[x]); } void merge(int x,int y){ int xxgetfa(x),yygetfa(y); if(xxyy) return ; fa[xx]yy; }2.Kruscalstruct node{ int x; int y; int v; }a[200010]; int fa[N]; int getf(int x){return fa[x]x?x:fa[x]getf(fa[x]); } bool mycmp(node x,node y){ return x.vy.v; } int Kruskal(){ sort(a1,ak1,mycmp); for(int i1;in;i) fa[i]i; int ans0,cnt0; for(int i1;ik;i){ int xa[i].x,ya[i].y,va[i].v; xgetf(x),ygetf(y); if(xy) continue; fa[x]y; ansv; cnt; if(cntn-1) break; } if(cnt!n-1) exit(0); return ans; }3.Prim我不会4.Floydint f[985][985]; memset(f,0x3f,sizeof(f)); for(int i1;in;i) f[i][i]0; for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) f[i][j]min(f[i][j],f[i][k]f[k][j]);5.Dijkstraint dis[N]; bool vis[N]; vector pair int , int son[N]; void Dijkstra(){ memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); priority_queue pair int , int qu; dis[1]0; qu.push({0,1}); while(qu.size()){ int xqu.top().second; qu.pop(); if(vis[x]) continue; vis[x]1; for(auto zzz:son[x]){ int yzzz.first,wzzz.second; if(dis[y]dis[x]w){ dis[y]dis[x]w; qu.push({-dis[y],y}); } } } }6.SPFAint cnt[5010],dis[5010]; bool vis[5010]; vectorpairint ,int son[5010]; void SPFA(){ memset(dis,0x3f,sizeof(dis)); queue int q; q.push(0); dis[0]0,vis[0]1,cnt[0]; while(q.size()){ int xq.front(); q.pop(); vis[x]0; for(auto zzz:son[x]){ int yzzz.first; int wzzz.second; if(dis[y]dis[x]w){ dis[y]dis[x]w; if(!vis[y]){ vis[y]1,cnt[y]; q.push(y); if(cnt[y]n1){ coutNO; exit(0); } } } } } }7.ST表求LCAint s,dep[N],f[N][25]; vector int son[N]; void dfs(int x,int fa){ dep[x]dep[fa]1; f[x][0]fa; for(auto y:son[x]){ if(yfa) continue; dfs(y,x); } } int lca(int x,int y){ if(dep[y]dep[x]) swap(x,y); for(int i23;i0;i--) if(dep[f[y][i]]dep[x]) yf[y][i]; if(xy) return x; for(int i23;i0;i--) if(f[x][i]!f[y][i]) xf[x][i],yf[y][i]; return f[x][0]; } dfs(s,0); for(int j1;j23;j) for(int i1;in;i) f[i][j]f[f[i][j-1]][j-1];8.树剖求LCA我还不会9.拓扑排序int n,boat_du[N]; vector int son[N]; void Topsort(){ queue int qu; for(int i1;in;i) if(!boat_du[i]) qu.push(i); while(qu.size()){ int xqu.front(); qu.pop(); for(auto y:son[x]) if((--boat_du[y])0) qu.push(y); } } boat_du[x];四.数据结构Data Structure,DS五.字符串相关1.字符串双hashconst int mod119491001; const int mod2998244353; const int pp1131; const int pp213331; void init(){ p1[0]1; for(int i1;in;i){ p1[i]p1[i-1]*pp1; p1[i]%mod1; } for(int i1;in;i){ h1[i]h1[i-1]*pp1(s[i]-a); h1[i]%mod1; } p2[0]1; for(int i1;in;i){ p2[i]p2[i-1]*pp2; p2[i]%mod2; } for(int i1;in;i){ h2[i]h2[i-1]*pp2(s[i]-a); h2[i]%mod2; } } pairll,ll get(int x,int y){ int ans1(h1[y]-(h1[x-1]*p1[y-x1])%mod1mod1)%mod1; int ans2(h2[y]-(h2[x-1]*p2[y-x1])%mod2mod2)%mod2; return {ans1,ans2}; } for(int len1;lenn;len){ for(int i1;i2*len-1n;i){ auto hs1get(i,ilen-1); auto hs2get(ilen,i2*len-1); } }2.Trieint len,idx,cnt[N],tr[N][70]; ll getid(char c){ if(cAcZ) return c-A; else if(cacz) return c-a26; else return c-052; } void add(string s){ lens.size(); s s; int p0; for(int i1;ilen;i){ int idgetid(s[i]); if(!tr[p][id]) tr[p][id]idx; ptr[p][id]; cnt[p]; } } ll ask(string s){ lens.size(); s s; int p0; for(int i1;ilen;i){ int idgetid(s[i]); if(!tr[p][id]) return 0; ptr[p][id]; } return cnt[p]; }六.杂项和基础算法1.离散化for(int i1;in;i) a[i]read(),b[i]a[i]; sort(a1,an1); int cntunique(a1,an1)-a-1; for(int i1;in;i) b[i]lower_bound(a1,acnt1,b[i])-a;2.二分答案//最小 while(l1r){ int mid(lr)1; if(check(mid)) rmid,ansr; else lmid1; } if(check(l)); if(check(r)); //最大 while(l1r){ int mid(lr)1; if(check(mid)) rmid-1,ansr; else lmid; } if(check(r)); if(check(l));