板子 5.29–7.19
目录
1. 树状数组2. KMP3. 矩阵快速幂4. 数位DP5. 状压枚举子集6. 快速幂（新版7. priority_queue8. dijkstra9. 单调栈10. debug
内容
1. 树状数组
// 树状数组 快速求前缀和 / 前缀最大值// 维护位置数量(离散化)...// (区间加 区间求和)维护差分数组 初始化add(i,a[i]-a[i-1])// tr1：维护d[i]的区间和。tr2：维护i⋅d[i]的区间和。// 则前缀和 pre[i]=(i + 1) * tr1.ask(i) - tr2.ask(i) 区间和 pre[r]-pre[l-1]struct Tree{ int n; vector tr; Tree(int n1) { n = n1 + 10; tr.assign(n, 0); } void add(int x, int v) // 加点 { assert(x > 0); for (int i = x; i <= n; i += i & -i) tr[i] += v; } int ask(int x) // 前缀查询 { if (!x) return 0; int res = 0; for (int i = x; i; i -= i & -i) res += tr[i]; return res; } int ask(int l, int r) // 区间查询 { r = max(1ll, r); assert(l 0); if (l > r) return 0ll; return ask(r) - ask(l - 1); }}; // Tree tr(n);
2. KMP
pair<vector, vector> KMP(string &s, string &t){ vector idx; // t作为子串在s中出现的下标 int n = t.size(), m = s.size(); string a = \" \" + t + \"#\" + s; vector kmp(n + m + 10); // t的前缀t[1~i]中 t[1~i]的前缀和后缀相同的最大长度 for (int i = 2; i n && kmp[i] == n) idx.push_back(i - 2 * n); } return {idx, kmp};} // auto [idx, kmp] = KMP(s, t);
3. 矩阵快速幂
struct Matrix{ int n, m; vector<vector> mat; Matrix(int _n, int _m) : n(_n), m(_m), mat(_n + 1, vector(_m + 1, 0)) {} // 下标从1开始 // 生成单位矩阵 static Matrix identity(int size) { Matrix res(size, size); for (int i = 1; i <= size; i++) res[i][i] = 1; return res; } // 只读访问 const vector &operator[](int i) const { return mat[i]; } // 可写访问 vector &operator[](int i) { return mat[i]; } // 矩阵乘法 Matrix operator*(const Matrix &b) const { assert(m == b.n); Matrix res(n, b.m); for (int i = 1; i <= n; i++) for (int j = 1; j <= b.m; j++) for (int k = 1; k >= 1; } return res; }};
4. 数位DP
void _(){ string k; int d; cin >> k >> d; int n = k.size(); k = \' \' + k; vector num(n + 1); for (int i = 1; i <= n; i++) num[i] = k[n - i + 1] - \'0\'; vector<vector<array>> f(n + 1, vector<array>(110, array{-1, -1})); auto dfs = [&](auto &&self, int u, int pre, int lim) -> int // 1~k数位和是d的倍数的个数 { if (!u) { return !pre; } if (~f[u][pre][lim]) return f[u][pre][lim]; int maxk = lim ? num[u] : 9; int res = 0; for (int i = 0; i <= maxk; i++) { res += self(self, u - 1, (pre + i) % d, lim && i == maxk); res %= mod; } return f[u][pre][lim] = res; }; cout << (dfs(dfs, n, 0, 1) - 1 + mod) % mod << \'\\n\';}
5. 状压枚举子集
void _() // 选择状态011001101 这些能够形成答案的最大值 然后再考虑划分为2个集合{ int n; cin >> n; int a[17][17] = {}; for (int i = 1; i <= n; i++) { for (int j = 1; j > a[i][j]; } int mx = 1ll << n; vector f(mx, -1); auto dp = [&](auto &&self, int u) -> int { if (~f[u]) return f[u]; f[u] = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j > i - 1 & 1 && u >> j - 1 & 1); } } // 子集 for (int sub = u; sub = sub - 1 & u;) f[u] = max(f[u], self(self, sub) + self(self, sub ^ u)); return f[u]; }; cout << dp(dp, mx - 1);}
6. 快速幂（新版
constexpr int mod = 998244353;int q_pow(int a, int b){ if (!a) return 1ll; int res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res;}int fen(int u, int d){ u %= mod, d %= mod; return u * q_pow(d, mod - 2) % mod;}
7. priority_queue
struct Node{ int x, y; // priority_queue q; bool operator<(const Node &other) const // 大根堆 { if (x - other.x) return x < other.x; else return y < other.y; } // priority_queue<Node, vector, greater> q; bool operator>(const Node &other) const // greater 小根堆 { if (x - other.x) return x > other.x; else return y > other.y; }};
8. dijkstra
struct Node{ int u, dis; // priority_queue q; bool operator<(const Node &other) const // 大根堆 { return dis < other.dis; } // priority_queue<Node, vector, greater> q; bool operator>(const Node &other) const // greater 小根堆 { return dis > other.dis; }};struct edge{ int v, w;}; auto dij = [&](vector<vector> &e, int s) { vector f(n + 1, 1e18); priority_queue<Node, vector, greater> q; q.push({s, 0}); f[s] = 0; while (q.size()) { auto [u, dis] = q.top(); q.pop(); if (dis > f[u]) continue; for (auto [v, d] : e[u]) { if (f[v] > f[u] + d) { f[v] = f[u] + d; q.push({v, f[v]}); } } } return f; };
9. 单调栈
// 下标 int t = 0; vector stk(n + 1); for (int i = 1; i = 0; j--) if (!j) lmx[i] = -1, t = j; else if (a[stk[j]] >= x) { lmx[i] = stk[j]; t = j; break; } stk[++t] = i; }
10. debug
template void bug(initializer_list list){ cerr << \"debug: \"; for (const auto &elem : list) cerr << elem << \' \'; cerr << endl;}template void bug(const Container &container){ cerr << \"debug: \"; for (const auto &elem : container) cerr << elem << \' \'; cerr << endl;}
