Template
快读
CODE
struct FastIO{//不可与scanf,printf,getchar,putchar,gets,puts,cin,cout混用
private:
static const int BUFSIZE=1e5;
char buf[BUFSIZE];int pos,len;//读入buffer(缓冲器)以及读入指针
int wpos;char wbuf[BUFSIZE];//输出指针以及输出buffer
#define gc() (pos==len&&(len=(pos=0)+fread(buf,1,BUFSIZE,stdin),!len)?EOF:buf[pos++])
#define pc(c) (wpos==BUFSIZE?fwrite(wbuf,1,BUFSIZE,stdout),wpos=0,wbuf[wpos++]=c:wbuf[wpos++]=c)
public:
FastIO():wpos(0),pos(0),len(0){}
~FastIO(){if(wpos)fwrite(wbuf,1,wpos,stdout),wpos=0;}
inline char getc(){return gc();}//读取char
inline void putc(char c){pc(c);}//输出字符
inline long long rd(){//读取long long
long long x=0;char c=gc();bool f=0;
for(;c<'0'||c>'9';c=gc())f|=c=='-';
for(;c>='0'&&c<='9';c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?-x:x;
}
templateinline bool read(T &x){//多测读整数while(io.read(n))work();本地测试请输入两次ctrl Z
x=0;char c=gc();bool f=0;
for(;c<'0'||c>'9';c=gc()){if(c==EOF)return false;f|=c=='-';}
for(;c>='0'&&c<='9';c=gc())x=(x<<3)+(x<<1)+(c^48);
if(f)x=-x;return true;
}
inline void wt(long long x){//输出整数
if(x<0)pc('-'),x=-x;
char a[20];short int h=0;
for(a[++h]='0'+x%10,x/=10;x;x/=10)a[++h]='0'+x%10;
for(;h;)pc(a[h--]);
}
inline void wtl(long long x){wt(x);pc('\n');}//write line输出整数并换行
inline void wtb(long long x){wt(x);pc(' ');}//write blank输出整数并空格
inline int gets(char s[]){int l=0;char c=gc();for(;c<=' ';c=gc());for(;c>' ';c=gc())s[l++]=c;s[l]=0;return l;}
inline void puts(const char *s){for(const char *p=s;*p;)pc(*p++);}//输出字符串 (不带换行)
templateinline FastIO & operator >> (T &a){return read(a),*this;}//io>>a>>b;只能输入整数
inline FastIO & operator << (long long a){return wtb(a),*this;}//io< modint
CODE
const int MOD = 998244353;
inline int mod(int x) {return x >= MOD ? x - MOD : x;}
inline int ksm(int a, int b) {
int ret = 1; a = mod(a);
for(; b; b >>= 1, a = 1LL * a * a % MOD) if(b & 1) ret = 1LL * ret * a % MOD;
return ret;
}
template
struct modint {
int x;
modint() {x = 0; }
modint(int y) {x = y;}
inline modint inv() const { return modint{ksm(x, MOD - 2)}; }
explicit inline operator int() { return x; }
friend inline modint operator + (const modint &a, const modint& b) { return modint(mod(a.x + b.x)); }
friend inline modint operator - (const modint &a, const modint& b) { return modint(mod(a.x - b.x + MOD)); }
friend inline modint operator * (const modint &a, const modint& b) { return modint(1ll * a.x * b.x % MOD); }
friend inline modint operator / (const modint &a, const modint& b) { return modint(1ll * a.x * b.inv().x % MOD); }
friend inline modint operator - (const modint &a) { return modint(mod(MOD - a.x)); }
friend inline modint& operator += (modint &a, const modint& b) { return a = a + b; }
friend inline modint& operator -= (modint &a, const modint& b) { return a = a - b; }
friend inline modint& operator *= (modint &a, const modint& b) { return a = a * b; }
friend inline modint& operator /= (modint &a, const modint& b) { return a = a / b; }
friend auto &operator >> (istream &i, modint &a) {return i >> a.x; }
friend auto &operator << (ostream &o, const modint &z) { return o << z.x; }
inline bool operator == (const modint &b) { return x == b.x; }
inline bool operator != (const modint &b) { return x != b.x; }
inline bool operator < (const modint &a) { return x < a.x; }
inline bool operator <= (const modint &a) { return x <= a.x; }
inline bool operator > (const modint &a) { return x > a.x; }
inline bool operator >= (const modint &a) { return x >= a.x; }
};
typedef modint mint;
inline mint ksm(mint a, int b) {
mint ret = 1;
for(; b; b >>= 1, a = a * a ) if(b & 1) ret = ret * a ;
return ret;
}
const int N = 2e5 + 10;
mint fact[N + 1], infact[N + 1], inv[N + 1];
void init() {
fact[0] = 1; for(int i = 1; i <= N; ++ i ) { fact[i] = fact[i - 1] * i; }
infact[N] = ksm(fact[N], MOD - 2); for(int i = N - 1; i >= 0; -- i ) infact[i] = infact[i + 1] * (i + 1);
inv[0] = inv[1] = 1; for(int i = 2; i <= N; ++ i) inv[i] = inv[MOD % i] * (MOD - MOD / i);
}
封装线段树
CODE
int a[100010];
struct segment_tree {
struct tree {int tl, tr, val, tag;} t[M << 2];
#define l(x) t[(x)].tl
#define r(x) t[(x)].tr
#define len(x) (r(x) - l(x) + 1)
#define val(x) t[(x)].val
#define tag(x) t[(x)].tag
#define lson k << 1
#define rson k << 1 | 1
void pushup(int k)
{val(k)=val(lson)+val(rson);}
void pushdown(int k)
{val(lson) += tag(k) * len(lson), val(rson) += tag(k)*len(rson);
tag(lson) += tag(k), tag(rson) += tag(k); tag(k) = 0;}
void build(int k, int l, int r) {
l(k) = l, r(k) = r;
if(l == r) {val(k) = a[l]; return;}
int Mid = (l + r) >> 1;
build(lson,l,Mid);
build(rson, Mid + 1, r);
pushup(k);
}
void update(int k, int l, int r, int z) {
if(l(k) >= l && r(k) <= r) {val(k) += z*len(k), tag(k) += z; return;}
if(l(k) > r || r(k) < l)return;
pushdown(k);
update(lson, l, r, z); update(rson, l, r, z);
pushup(k);
}
int query(int k, int l, int r) {
if(l(k) >= l && r(k) <= r) return val(k);
if(l(k) > r || r(k) < l) return 0;
pushdown(k);
return query(lson, l, r) + query(rson, l, r);
}
}T;
\(unordered_map\) 的 \(hash\) 函数
- one
点击查看代码
struct splitmix64 {
size_t operator()(size_t x) const {
static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
x += 0x9e3779b97f4a7c15 + fixed;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
};
unordered_map mp;
- two
点击查看代码
struct Hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
Dijkstra
点击查看代码
struct node {
int ver; LL distance;
bool operator < (const node &T) const {
return T.distance < distance;
}
};
auto dijkstra = [&](vector s) {
priority_queue q;
vector st(n);
vector dist(n, inf);
for(auto &v: s) q.push({v, 0}), dist[v] = 0;
while(q.size()) {
auto t = q.top(); q.pop();
int ver = t.ver; LL d = t.distance;
if(st[ver]) continue;
st[ver] = true;
for(auto [v, w]: son[ver]) {
if(dist[v] > d + w) {
dist[v] = d + w;
q.push({v, dist[v]});
}
}
}
return dist;
};
trie 树
点击查看代码
// by 绒绒 http://oj.daimayuan.top/submission/135434
struct Trie {
int c[N][26], tot, v[N];
void init() {
while (tot) {
v[tot] = 0;
memset(c[tot], 0, sizeof(c[tot]));
--tot;
}
memset(c[0], 0, sizeof(c[0]));
v[0] = 0;
}
void insert(char s[], int len) {
int now = 0;
for (int i = 0; i < len; ++i) {
int to = s[i] - 'a';
if (!c[now][to])c[now][to] = ++tot;
now = c[now][to];
}
v[now] = 1;
}
bool query(char s[], int len) {
int now = 0;
for (int i = len - 1; ~i; --i) {
int to = s[i] - 'a';
if (!c[now][to])return 0;
now = c[now][to];
}
return v[now];
}
}A;
01 trie
点击查看代码
// by 严格鸽 https://www.zhihu.com/people/yan-ge-ge-32-1
void init()
{
nxt[0][0] = nxt[0][1] = 0;
cnt = 1;
}
void add(int n)
{
int cur = 0;
for (int i = MAXBIT; i >= 0; --i)
{
int bit = (n >> i) & 1;
if (!nxt[cur][bit]) {
nxt[cnt][0] = nxt[cnt][1] = 0;
nxt[cur][bit] = cnt++;
}
cur = nxt[cur][bit];
}
val[cur] = n;
}