板子 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;
}