板子 5.29–7.19

目录

1. 树状数组
2. KMP
3. 矩阵快速幂
4. 数位DP
5. 状压枚举子集
6. 快速幂（新版
7. priority_queue
8. dijkstra
9. 单调栈
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<int> 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 <= r);assert(l > 0);if (l > r)return 0ll;return ask(r) - ask(l - 1);}
}; // Tree tr(n);

2. KMP

 
pair<vector<int>, vector<int>> KMP(string &s, string &t)
{vector<int> idx; // t作为子串在s中出现的下标int n = t.size(), m = s.size();string a = " " + t + "#" + s;vector<int> kmp(n + m + 10); // t的前缀t[1~i]中 t[1~i]的前缀和后缀相同的最大长度for (int i = 2; i <= n + m + 1; i++) {int j = kmp[i - 1];while (j && a[i] != a[j + 1])j = kmp[j];if (a[i] == a[j + 1])j++;kmp[i] = j;if (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<int>> mat;Matrix(int _n, int _m) : n(_n), m(_m), mat(_n + 1, vector<int>(_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<int> &operator[](int i) const { return mat[i]; }// 可写访问vector<int> &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 <= m; k++){res[i][j] = (res[i][j] + mat[i][k] * b[k][j]) % mod;}return res;}// 矩阵快速幂Matrix pow(int k) const{assert(n == m);Matrix res = Matrix::identity(n);Matrix a = *this;while (k){if (k & 1)res = res * a;a = a * a;k >>= 1;}return res;}
};

4. 数位DP

void _()
{string k;int d;cin >> k >> d;int n = k.size();k = ' ' + k;vector<int> num(n + 1);for (int i = 1; i <= n; i++)num[i] = k[n - i + 1] - '0';vector<vector<array<int, 2>>> f(n + 1, vector<array<int, 2>>(110, array<int, 2>{-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 <= n; j++)cin >> a[i][j];}int mx = 1ll << n;vector<int> 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 <= n; j++){f[u] += a[i][j] * (u >> 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<Node> q;bool operator<(const Node &other) const // 大根堆{if (x - other.x)return x < other.x;elsereturn y < other.y;}// priority_queue<Node, vector<Node>, greater<>> q;bool operator>(const Node &other) const // greater<> 小根堆{if (x - other.x)return x > other.x;elsereturn y > other.y;}
};

8. dijkstra

struct Node
{int u, dis;// priority_queue<Node> q;bool operator<(const Node &other) const // 大根堆{return dis < other.dis;}// priority_queue<Node, vector<Node>, greater<>> q;bool operator>(const Node &other) const // greater<> 小根堆{return dis > other.dis;}
};
struct edge
{int v, w;
};auto dij = [&](vector<vector<edge>> &e, int s){vector<int> f(n + 1, 1e18);priority_queue<Node, vector<Node>, 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<int> stk(n + 1);for (int i = 1; i <= n; i++){int x = a[i];for (int j = t; j >= 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 <typename T>
void bug(initializer_list<T> list)
{cerr << "debug: ";for (const auto &elem : list)cerr << elem << ' ';cerr << endl;
}template <typename Container>
void bug(const Container &container)
{cerr << "debug: ";for (const auto &elem : container)cerr << elem << ' ';cerr << endl;
}