数据结构
树状数组
//单点修改+区间查询 或 区间修改+单点查询
struct bit {
int n;
vector<int> a;
bit(int _n) : n(_n) {
a.assign(n + 1, 0);
}
void ad(int p, int v) {
for (; p <= n; p += p & -p) {
a[p] += v;
}
}
int qr(int p) {
int sum = 0;
for (; p; p -= p & -p) {
sum += a[p];
}
return sum;
}
int sum(int l, int r) {
return qr(r) - qr(l - 1);
}
};
区间修改+区间查询
struct BIT {
int n;
vector<int> b1, b2;
BIT(int _n) {
n = _n;
b1.assign(n+1,0);
b2.assign(n+1,0);
}
inline int lowbit(int x) {
return x & -x;
}
void update(int p, int v) {
for (int i = p; i <= n; i += lowbit(i)) {
b1[i] += v;
b2[i] += p*v;
}
}
void update(int l, int r, int v) {
update(l,v);
update(r+1,-v);
}
int query(int p) {
int sum = 0;
for (int i = p; i; i -= lowbit(i)) {
sum += (p+1) * b1[i] - b2[i];
}
return sum;
}
int query(int l, int r) {
return query(r) - query(l-1);
}
};
并查集
struct DSU {
vector<int> f, sz;
DSU(int n) {
f.resize(n + 1);
iota(f.begin(), f.end(), 0);
sz.assign(n + 1, 1);
}
int find(int x) {
if (f[x] != x) {
f[x] = find(f[x]);
}
return f[x];
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
f[y] = x;
return true;
}
};
单调栈
//O(n) 求离 a[i] 最近的第一个 大于/小于(等于) a[i] 的下标
stack<int> stk;
a[0] = a[n + 1] = 1e9;
stk.push(0);
for (int i = 1; i <= n; i++) {
while (stk.size() && a[i] > a[stk.top()]) stk.pop();
L[i] = stk.top() + 1;
stk.push(i);
}
while (stk.size()) stk.pop();
stk.push(n + 1);
for (int i = n; i >= 1; i--) {
while (stk.size() && a[i] >= a[stk.top()]) stk.pop();
R[i] = stk.top() - 1;
stk.push(i);
}
单调队列
// 求区间长度为k的最大值
int L = 1, R = 0; // [L,R]
for (int i = 1; i <= n; i++) {
while (R - L + 1 >= 1 && a[i] < a[qmini[R]]) {
R--;
}
qmini[++R] = i;
if (i > k && i - k >= qmini[L]) {
L++;
}
if (i >= k) cout << a[qmini[L]] << " ";
}
ST表
int st[N][__lg(N) + 1];
int lg[N];
void solve() {
int n,m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> st[i][0];
}
lg[1] = 0;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
for (int j = 1; j <= lg[n]; j++) {
for (int i = 1; i+(1<<(j-1)) <= n; i++) {
st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--) {
int l, r;
cin >> l >> r;
int k = lg[r-l+1];
cout << max(st[l][k],st[r-(1<<k)+1][k]) << "\n";
}
}
线段树
struct tag {
tag() {}
void apply(tag& t) {
}
};
struct nd {
nd() {}
nd operator+ (const nd& b) const {
}
void apply(tag t) {
}
};
struct lazy {
int n;
vector<nd> a;
vector<tag> tg;
lazy(int _n, vector<nd>& b) : n(_n) {
a.assign(4 * n, nd());
tg.assign(4 * n, tag());
auto bd = [&](auto&& self, int p, int l, int r) -> void {
if (l == r) {
a[p] = b[l];
return;
}
int m = l + r >> 1;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
up(p);
};
bd(bd, 1, 1, n);
}
inline void up(int p) {
a[p] = a[p << 1] + a[p << 1 | 1];
}
void apply(int p, tag& t) {
a[p].apply(t);
tg[p].apply(t);
}
void down(int p) {
apply(p << 1, tg[p]);
apply(p << 1 | 1, tg[p]);
tg[p] = tag();
}
void modify(int p, int l, int r, int x, int y, tag& t) {
if (r < x || l > y) {
return;
}
if (l >= x && r <= y) {
apply(p, t);
return;
}
down(p);
int m = l + r >> 1;
modify(p << 1, l, m, x, y, t);
modify(p << 1 | 1, m + 1, r, x, y, t);
up(p);
}
nd qr(int p, int l, int r, int x, int y) {
if (r < x || l > y) {
return nd();
}
if (l >= x && r <= y) {
return a[p];
}
int m = l + r >> 1;
down(p);
return qr(p << 1, l, m, x, y) + qr(p << 1 | 1, m + 1, r, x, y);
}
};
仅单点修改
void modify(int x, nd& t) {
x = mp[x];
a[x] = t;
while(x/2) up(x);
}
线段树上二分
int qr_pos(int p, int l, int r, int x, int y, long long& k) { // 查询 [x,y] 区间前缀第一个大于等于k的位置
if (r < x || l > y) return -1;
if (l >= x && r <= y) {
if (a[p].sum < k) {
k -= a[p].sum;
return -1;
}
if (l == r) return l;
}
down(p);
int m = (l + r) >> 1;
int res = qr_pos(p << 1, l, m, x, y, k);
if (res != -1) return res;
return qr_pos(p << 1 | 1, m + 1, r, x, y, k);
}
可持久化
查询区间 [L,R] 中第k大的数
#include <bits/stdc++.h>
using namespace std;
struct PresidentTree
{
static constexpr int N = 2e5 + 10;
int cntNodes = 0, root[N]; // root[i] 表示前i个元素构成的版本
struct Node
{
int l = 0, r = 0; // 左右子节点编号（初始为0）
int cnt = 0; // 当前区间的元素个数
};
vector<Node> tr;
PresidentTree() { tr.resize(20 * N); }
// 构建初始空树
void build_empty(int &u, int l, int r)
{
u = ++cntNodes;
tr[u] = Node();
if (l == r)
return;
int mid = (l + r) >> 1;
build_empty(tr[u].l, l, mid);
build_empty(tr[u].r, mid + 1, r);
}
// 插入数值 x，返回新版本的根
void modify(int &u, int v, int l, int r, int x)
{
u = ++cntNodes;
tr[u] = tr[v];
tr[u].cnt++;
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
modify(tr[u].l, tr[v].l, l, mid, x);
else
modify(tr[u].r, tr[v].r, mid + 1, r, x);
}
// 查询第k小
int kth(int u, int v, int l, int r, int k)
{
if (l == r)
return l;
int left_cnt = tr[tr[v].l].cnt - tr[tr[u].l].cnt;
int mid = (l + r) >> 1;
if (k <= left_cnt)
return kth(tr[u].l, tr[v].l, l, mid, k);
else
return kth(tr[u].r, tr[v].r, mid + 1, r, k - left_cnt);
}
};
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b.begin() + 1, b.end());
auto ed = unique(b.begin() + 1, b.end());
int m = ed - (b.begin() + 1);
PresidentTree tree;
tree.build_empty(tree.root[0], 1, m); // 初始空树 root[0]
// 构建前缀版本：遍历 a[1..n]
for (int i = 1; i <= n; ++i) {
int x = lower_bound(b.begin() + 1, ed, a[i]) - (b.begin() + 1) + 1;
tree.modify(tree.root[i], tree.root[i - 1], 1, m, x);
}
while (q--) {
int l, r, k;
cin >> l >> r >> k;
int rank = tree.kth(tree.root[l - 1], tree.root[r], 1, m, k);
cout << b[rank] << "\n";
}
return 0;
}
重链剖分
树拆成多条重链，然后放到线段树上维护，可以lg^2解决一条路径的询问
重儿子：子树中size最大的儿子，每个节点只有一个重儿子，其余为轻儿子
重链：从一个节点开始依次访问重儿子
https://www.luogu.com.cn/problem/P3384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int N = 1e5 + 10;
int n, q, r, mod, id = 1, cnt = 0;
int head[N], v[N], to[2 * N], nx[2 * N], fa[N], dep[N], dfn[N], son[N], tp[N], sz[N], sz2[4*N];
void ad(int x, int y) {
to[id] = y;
nx[id] = head[x];
head[x] = id++;
}
void dfs1(int cur, int f) {
dep[cur] = dep[f] + 1;
fa[cur] = f;
sz[cur] = 1;
for (int i = head[cur]; i > 0; i = nx[i]) {
int u = to[i];
if (u == f) {
continue;
}
dfs1(u, cur);
if (sz[u] > sz[son[cur]]) {
son[cur] = u;
}
sz[cur] += sz[u];
}
}
void dfs2(int cur, int f) {
cnt++;
dfn[cur] = cnt;
tp[cur] = f;
if (son[cur] == 0) return;
dfs2(son[cur], f);
for (int i = head[cur]; i > 0; i = nx[i]) {
int u = to[i];
if (u == fa[cur] || u == son[cur]) {
continue;
}
dfs2(u, u);
}
}
int tree[4 * N], tag[4 * N];
void up(int p) {
tree[p] = (tree[p << 1] + tree[p << 1 | 1]) % mod;
}
void build(int p, int l, int r, vector<int>& b) {
if (l == r) {
tree[p] = b[l];
sz2[p] = 1;
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid, b);
build(p << 1 | 1, mid + 1, r, b);
up(p);
sz2[p] = r - l + 1;
}
void apply(int p, int v) {
tree[p] = (tree[p] + v*sz2[p] % mod) % mod;
tag[p] = (tag[p] + v) % mod;
}
void down(int p) {
apply(p << 1, tag[p]);
apply(p << 1 | 1, tag[p]);
tag[p] = 0;
}
void update(int ul, int ur, int v, int p, int l, int r) {
if (l > ur || r < ul) return;
if (l >= ul && r <= ur) {
apply(p, v);
return;
}
down(p);
int mid = l + r >> 1;
update(ul, ur, v, p << 1, l, mid);
update(ul, ur, v, p << 1 | 1, mid + 1, r);
up(p);
}
void update(int ul, int ur, int v) {
update(ul, ur, v, 1, 1, n);
}
int query(int ql, int qr, int p, int l, int r) {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) {
return tree[p] % mod;
}
down(p);
int mid = l + r >> 1;
return (query(ql, qr, p << 1, l, mid) + query(ql, qr, p << 1 | 1, mid + 1, r)) % mod;
}
int query(int ql, int qr) {
return query(ql, qr, 1, 1, n);
}
void add(int x, int y, int v) {
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) {
swap(x, y);
}
update(dfn[tp[x]],dfn[x],v);
x = fa[tp[x]];
}
if (dep[x] > dep[y]) {
swap(x,y);
}
update(dfn[x],dfn[y],v);
}
int sum(int x, int y) {
int res = 0;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) {
swap(x, y);
}
res = (res + query(dfn[tp[x]],dfn[x])) % mod;
x = fa[tp[x]];
}
if (dep[x] > dep[y]) {
swap(x,y);
}
res = (res + query(dfn[x],dfn[y])) % mod;
return res;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> q >> r >> mod;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
ad(u, v);
ad(v, u);
}
dfs1(r, 0);
dfs2(r, r);
for (int i = 1; i <= n; i++) {
b[dfn[i]] = a[i];
}
build(1,1,n,b);
int op, x, y, z;
while (q--) {
cin >> op;
if (op == 1) {
cin >> x >> y >> z;
add(x,y,z);
} else if (op == 2) {
cin >> x >> y;
cout << sum(x,y) << '\n';
} else if (op == 3) {
cin >> x >> z;
update(dfn[x], dfn[x] + sz[x] - 1, z);
} else {
cin >> x;
cout << query(dfn[x], dfn[x] + sz[x] - 1) << '\n';
}
}
return 0;
}
ODT 颜色段均摊
struct odt {
struct node {
int l, r;
mutable int v;
node(int _l, int _r = -1,int _v = 0):l(_l), r(_r),v(_v) {}
bool operator< (const node& b) const {
return l < b.l;
};
};
set<node> s;
odt() { s.clear(); }
auto split(int pos) {
auto it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
it--;
int l = it->l, r = it->r, v = it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
auto assign(int l, int r, int v) {
auto itr = split(r+1), itl = split(l);
s.erase(itl,itr);
s.insert(node(l,r,v));
}
void add(int l, int r, int x) {
auto itr = split(r+1), itl = split(l);
for (auto it = itl; it != itr; it++) {
it->v += x;
}
}
int kth(int l, int r,int k) {
auto itr = split(r+1), itl = split(l); // 不能交换顺序,如果先左后右左边的迭代器被删除会RE
vector<pair<int,int>> tmp;
for (auto it = itl; it != itr; it++) {
tmp.push_back({it->v,it->r - it->l+1});
}
sort(tmp.begin(),tmp.end());
for (auto i : tmp) {
k -= i.second;
if (k <= 0) {
return i.first;
}
}
}
int ksm(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b > 0) {
if (b&1) ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans;
}
int po(int l, int r, int x, int y) {
auto itr = split(r+1), itl = split(l);
int tot = 0;
for (auto it = itl; it != itr; it++) {
tot = (tot + ((it->r - it->l + 1) % y) * ksm(it->v,x,y)) % y;
}
return tot;
}
};
带修莫队
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int N = 1e6 + 10;
int n, q, sz, cc = 0, sum = 0;
struct nd {
int id, l, r, t;
} a[N];
pair<int,int> qr[N];
int cnt[N], ans[N], num[N];
bool cmp (const nd& a, const nd&b) {
if (a.l / sz != b.l / sz) return a.l / sz < b.l / sz;
if (a.r / sz != b.r / sz) return a.r / sz < b.r / sz;
return a.t < b.t;
}
void ad(int x) {
sum += (cnt[x] == 0);
cnt[x]++;
}
void del(int x) {
sum -= (cnt[x] == 1);
cnt[x]--;
}
void up(int x, int t) {
if (qr[t].first >= a[x].l && qr[t].first <= a[x].r) {
del(num[qr[t].first]);
ad(qr[t].second);
}
swap(num[qr[t].first],qr[t].second);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
sz = pow(n,0.666);
int len = 0;
for (int i = 1; i <= q; i++) {
char c;
int l, r;
cin >> c >> l >> r;
if (c == 'Q') {
len++;
a[len].id = len;
a[len].l = l, a[len].r = r;
a[len].t = cc;
} else {
cc++;
qr[cc].first = l, qr[cc].second = r;
}
}
sort(a+1,a+len+1,cmp);
int l = 1, r = 0, t = 0;
for (int i = 1; i <= len; i++) {
while (l < a[i].l) del(num[l++]);
while (l > a[i].l) ad(num[--l]);
while (r < a[i].r) ad(num[++r]);
while (r > a[i].r) del(num[r--]);
while (t < a[i].t) up(i,++t);
while (t > a[i].t) up(i,t--);
ans[a[i].id] = sum;
}
for (int i = 1; i <= len; i++) {
cout << ans[i] << '\n';
}
return 0;
}
二维树状数组 区间 + 单点
struct BIT {
int n, m;
vector<vector<int>> a;
BIT(int _n, int _m) {
n = _n, m = _m;
a.assign(n+1,vector<int>(m+1));
}
inline int lowbit(int x) {
return x & -x;
}
void update(int x, int y, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j+= lowbit(j)) {
a[i][j] += v;
}
}
}
void update(int x1, int y1, int x2, int y2, int v) {
update(x1,y1,v);
update(x1,y2+1,-v);
update(x2+1,y1,-v);
update(x2+1,y2+1,v);
}
int query(int x, int y) {
int sum = 0;
for (int i = x; i; i -= lowbit(i)) {
for (int j = y; j; j -= lowbit(j)) {
sum += a[i][j];
}
}
return sum;
}
int query(int x1, int y1, int x2, int y2) {
return query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1);
}
};
二维树状数组区间修改+区间查询
struct BIT {
int n, m;
vector<vector<int>> b[4];
BIT(int _n, int _m) {
n = _n, m = _m;
for (int i = 0; i < 4; i++) {
b[i].assign(n + 1, vector<int>(m + 1));
}
}
inline int lowbit(int x) {
return x & -x;
}
void update(int x, int y, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
b[0][i][j] += v;
b[1][i][j] += x * v;
b[2][i][j] += y * v;
b[3][i][j] += x * y * v;
}
}
}
void update(int x1, int y1, int x2, int y2, int v) {
update(x1, y1, v);
update(x1, y2 + 1, -v);
update(x2 + 1, y1, -v);
update(x2 + 1, y2 + 1, v);
}
int query(int x, int y) {
int sum = 0;
for (int i = x; i; i -= lowbit(i)) {
for (int j = y; j; j -= lowbit(j)) {
sum += (x + 1) * (y + 1) * b[0][i][j];
sum -= (x + 1) * b[2][i][j];
sum -= (y + 1) * b[1][i][j];
sum += b[3][i][j];
}
}
return sum;
}
int query(int x1, int y1, int x2, int y2) {
return query(x2, y2) + query(x1 - 1, y1 - 1) - query(x1 - 1, y2) - query(x2, y1 - 1);
}
};
数论
GCD
int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
int lcm(int a,int b) {
return a / gcd(a, b) * b;
}
筛
埃氏筛
ll countPrimes(ll n) {
bool vis[n + 1];
for (int i = 0; i <= n; i++) vis[i] = false;
for (ll i = 2; i <= n; i++) {
if (!vis[i]) {
for (ll j = i * i; j <= n; j += i) {
vis[j] = true;
}
}
}
ll cnt = 0;
for (ll i = 2; i <= n; i++) {
if (!vis[i]) {
cnt++;
}
}
return cnt;
}
int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
欧拉筛
vector<int> pri;
vector<bool> not_prime(N,false);
void pre(int n) {
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
}
for (int j : pri) {
if (i * j > n) break;
not_prime[i * j] = true; // i*j 以 j 为最小因子被筛除
if (i % j == 0) break; // 这样以后的数必然能被j筛除，以后再筛
}
}
}
快速幂
const int mod = 1e9 + 10;
int ksm(int a,int b) {
int ans = 1;
while (b > 0) {
if (b & 1) {
ans = ans * a % mod;
}
a = a*a%mod;
b >>= 1;
}
return ans;
}
int inv(int x) {
return ksm(x,mod-2);
}
组合数
卢卡斯定理：
const int N = 100000;
int fac[N + 5], inv[N + 5]; // 阶乘和阶乘的逆元
// 计算 a 的 b 次方模 mod
int mod = 1e9 + 7;
int ksm(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
// 预处理前n阶乘和阶乘逆元
void pre(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = (fac[i - 1] * i) % mod;
}
inv[n] = ksm(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
inv[i] = (inv[i + 1] * (i + 1)) % mod;
}
}
int C(int n, int m) {
if (m > n) return 0; // 不合法情况
return (fac[n] * inv[m] % mod * inv[n - m] % mod);
}
int Lucas(int n, int m) {
if (m == 0) return 1;
return (C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod);
}
矩阵运算，逆矩阵，矩阵快速幂
const int sz = 2;
struct Mat {
ll M[sz + 5][sz + 5];
void clear() { memset(M, 0, sizeof(M)); }
void reset() { // 初始化
clear();
for (int i = 1; i <= sz; ++i) M[i][i] = 1;
}
Mat friend operator*(const Mat &A, const Mat &B) {
Mat Ans;
Ans.clear();
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j)
for (int k = 1; k <= sz; ++k)
Ans.M[i][j] = (Ans.M[i][j] + A.M[i][k] * B.M[k][j]) % mod;
return Ans;
}
Mat friend operator+(const Mat &A, const Mat &B) {
Mat Ans;
Ans.clear();
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j)
Ans.M[i][j] = (A.M[i][j] + B.M[i][j]) % mod;
return Ans;
}
};
inline int mypow(ll n, ll k, int p = mod) {
ll r = 1;
for (; k; k >>= 1, n = n * n % p) {
if (k & 1) r = r * n % p;
}
return r;
}
inline Mat mypow(Mat n, ll k) {
Mat r;
r.reset();
for (; k; k >>= 1, n = n * n) {
if (k & 1) r = r * n;
}
return r;
}
bool ok = 1;
Mat getinv(Mat a) { // 矩阵求逆
int n = sz, m = sz * 2;
for (int i = 1; i <= n; i++) a.M[i][i + n] = 1;
for (int i = 1; i <= n; i++) {
int pos = i;
for (int j = i + 1; j <= n; j++)
if (abs(a.M[j][i]) > abs(a.M[pos][i])) pos = j;
if (i != pos) swap(a.M[i], a.M[pos]);
if (!a.M[i][i]) {
puts("No Solution");
ok = 0;
}
ll inv = mypow(a.M[i][i], mod - 2);
for (int j = 1; j <= n; j++)
if (j != i) {
ll mul = a.M[j][i] * inv % mod;
for (int k = i; k <= m; k++)
a.M[j][k] = ((a.M[j][k] - a.M[i][k] * mul) % mod + mod) % mod;
}
for (int j = 1; j <= m; j++) a.M[i][j] = a.M[i][j] * inv % mod;
}
Mat res;
res.clear();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
res.M[i][j] = a.M[i][n + j];
return res;
}
字符串
字符串哈希
base 进制下
$s[1] * base^{n-1} … s[n-1] * base ^ {1} + s[n] * base ^ {0}$
常用base: 31, 131, 13331
质数: 999999929, 999999937
记得开双模, 单模和自然溢出容易被卡
/* 1-index */
const int mod = 999999937;
const int base = 131;
ll ha[n+1];
ll p[n+1];
p[0] = 1, ha[0] = 0;
for(int i = 1; i <= len; i++) {
p[i] = p[i-1]*base;
ha[i] = ha[i-1]*base + s[i];
}
auto cal = [&] (int l, int r) -> int {
return (ha[r] - ha[l-1] * p[r-l+1] % mod + mod) % mod;
}
双模
static mt19937_64 rng(random_device{}());
int rd(int l, int r) {
return rng() % (r - l + 1) + l;
}
const int mod1 = rd((int)1e9,(int)2e9), mod2 = rd((int)1e9,(int)2e9);
struct Hash {
int b1 = 17, b2 = 233, n;
vector<int> f1, f2, B1, B2;
Hash() {}
Hash(string s) : n(s.length()), f1(n + 1), f2(n + 1), B1(n + 1), B2(n + 1) {
B1[0] = B2[0] = 1;
for (int i = 1; i <= n; i++) {
B1[i] = B1[i - 1] * b1 % mod1;
B2[i] = B2[i - 1] * b2 % mod2;
f1[i] = (f1[i - 1] * b1 + s[i - 1]) % mod1;
f2[i] = (f2[i - 1] * b2 + s[i - 1]) % mod2;
}
}
pair<int, int> get(int l, int r) {
int a1 = ((f1[r] - f1[l - 1] * B1[r - l + 1]) % mod1 + mod1) % mod1;
int a2 = ((f2[r] - f2[l - 1] * B2[r - l + 1]) % mod2 + mod2) % mod2;
return {a1, a2};
}
};
KMP
nxt[i] 表示 pre[i] 的最长非平凡border长度
失配后利用
s 的 border的border仍是 s 的border性质
加速匹配
string s1, s2;
cin >> s1 >> s2;
int n = s1.size(), m = s2.size();
s1 = '.' + s1, s2 = '.' + s2;
vector<int> nxt(m + 1);
nxt[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
j = nxt[i - 1];
while (j && s2[j + 1] != s2[i]) {
j = nxt[j];
}
if (s2[i] == s2[j + 1]) j++;
nxt[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j && s1[i] != s2[j + 1]) {
j = nxt[j];
}
if (s1[i] == s2[j + 1]) j++;
if (j == m) {
cout << i - m + 1 << '\n';
j = nxt[j];
}
}
扩展KMP
vector<int> zf(string& c) {
int len = c.size();
vector<int> nxt(len);
int p = 0, k = 1, l; //我们会在后面先逐位比较出 nxt[1] 的值，这里先设 k 为 1
//如果 k = 0，p 就会锁定在 |c| 不会被更改，无法达成算法优化的效果啦
nxt[0] = len; //以 c[0] 开始的后缀就是 c 本身，最长公共前缀自然为 |c|
while(p + 1 < len && c[p] == c[p + 1]) p++;
nxt[1] = p; //先逐位比较出 nxt[1] 的值
for(int i = 2; i < len; i++) {
p = k + nxt[k] - 1; //定义
l = nxt[i - k]; //定义
if(i + l <= p) nxt[i] = l; //如果灰方框小于初始的绿方框,直接确定 nxt[i] 的值
else {
int j = max(0LL, p - i + 1);
while(i + j < len && c[i + j] == c[j]) j++; //否则进行逐位比较
nxt[i] = j;
k = i; //此时的 x + nxt[x] - 1 一定刷新了最大值，于是我们要重新赋值 k
}
}
return nxt;
}
vector<int> zf(string& a, string& b, vector<int>& nxt) {
int la = a.size(), lb = b.size();
vector<int> ext(la);
int p = 0, k = 0, l;
while(p < la && p < lb && a[p] == b[p]) p++; //先算出初值用于递推
ext[0] = p;
for(int i = 1; i < la; i++) {
p = k + ext[k] - 1;
l = nxt[i - k];
if(i + l <= p) ext[i] = l;
else
{
int j = max(0LL, p - i + 1);
while(i + j < la && j < lb && a[i + j] == b[j]) j++;
ext[i] = j;
k = i;
}
}
return ext;
}
Manacher
p[i] 是包括了中心的回文半径
p[i] - 1 才是以回文长度
string s;
cin >> s;
int n = s.size();
string t = "-#";
for (int i = 0; i < n; i++) {
t += s[i];
t += '#';
}
int m = t.size();
t += '+';
int mid = 0, r = 0;
vector<int> p(m);
int ans = 0;
for (int i = 1; i < m; i++) {
p[i] = i < r ? min(p[2 * mid - i], r - i) : 1;
while (t[i - p[i]] == t[i + p[i]]) p[i]++;
if (i + p[i] > r) {
r = i + p[i];
mid = i;
}
}
trie
struct trie {
int n, cnt;
vector<vector<int>> nex;
vector<bool> f;
trie(int _n) : cnt(0), n(_n) {
nex.assign(n+1,vector<int>(26,0));
f.assign(n+1,0);
}
void insert(string& s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++cnt;
p = nex[p][c];
}
f[p] = true;
}
bool find(string& s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!nex[p][c]) return 0;
p = nex[p][c];
}
return f[p];
}
};
可持久化 0-1 trie
char op;
const int N = 6e5 + 10;
int val[N * 30];
int nx[N * 30][2];
int cnt = 0;
int rt[N], a[N];
void ins(int p, int lst, int v) {
for (int i = 30; i >= 0; i--) {
bool c = ((1 << i) & v);
if (!nx[p][c]) nx[p][c] = ++cnt;
nx[p][!c] = nx[lst][!c];
p = nx[p][c];
lst = nx[lst][c];
val[p] = val[lst] + 1;
}
}
int qr(int l, int r, int v) {
int ans = 0;
for (int i = 30; i >= 0; i--) {
bool c = (1 << i) & v;
if (val[nx[r][!c]] - val[nx[l][!c]]) {
ans |= 1 << i;
l = nx[l][!c], r = nx[r][!c];
}
else {
l = nx[l][c], r = nx[r][c];
}
}
return ans;
};
cnt = 0
for (int i = 0; i <= cnt; i++) {
val[i] = 0;
nx[i][0] = nx[i][1] = 0;
}
AC 自动机
struct AC {
int c[N][26];
int fail[N];
int val[N];
int id = 1;
void insert(string& s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
if (!c[p][s[i]-'a']) c[p][s[i]-'a']=id++;
p = c[p][s[i]-'a'];
}
val[p]++;
}
void build() {
queue<int> q;
for(int i=0;i<26;i++) {
if (c[0][i]) {
fail[c[0][i]]=0,q.push(c[0][i]);
}
}
while(!q.empty()) {
int cur=q.front();
q.pop();
for(int i=0;i<26;i++) {
if(c[cur][i]) {
fail[c[cur][i]]=c[fail[cur]][i],q.push(c[cur][i]);
} else {
c[cur][i]=c[fail[cur]][i]; // 虚 fail指针
}
}
}
}
int query(string& s){
int p=0,ans=0;
for(int i=0; i < s.size(); i++){
p=c[p][s[i]-'a'];
for(int t=p; t && ~val[t];t = fail[t]) {
ans+=val[t],val[t]=-1;
}
}
return ans;
}
};
图论
建图
邻接表
const int N = 2e5+10;
vector<vector<pair<int,int>>> G[N];
void addedge(int x,int y,int v) {
G[x].push_back(make_pair(y,v));
G[y].push_back(make_pair(x,v));
}
for(auto& i : adj[x]) {
}
前向星
vector<int> head(n+1), nx(m+1), to(m+1);
int id = 1;
auto ad = [&] (int x, int y) {
to[id] = y;
nx[id] = head[x];
head[x] = id++;
};
for(int i = head[x]; i > 0; i = nx[i]) {
}
拓扑排序
DAG 一定有
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) {
q.push(i);
}
}
while (q.size()) {
int t = q.front();
q.pop();
cout << t << " ";
for (int i = head[t]; i > 0; i = nx[i]) {
int tt = to[i];
if (--deg[tt] == 0) {
q.push(tt);
}
}
}
Dijstra
#include <bits/stdc++.h>
using namespace std;
const long long inf = 2147483647;
struct edge {
int to, next, w;
} e[1001000];
int cnt = 0;
int head[1001000];
void addedge(int x, int y, int v) {
e[++cnt].next = head[x];
e[cnt].to = y;
e[cnt].w = v;
head[x] = cnt;
}
struct Node {
int dis;
int id;
bool operator <(const Node& b)const { //重载比较运算符，可以直接放进优先队列
return dis > b.dis;
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);//数据多加快读
int n, m, s; // 三个整数n,m,s分别表示点的个数、有向边的个数、出发点的编号
cin >> n >> m >> s;
long long dist[n + 1];
bool vis[n + 1];
for (int i = 1; i <= n; i++) {
dist[i] = inf;
vis[i] = false;
}
dist[s] = 0;
/*使用前向星*/
for (int i = 1; i <= m; i++) {
int begin, end, v;
cin >> begin >> end >> v;
addedge(begin, end, v);
}
priority_queue<Node> q;
q.push((Node) {0,s});
while (!q.empty()) {
Node temp = q.top();
q.pop();
if(vis[temp.id]) continue;
vis[temp.id] = true;
int cur = temp.id;
for (int j = head[cur]; j != 0; j = e[j].next) {
int to = e[j].to;
if (!vis[to] && dist[cur] + e[j].w < dist[to]) {
dist[to] = dist[cur] + e[j].w;
q.push((Node){dist[to],to});
}
}
}
for (int i = 1; i <= n; i++)
cout << dist[i] << " ";
return 0;
}
Floyd
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dis[i][j] = 0;
} else {
dis[i][j] = inf;
}
}
}
for(int k = 1; k <= n; k++) { //途径k
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
}
}
SPFA
const int inf = 1e16;
int dis[N], vis[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int x, y, w;
cin >> x >> y >> w;
ad(x, y, w);
}
for (int i = 1; i <= n; i++) {
dis[i] = inf;
}
dis[s] = 0;
queue<int> q;
q.push(s);
while (q.size()) {
int cur = q.front();
q.pop();
vis[cur] = false;
for (int i = head[cur]; i; i = nx[i]) {
if (dis[cur] + v[i] < dis[to[i]]) {
dis[to[i]] = dis[cur] + v[i];
if (!vis[to[i]]) {
q.push(to[i]);
vis[to[i]] = true;
}
}
}
}
return 0;
}
树的直径
两遍DFS求深度最大点
结论：树上一点到树上另一点的最远点为树的直径的一个端点
倍增LCA
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
const int N = 5e5 + 10;
int head[N], nx[N*2], to[N*2];
int fa[N][35];
int dep[N];
int id = 1;
int n, m, s;
void add(int x, int y) {
to[id] = y;
nx[id] = head[x];
head[x] = id++;
}
void dfs(int now, int f) {
fa[now][0] = f;
dep[now] = dep[f] + 1;
for (int i = head[now]; i; i = nx[i]) {
if (to[i] == f) continue;
dfs(to[i], now);
}
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) {
swap(x,y);
}
while (dep[x] > dep[y]) {
x = fa[x][__lg(dep[x] - dep[y])];
}
if (x == y) return x; // 节点相同就返回本身，否则就错误返回父亲节点
for (int i = 30; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s;
for (int i = 1; i <= n-1; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dep[0] = 0;
dfs(s,0);
fa[s][0] = s;
for (int i = 1; i <= 21; i++) {
for (int j = 1; j <= n; j++) {
fa[j][i] = fa[fa[j][i-1]][i-1];
}
}
while (m--) {
int a, b;
cin >> a >> b;
cout << LCA(a, b) << "\n";
}
return 0;
}
强联通分量缩点(SCC)
自带拓扑序
struct SCC {
int n, now, cnt;
vector<vector<int>> ver;
vector<int> dfn, low, col, stk;
SCC(int n) : n(n), ver(n + 1), low(n + 1) {
dfn.resize(n + 1, -1);
col.resize(n + 1, -1);
now = cnt = 0;
}
void add(int x, int y) {
ver[x].push_back(y);
}
void tarjan(int x) {
dfn[x] = low[x] = now++;
stk.push_back(x);
for (auto y : ver[x]) {
if (dfn[y] == -1) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (col[y] == -1) {
low[x] = min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) {
int pre;
cnt++;
do {
pre = stk.back();
col[pre] = cnt;
stk.pop_back();
} while (pre != x);
}
}
auto work() { // cnt 新图的顶点数量
for (int i = 1; i <= n; i++) { // 避免图不连通
if (dfn[i] == -1) {
tarjan(i);
}
}
vector<int> siz(cnt + 1); // siz 每个 scc 中点的数量
vector<vector<int>> adj(cnt + 1);
for (int i = 1; i <= n; i++) {
siz[col[i]]++;
for (auto j : ver[i]) {
int x = col[i], y = col[j];
if (x != y) {
adj[x].push_back(y);
}
}
}
return make_tuple(cnt, adj, col, siz);
}
//SCC scc(n);
//auto [cnt, adj, col, siz] = scc.work(); C++17 结构化绑定
};
最小生成树
const int MAXN = 2e5 + 1;
struct Node {
int x,y,v;
} a[MAXN];
int fa[5001];
int find(int x) {
if(fa[x] != x) {
x = find(fa[x]);
}
return fa[x];
}
bool merge(int x,int y) {
int fx = find(x),fy = find(y);
if(fx != fy) {
fa[fx] = fy;
return true;
} else {
return false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> a[i].x >> a[i].y >> a[i].v;
}
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
sort(a+1,a+m+1,[](Node a,Node b) {return a.v < b.v;});
int cnt = 0;
int ans = 0;
for (int i = 1; i <= m; i++) {
if(merge(a[i].x,a[i].y)) {
cnt++;
ans += a[i].v;
}
}
if(cnt == n - 1) {
cout<<ans;
} else {
cout<<"orz";
}
cout<<endl;
return 0;
}
其他
二分
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
二维差分前缀和
void add(int x1, int y1, int x2, int y2, int v) {
sum[x1][y1] += v;
sum[x2 + 1][y2 + 1] += v;
sum[x2 + 1][y1] -= v;
sum[x1][y2 + 1] -= v;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; i <= m; j++) {
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
int query(int x1 ,int y1 ,int x2, int y2) {
return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}
等差数列差分
[L,R] 加上一段等差数列
做两次差分
然后最后做两遍前缀和还原
void op(int l, int r, int s, int e,int d) {
ans[l] += s;
ans[l + 1] += d - s;
ans[r + 1] += -e - d;
ans[r + 2] += e;
}
背包DP
01背包
每种物品只能选择一次,设有n种物品，每种物品的价值为wi，体积为vi，背包的容量为V。 ans[i][j]代表有前i个物品，空间为j时的价值最大值。 取选第i个物品与不选第i个物品的较大值。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j < v[i]) {
ans[i][j] = ans[i - 1][j];
} else {
ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - v[i]] + w[i]);
}
}
}
Copy
滚动数组压缩空间
从后往前更新
for(int i = 1; i <= n; i++) {
for(int j = V; j >= v[i]; j--) {
ans[j] = max(ans[j],ans[j-v[i]] + w[i]);
}
}
Copy
完全背包
每种物品可以取任意次。 转移方程和01背包类似
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j < v[i]) {
ans[i][j] = ans[i - 1][j];
} else {
ans[i][j] = max(ans[i - 1][j], ans[i][j - v[i]] + w[i]);
}
}
}
滚动数组压缩空间
从前往后更新
for(int i = 1; i <= n; i++) {
for(int j = v[i]; j <= V; j++) {
ans[j] = max(ans[j],ans[j-v[i]] + w[i]);
}
}
n维背包
有多个考虑因素
以二维01背包为例，增加条件背包最大承重为M，每一件物品的质量为mi。
for (int i = 1; i <= n; i++)//放置第i件物品
{
for (int j = 1; j <= V; j++)//j为当前体积
{
for (int k = 1; k <= M; k++)//k为当前质量
{
if (j - v[i] < 0 || k - m[i] < 0) { //任意一种条件不满足就放不进去
a[i][j][k] = a[i - 1][j][k];
} else {
a[i][j][k] = max(a[i - 1][j][k], a[i - 1][j - v[i]][k - m[i]] + c[i]);
}
}
}
}
滚动数组压缩空间
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) { // j为当前体积
for (int k = M; k >= m[i]; k--) { // k为当前质量
b[j][k] = max(b[j][k], b[j - v[i]][k - m[i]] + c[i]);
}
}
}
杂项
头
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dbg(...) _((char*)#__VA_ARGS__,__VA_ARGS__)
template<typename t> void _(char* p,t x){cout<<p<<'='<<x<<'\n';}
template<typename t,typename... a>
void _(char* p,t x,a... y){while(*p!=',')cout<<*p++;cout<<'='<<x<<',';_(p+1,y...);}
void solve() {
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
对拍
//输入输出重定向
// wa.cpp, 存放待寻找错误的代码
freopen("rd.txt","r",stdin);
freopen("wa.out","w",stdout);
// ac.cpp, 存放暴力或正确的代码
freopen("rd.txt","r",stdin);
freopen("ac.out","w",stdout);
// rd.cpp
freopen("rd.txt", "w", stdout);
//随机数生成
static mt19937_64 rng(random_device{}());
int r(int l, int r) {
return uniform_int_distribution<int>(l,r)(rng); // rng() % (r - l + 1) + l;
}
//对拍器
#include<bits/stdc++.h>
using namespace std;
int main() {
int i=1;
int n = 100;
while (i <= n) { //一直循环，直到找到不一样的数据
// cout<<i<<endl;
system("rd.exe");
system("wa.exe");
system("ac.exe");
if (system("fc ac.out wa.out")) { //当 fc 返回 1 时，说明这时数据不一样
cout << "WA" << endl;
return 0;
}
i++;
}
cout << n << "组数据"<< "OK" <<'\n';
return 0;
}
int128
using i128 = __int128_t;
auto& operator>>(istream& it, __int128_t& j) {
string val;
it >> val;
reverse(val.begin(), val.end());
__int128_t ans = 0;
bool f = 0;
char c = val.back();
val.pop_back();
for (; c < '0' || c > '9'; c = val.back(), val.pop_back()) {
if (c == '-') {
f = 1;
}
}
for (; c >= '0' && c <= '9'; c = val.back(), val.pop_back()) {
ans = ans * 10 + c - '0';
}
j = f ? -ans : ans;
return it;
}
auto& operator<<(ostream& os, const __int128_t& j) {
string ans;
function<void(__int128_t)> write = [&](__int128_t x) {
if (x < 0) ans += '-', x = -x;
if (x > 9) write(x / 10);
ans += x % 10 + '0';
};
write(j);
return os << ans;
}
关闭同步流版本
#define int __int128_t
// 快读 __int128
inline int read() {
int x = 0;
bool neg = false;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') neg = true, c = getchar();
while (c >= '0' && c <= '9') {
x = x*10 + (c-'0');
c = getchar();
}
return neg ? -x : x;
}
// 快写 __int128
inline void write(int x) {
if (x == 0) { putchar('0'); return; }
if (x < 0) { putchar('-'); x = -x; }
char buf[40]; // __int128 最多 39 位
int i = 0;
while (x) {
buf[i++] = '0' + (int)(x % 10);
x /= 10;
}
while (i--) putchar(buf[i]);
}
取模机
using i64 = long long;
using u64 = unsigned long long;
// 特化的 2^61-1 模数类
struct Mod61 {
static constexpr u64 M = (1ull << 61) - 1;
u64 v;
Mod61(u64 x = 0) : v(x) {
v = (v & M) + (v >> 61);
v = v < M ? v : v - M;
}
static u64 mul(u64 a, u64 b) {
u64 l = (u32)a * (u32)b;
u64 m = (u32)a * (b >> 32) + (u32)b * (a >> 32);
u64 h = (a >> 32) * (b >> 32);
u64 t = (l & M) + (l >> 61) + (h << 3) + (m >> 29) + ((u32)m << 32 >> 3) + 1;
t = (t & M) + (t >> 61);
return t - 1;
}
Mod61 operator+(Mod61 o) const {
u64 s = v + o.v;
return {s < M ? s : s - M};
}
Mod61 operator-(Mod61 o) const {
return {v >= o.v ? v - o.v : M + v - o.v};
}
Mod61 operator*(Mod61 o) const {
return {mul(v, o.v)};
}
Mod61& operator+=(Mod61 o) {
v += o.v;
if (v >= M) v -= M;
return *this;
}
Mod61& operator-=(Mod61 o) {
v = v >= o.v ? v - o.v : M + v - o.v;
return *this;
}
Mod61& operator*=(Mod61 o) {
v = mul(v, o.v);
return *this;
}
bool operator==(Mod61 o) const { return v == o.v; }
bool operator!=(Mod61 o) const { return v != o.v; }
Mod61 pow(u64 exp) const {
Mod61 res(1), base(*this);
for (; exp; exp /= 2) {
if (exp & 1) res *= base;
base *= base;
}
return res;
}
Mod61 inv() const {
return pow(M - 2);
}
Mod61 operator/(Mod61 o) const {
return *this * o.inv();
}
Mod61& operator/=(Mod61 o) {
return *this *= o.inv();
}
friend std::ostream& operator<<(std::ostream& os, Mod61 m) {
return os << m.v;
}
friend std::istream& operator>>(std::istream& is, Mod61& m) {
u64 x;
is >> x;
m = Mod61(x);
return is;
}
u64 val() const { return v; }
};
/** 取模类（MLong & MInt 新版）
* 2023-08-14: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63433564
*
* 根据输入内容动态修改 MOD 的方法：Z::setMod(p) 。
**/
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
// template<>
// int MInt<0>::Mod = 998244353;
// template<int V, int P>
// constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353;
using Z = MInt<P>;