- 缺省源
\(85\)
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=x,##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) begin(a),end(a)
#define fi first
#define se second
typedef long long LL; typedef vector<int> Vi; typedef pair<int,int> Pii;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
template<typename T=int>T read() { T x; cin>>x; return x; }
signed main() {
#ifdef D
freopen("in","r",stdin); freopen("out","w",stdout);
#endif
ios::sync_with_stdio(0);cin.tie(0);
return 0;
}
数据结构
- 可持久化 \(01\)Trie
值域 \([0,2^{30})\)
struct {
int ind,rt[N],ch[N*31][2],siz[N*31];
void ins(int u,int v,int x) {
u = rt[u], v = rt[v] = ++ind;
rFor(i,29,0) {
bool y = x>>i&1;
ch[v][!y] = ch[u][!y], u = ch[u][y], v = ch[v][y] = ++ind,
siz[v] = siz[u] + 1;
}
}
int qry(int u,int v,int x) {
u = rt[u], v = rt[v];
int res = 0;
for(int i = 1<<29; i; i >>= 1) {
bool y = ~x&i;
if( siz[ch[u][y]] < siz[ch[v][y]] ) res |= i, u = ch[u][y], v = ch[v][y];
else u = ch[u][!y], v = ch[v][!y];
}
return res;
}
} ;
字符串
- SA
多测需要清空 h[n+1]
struct {
int sa[N],rk[N],id[N],buc[N],h[N];
void bld() {
int m = 130;
For(i,1,n) ++buc[rk[i]=s[i]]; For(i,1,m) buc[i] += buc[i-1];
rFor(i,n,1) sa[buc[rk[i]]--] = i;
for(int w = 1, p = 0; p < n; w <<= 1, m = p) {
p = 0; For(i,n-w+1,n) id[++p] = i;
For(i,1,n) if( sa[i] > w ) id[++p] = sa[i]-w;
memset(buc+1,0,sizeof(int)*m);
For(i,1,n) ++buc[rk[i]]; For(i,1,m) buc[i] += buc[i-1];
rFor(i,n,1) sa[buc[rk[id[i]]]--] = id[i];
p = 0, memcpy(h+1,rk+1,sizeof(int)*n);
auto cmp=[&](int i,int j) { return h[i]==h[j] && h[i+w]==h[j+w]; };
For(i,1,n) rk[sa[i]] = cmp(sa[i],sa[i-1]) ? p : ++p;
}
For(i,1,n, k = 0) {
int j = sa[rk[i]-1];
for(k -= !!k; s[i+k] == s[j+k]; ++k);
h[rk[i]] = k;
}
}
} ;
- SAM
struct {
int ind=1,lst=1,t[N][26],fa[N],len[N],cnt[N];
Vi e[N];
void extend(int x) {
int p = lst, np = lst = ++ind; len[np] = len[p]+1, cnt[np] = 1;
for(; p && !t[p][x]; p = fa[p]) t[p][x] = np;
if( !p ) fa[np] = 1;
else {
int q = t[p][x];
if( len[p]+1 == len[q] ) fa[np] = q;
else {
int nq = ++ind; len[nq] = len[p]+1;
memcpy(t[nq],t[q],sizeof(t[nq]));
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; p && t[p][x] == q; p = fa[p]) t[p][x] = nq;
}
}
}
} ;
图论
数学
- 线性建凸包
其他
- 取模
mint(int x) 要求 x < 2*mod
const int mod = 998244353;
struct mint {
int x; mint(int x=0):x(x<0?x+mod:x<mod?x:x-mod){}
mint(LL y) { y%=mod, x=y<0?y+mod:y; }
mint& operator += (const mint &y) { x=x+y.x<mod?x+y.x:x+y.x-mod; return *this; }
mint& operator -= (const mint &y) { x=x-y.x<0?x-y.x+mod:x-y.x; return *this; }
mint& operator *= (const mint &y) { x=1ll*x*y.x%mod; return *this; }
friend mint operator + (mint x,const mint &y) { return x+=y; }
friend mint operator - (mint x,const mint &y) { return x-=y; }
friend mint operator * (mint x,const mint &y) { return x*=y; }
}; mint Pow(mint x,LL y=mod-2) { mint z(1);for(;y;y>>=1,x*=x)if(y&1)z*=x;return z; }
- 快读
#define getchar() getchar_unlocked()
struct IO {
IO& operator >> (char &x) { while(isspace(x=getchar())); return *this; }
IO& operator >> (char *s) {
while(isspace(*s=getchar())); while(isgraph(*++s=getchar()));
return *s=0, *this;
}
template<typename T>IO& operator >> (T &x) {
x=0;bool f=0;char c;while(!isdigit(c=getchar()))f|=c=='-';
do x=x*10+c-48;while(isdigit(c=getchar()));if(f)x=-x;
return *this;
}
} io;
#define cin io
- 对拍
clear; g++ g.cpp -og -std=c++17 -O2
let i=0; while true; do
let i++; printf "#$i\n"
./g; ./a; ./a0
if ! diff out ans -bB; then break; fi
done