矩阵优化DP+后缀树+线段树/值域二进制划分+前缀和fight
先考虑刷表 \(DP\) ，直接依次考虑这一次攻击谁即可。
设 \(f[n][i][j][t]\) 表示第 \(n\) 局有 \(i\) 个 \(1\) 星怪， \(j\) 个 \(2\) 星怪， \(t\) 个 \(3\) 星怪这个局面的概率。
发现有效状态最多只有 \(166\) 个，且 \(n\) 为 \(10^{18}\) 量级，考虑矩阵优化。
然后发现过不去，预处理出转移矩阵的 \(2\) 的整次幂，然后和状态列向量直接乘，可以省去一个 \(166\) 。
点击查看
/*
Begin 8:13
Start code 8:24
End Debug 9:24
AC
Enjoy coding
*/
#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int mod = 998244353;
const int V = 60;
typedef long long ll;int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
int mul(int u, int v) { return 1ll * u * v >= mod ? 1ll * u * v % mod : u * v; }
int MyPow(int a, int b) { int ans = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a); return ans; }
struct Matrix {int a[170][170], n, m;Matrix() { n = m = 0; std::memset(a, 0, sizeof(a)); }int* operator [](int x) { return a[x]; }void init() { lep(i, 0, n - 1) a[i][i] = 1; }friend Matrix operator * (Matrix A, Matrix B) {Matrix C; C.n = A.n, C.m = B.m;lep(i, 0, C.n - 1) lep(j, 0, C.m - 1) {__int128 K = 0;lep(k, 0, A.m - 1) K += 1ll * A[i][k] * B[k][j];C[i][j] = K % mod;}return C;}
}I, D, pw[V + 1], Y;int Q, m, k, ud[10][10][10], idx; ll n;inline int id(int i, int j, int k) { return (ud[i][j][k] ? ud[i][j][k] : ud[i][j][k] = ++idx) - 1; }int main() {std::ios::sync_with_stdio(false);std::cin >> Q >> m >> k; int pt = id(k, k, k), inv, p, J, T;D[pt][pt] = 1;lep(i, 0, k) lep(j, 0, k) lep(t, 0, k) if (i + j + t <= k) {if (m < 2 and j) continue;if (m < 3 and t) continue;inv = MyPow(i + j + t + 1, mod - 2), p = id(i, j, t);D[pt][p] = inv, D[p][p] = inv;if (i) D[id(i - 1, j, t)][p] = mul(i, inv);if (j) { J = mul(j, inv);if (i + j + t < k) {if (m == 2) D[id(i + 1, j, t)][p] = J;else D[id(i + 1, j - 1, t + 1)][p] = J;}else D[id(i + 1, j - 1, t)][p] = J;}if (t) { T = mul(t, inv);if (i + j + t < k) D[id(i, j + 1, t)][p] = T;else D[id(i, j + 1, t - 1)][p] = T;}} D.n = D.m = I.n = idx, I.m = 1;if (m == 1) I[id(1, 0, 0)][0] = 1;else if (m == 2) I[id(0, 1, 0)][0] = 1;else I[id(0, 0, 1)][0] = 1;pw[0] = D;lep(i, 1, V) pw[i] = pw[i - 1] * pw[i - 1];lep(i, 1, Q) {std::cin >> n; Y = I;rep(i, V, 0) if ((n >> i) & 1) Y = pw[i] * Y;std::cout << Y[pt][0] << '\n';}return 0;
}
sufparacautokmpar
在后缀树的某个节点上，我们的问题即要求子树内两两异或的最大值，使用 \(Tire\) 树启发式合并即可。
具体的，我们维护每棵 \(Tire\) 树的答案，合并时，选取更小的那一棵，遍历每个元素在另一棵上查询异或最大值，然后和原本取最优即可。
点击查看
#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 4e5 + 7;
const int V = 20;
typedef long long ll;int n, w[_], idx = 1, last = 1, lk[_], len[_], ans; char s[_];
int lt[_ << 5][2], tot, mx[_], rt[_]; std::multiset <int> S[_];
std::map<int, int> ch[_];
std::vector <int> e[_];int rb() { return ++tot; }
void ins(int&u, int x, int dp) {if (dp == -2) return; if (!u) u = rb();ins(lt[u][(x >> dp) & 1], x, dp - 1);
}
int qry(int u, int v) {int ans = 0, k;rep(i, V, 0) {if (!u) break; k = (v >> i) & 1;if (lt[u][k ^ 1]) u = lt[u][k ^ 1], ans ^= (1 << i);else u = lt[u][k];}return ans;
}
void Mrg(int x, int y) { bool fl = true;if (S[x].size() < S[y].size()) fl = false, std::swap(x, y);mx[x] = std::max(mx[x], mx[y]);for (int v : S[y]) mx[x] = std::max(mx[x], qry(rt[x], v));for (int v : S[y]) ins(rt[x], v, V), S[x].insert(v);if (!fl) { std::swap(mx[x], mx[y]), std::swap(S[x], S[y]), std::swap(rt[x], rt[y]); }
}
int exd(int c) {int p = last, np = ++idx; last = np; len[np] = len[p] + 1;while (p and !ch[p].count(c)) ch[p][c] = np, p = lk[p];if (!p) lk[np] = 1;else {int q = ch[p][c];if (len[q] == len[p] + 1) lk[np] = q;else {int nq = ++idx; ch[nq] = ch[q], lk[nq] = lk[q], len[nq] = len[p] + 1;lk[np] = lk[q] = nq;while (p and ch[p][c] == q) ch[p][c] = nq, p = lk[p];}}return np;
}
void dfs(int u) {for (int v : e[u]) dfs(v), Mrg(u, v);if (S[u].size() <= 1) return;ans = std::max(ans, mx[u] + len[u]);
}
void calc() {lep(i, 2, idx) e[lk[i]].push_back(i);dfs(1);
}int main() {std::ios::sync_with_stdio(false);std::cin >> n >> (s + 1);lep(i, 1, n) std::cin >> w[i];int c;rep(i, n, 1) c = exd(s[i] - 'a'), ins(rt[c], w[i], V), S[c].insert(w[i]);calc();std::cout << ans << '\n';return 0;
}
greedy
这里记录一个乱搞做法，正解思路写在本题加强版。
先二分找到能拿下的第一个前缀，然后直接暴力即可过。
点击查看
#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 2e5 + 7;
typedef long long ll;
typedef double db;
typedef std::pair<int, int> PII;int n, m, v[_], w[_]; ll sv[_], sw[_];
int stk[_], tp, pr[_];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> m;lep(i, 1, n) std::cin >> v[i] >> w[i], sv[i] = sv[i - 1] + v[i], sw[i] = sw[i - 1] + w[i];rep(i, n + 1, 1) {while (tp and v[i] < v[stk[tp]]) --tp;pr[i] = tp ? stk[tp] : n + 1; stk[++tp] = i;}ll V, ans;while (m--) {std::cin >> V; ans = 0;int l = 0, r = n, md;while (l < r) { md = (l + r + 1) >> 1;if (sv[md] <= V) l = md;else r = md - 1;}V -= sv[l], ans += sw[l];++l;while (l <= n) {if (v[l] <= V) ans += w[l], V -= v[l], ++l;else l = pr[l];}std::cout << ans << '\n';}return 0;
}
stlgsfyxy
注意到式子可以化简
\[\begin{align*}
&\sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1+d\cdot i+j} a_{p_2 + d\cdot j + k}\\
=& \sum_{j=0}^{d-1} (\sum_{i=0}^{d-1} a_{p_1+d\cdot i+j} \sum_{k=0}^{d-1}a_{p_2 + d\cdot j + k})\\
=& \sum_{j=0}^{d-1} (pre_{p_1+j+d(d-1)}-pre_{p_1+j-d}) (sum_{p_2+d\cdot j + d - 1} - sum_{p_2 + d\cdot j - 1})
\end{align*}
\]
其中， \(pre_i\) 表示以 \(i\) 为结尾，步长为 \(d\) 的前缀和， \(sum_i\) 表示前缀和。
因为题目保证询问的下标 \(\le n\) ，所以 \(1+d(d-1)+d-1=d^2\le n\) ，即 \(d\le \sqrt n\) 。
所以将所有询问离线后可以直接暴力维护 \(pre\) ，然后直接枚举 \(j\) 计算。
点击查看
#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 2e5 + 7;
typedef unsigned int ui;
typedef double db;
typedef std::pair<int, int> PII;struct node { int i, p1, p2; };
int n, m, a[_];
ui pre[_], sum[_], ans[_];
std::vector <node> q[_];int main() {std::ios::sync_with_stdio(false);std::cin >> n;lep(i, 1, n) std::cin >> a[i], sum[i] = sum[i - 1] + a[i];std::cin >> m;int d, p1, p2;lep(i, 1, m) {std::cin >> d >> p1 >> p2;q[d].push_back({i, p1, p2});}lep(d, 1, n) if (q[d].size()) {lep(i, 1, n) {pre[i] = a[i];if (i > d) pre[i] += pre[i - d];}for (auto t : q[d]) {lep(j, 0, d - 1) ans[t.i] += (pre[t.p1 + j + d * (d - 1)] - pre[std::max(0, t.p1 + j - d)])* (sum[t.p2 + d * j + d - 1] - sum[t.p2 + d * j - 1]);}}lep(i, 1, m) std::cout << ans[i] << '\n';return 0;
}