我对舟舟人的厌恶更深一层（大雾
T1 烧结核凝晶
题目
斯宝在维多利亚发现了一种新的物质——转质盐。
巨船的工匠发现转质盐可以制作一种名叫烧结核凝晶的材料，工匠们已经试制出了烧结核凝晶，可是他们不小心丢了一种关键合成物——转质盐聚块的合成配方，斯宝希望你能帮忙找回如何制作它的方法。
烧结核凝晶是一种特定高温环境下具有分子识别能力的材料。作为助剂能选择性地吸附源石，为精密加工源石材料、降低源石器件耗能提供新可能。 ——PRTS wiki
具体来说，转质盐聚块由糖组、半自然溶剂、转质盐组三种材料合成，工匠们先需要将糖组溶化至半自然溶剂中，再与打碎的转质盐组进行混合搅拌、高温熔化、塑型、冷却而成。工匠们丢失的配方记载的是将糖组溶化至半自然溶剂这一过程的配方比，但工匠们找到了当时的试验记录残破的一部分：
-
我们配置了 \(1 \le n \le 10^5\) 份糖组与半自然溶剂的溶液组，其中第 \(i\) 组溶液中糖组的质量为 \(a_i\)，整份溶液的质量为 \(b_i\)。
-
由前面的实验可以得到，选 \(1 \le k \le n\) 份溶液合成时成功率最大，并且糖的浓度越高，最后得到的转质盐聚块越稳定；
-
一位炎国的冶金学家用她特殊的源石技艺选出了这 \(k\) 份材料，让这 \(k\) 份材料混合后的糖的质量分数取到最大值；
虽然这位冶金学家已经暂时离开了斯宝的船，但工匠们幸运地找到了当时实验的数据记录表，工匠们现在只需要知道糖占整个溶液的质量分数，并且误差不超过 \(10^{-5}\)，就能成功还原配方了。
斯宝希望你能在这位炎国的女士回归巨船前，帮工匠们还原配方。
Solution
典型的 0/1 分数规划问题，一个典型的二分答案的应用。
考虑二分答案最终的溶液质量分数 \(x\)，那么就要求 \(\displaystyle\frac{\sum b}{\sum a}\ge x\)，也就是 \(\displaystyle\sum b\ge \sum a \cdot x\)，因此考虑对每一个溶液计算一个 \(c=b-a\cdot x\)，然后将所有溶液按照 \(c\) 从大到小排序贪心选取 \(k\) 个然后看是否可以满足大于等于的条件即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 1e5;
constexpr double eps = 1e-8;
int n, a[_SIZE + 5], b[_SIZE + 5], k;
double c[_SIZE + 5];
bool check(double x) {
for (int i = 1; i <= n; i++) c[i] = a[i] - b[i] * x;
sort(c + 1, c + n + 1, [](double _, double __) {
return _ > __;
});
double res = 0;
for (int i = 1; i <= k; i++) res += c[i];
return res >= 0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
double l = 0, r = 1;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(10) << l << '\n';
return 0;
}
T2 斩荆辟路
题目
斯宝正在开船，突然海面上出现了一群海怪，他们挥舞着触须，开始进攻斯宝的船，斯宝紧急召集了他的船员抵抗海怪入侵。
斯宝发现，这些海怪有了一种特殊生物的领导后，可以使船员们受到剧烈的神经损伤，斯宝称其为海嗣。
狩猎！捕食！进化！大群！回归大群！ ——某不知名海嗣
在战斗中，斯宝注意到 6星干员 可以很好地猎杀海嗣，但是这次出海斯宝没有携带足够的干员，于是他联系了 \(k\) ，并使用他的电脑开始在卡池里抽（kai）卡（gua）。
具体来说，\(k\) 的电脑修改了保底机制，让每一次抽卡的概率都产生了变化，规则是：如果前面抽了连续 \(i\) 次卡没有出 6星干员，那么这次抽卡抽出 6星干员 的概率为 \(p_i\)（\(0 \le i \le k \le 100\)），但是不变的是第 \(k+1\) 次抽卡必定抽出 6星干员 （即\(p_k=1\)）。
为了保护他的船，斯宝决定把所有资源都投入卡池中，一共能抽 \(0 \le n \le 2 \times 10^7\) 次卡。斯宝想知道，他期望能寻访到几个 6星干员？
由于斯宝的 不稳定AI 已经快速计算出了答案，你只需要验证 AI 的答案，具体的说，设期望寻访到 \(\frac{p}{q}\) 个6星干员（\(\gcd(p,q)=1\)），你只要输出一个数 \(0 \le ans < 998244353\)，满足 \(q \cdot ans \equiv p \pmod{998244353}\)。
Solution
先考虑部分分，尝试写出一个 \(\mathcal O(nk)\) 的期望 \(\texttt{DP}\)。
定义 \(f[i][j]\) 表示已经抽了 \(i\) 次，并且连续 \(j\) 次没抽出来的期望获得干员数量，\(h[i][j]\) 表示抽了 \(i\) 次，并且连续 \(j\) 次没抽出来这个事件的概率。那么会发现只有 \(j=0\) 的情况是可以从前面任何的 \(j\) 转移过来，而 \(j\neq 0\) 时只能从 \(j-1\) 转移过来。根据这个思路，写出 \(\texttt{DP}\) 方程（为了方便，定义 \(p_{k+1}=1\)，来表示保底）。
\[\begin{array}{lll} h[i][0] &=& \displaystyle\sum\limits _{t=0}^{k} h[i-1][t]\cdot p_{t + 1} \\ h[i][j] &=& h[i-1][j-1]\cdot (1-p_{j-1}) \end{array} \]求出 \(h\) 过后推 \(f\) 就要简单一点了：
\[\begin{array}{lll} f[i][0] &=& \displaystyle(\sum\limits_{t=0}^{k} f[i-1][t] \cdot p_{t + 1}) + h[i][0]\cdot 1 \\ f[i][j] &=& f[i-1][j-1] \cdot (1-p_{j-1}) \end{array} \]边界条件：\(h[0][0]=1\)（也没抽卡并且连续 \(0\) 次没出的情况是所有情况的起点）。
这样就拿到了 40pts。
赛时代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 1e5, mod = 998244353;
int n, k, p[_SIZE + 5];
int f[_SIZE + 5][105], h[_SIZE + 5][105];
int Qpow(int x, int y) {
int res = 1, base = x % mod;
while (y) {
if (y & 1) res = res * base % mod;
base = base * base % mod, y >>= 1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++) {
static int a, b;
cin >> a >> b;
p[i] = a * Qpow(b, mod - 2) % mod;
} p[++k] = 1;
h[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int t = 0; t <= k; t++) {
(f[i][0] += f[i - 1][t] * p[t + 1] % mod) %= mod;
(h[i][0] += h[i - 1][t] * p[t + 1] % mod) %= mod;
} (f[i][0] += h[i][0]) %= mod;
for (int j = 1; j <= k; j++) {
f[i][j] = f[i - 1][j - 1] * (mod + 1 - p[j]) % mod;
h[i][j] = h[i - 1][j - 1] * (mod + 1 - p[j]) % mod;
}
}
int ans = 0;
for (int i = 0; i <= k; i++) (ans += f[n][i]) %= mod;
cout << ans << '\n';
return 0;
}
然后看到题目中有 \(n=2\times 10^7,k=0/1\) 的情况，所以可以用滚动数组优化一下空间，这样就可以拿到 55pts。
滚动数组优化空间：
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int _SIZE = 1e5, mod = 998244353;
int n, k, p[_SIZE + 5];
int cur = 1, last = 0;
int f[2][105], h[2][105];
int Qpow(int x, int y) {
int res = 1, base = x % mod;
while (y) {
if (y & 1) res = res * base % mod;
base = base * base % mod, y >>= 1;
}
return res;
}
void MOD(int &x) {if (x > mod) x -= mod;}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++) {
static int a, b;
cin >> a >> b;
p[i] = a * Qpow(b, mod - 2) % mod;
} p[++k] = 1;
h[cur][0] = 1;
for (int i = 1; i <= n; i++) {
swap(last, cur);
f[cur][0] = h[cur][0] = 0;
for (int t = 0; t <= k; t++) {
f[cur][0] += f[last][t] * p[t + 1] % mod, MOD(f[cur][0]);
h[cur][0] += h[last][t] * p[t + 1] % mod, MOD(h[cur][0]);
} f[cur][0] += h[cur][0], MOD(f[cur][0]);
for (int j = 1; j <= k; j++) {
f[cur][j] = f[last][j - 1] * (mod + 1 - p[j]) % mod;
h[cur][j] = h[last][j - 1] * (mod + 1 - p[j]) % mod;
}
}
int ans = 0;
for (int i = 0; i <= k; i++) (ans += f[cur][i]) %= mod;
cout << ans << '\n';
return 0;
}
现在来考虑正解做法。注意到上述的 \(f,h\) 的转移是一对乘法式子加和得到的，所以可以用矩阵乘法进行优化。因为 \(f\) 的转移依赖 \(h\)，所以就将 \(f,h\) 放到一个向量里面进行转移。需要注意 \(f[i][0]\) 的转移是与 \(h[i][0]\) 相关，而非 \(h[i-1][0]\)，因此初始矩阵应该设计为 \(\begin{bmatrix}f[0][0],f[0][1]\cdots f[0][k],h[1][0],h[1][1]\cdots h[1][k] \end{bmatrix}\)。然后得到转移矩阵：
\[\begin{bmatrix}f[i][0]\cdots,h[i+1][0]\cdots\end{bmatrix} = \begin{bmatrix}f[i-1][0]\cdots,h[i][0]\cdots\end{bmatrix} \times \begin{bmatrix} p_1 & (1-p_1) & 0 & \cdots & 0 & \cdots & \cdots \\ p_2 & 0 & (1-p_2) & \cdots & 0 & \cdots & \cdots \\ \vdots & \vdots & \vdots & \ddots & \vdots & \cdots & \cdots\\ p_{k+1} & \cdots & \cdots & \cdots & 0 & \cdots & \cdots\\ 1 & 0 & \cdots & \cdots & p_1 & (1-p_1) & \cdots \\ \vdots & \vdots & \ddots & \vdots & \vdots & \cdots & \ddots\\ 0 & \cdots & \cdots & 0 & p_{k+1} & \cdots & 0 \end{bmatrix} \]（这个矩阵真的难写，参考代码里的实现可能更好看懂）
然后用矩阵快速幂转移就行了。时间复杂度为 \(\mathcal O(k^3\log n)\)，不过因为矩阵的边长是 \(2k\)，所以常数有点大，要卡一卡常数才可以过。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
constexpr int _SIZE = 2e2, mod = 998244353;
int n, k, p[_SIZE + 5];
int Qpow(int x, int y) {
int res = 1, base = x % mod;
while (y) {
if (y & 1) res = (long long)res * base % mod;
base = (long long)base * base % mod, y >>= 1;
}
return res;
}
void MOD(int &x) {if (x >= mod) x -= mod;}
int MUL(int x, int y) {long long res = (long long)x * y; if (res >= mod) res %= mod; return res;}
struct MATRIX {
int a[_SIZE + 5][_SIZE + 5], r, c;
MATRIX() {memset(a, 0, sizeof a); r = 0; c = 0;}
void reset() {for (int i = 1; i <= 2 * k + 2; i++) a[i][i] = 1;}
MATRIX operator * (const MATRIX &x) const {
MATRIX res; res.r = r, res.c = x.c;
for (int k = 1; k <= c; k++)
for (int j = 1; j <= res.c; j++) {
if (!x.a[k][j]) continue;
for (int i = 1; i <= res.r; i++)
MOD(res.a[i][j] += MUL(a[i][k], x.a[k][j]));
}
return res;
}
MATRIX operator ^ (int x) const {
MATRIX res; res.reset(); res.c = res.r = 2 * k + 2;
MATRIX base = *this;
while (x) {
if (x & 1) res = res * base;
x >>= 1, base = base * base;
}
return res;
}
void print() {
for (int i = 1; i <= r; i++, cout << '\n')
for (int j = 1; j <= c; j++) cout << setw(10) << a[i][j] << ' ';
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++) {
static int a, b;
cin >> a >> b;
p[i - 1] = (long long)a * Qpow(b, mod - 2) % mod;
} p[k] = 1;
int maxn = 2 * k + 2;
MATRIX base; base.r = 1, base.c = maxn;
base.a[1][k + 2] = p[0], base.a[1][k + 3] = (mod + 1 - p[0]);
MATRIX turn; turn.r = turn.c = maxn;
for (int i = 0; i <= k; i++) turn.a[i + 1][1] = p[i]; turn.a[k + 2][1] = 1;
for (int i = 1; i <= k; i++) turn.a[i][i + 1] = (mod + 1 - p[i - 1]);
for (int i = k + 2; i <= maxn; i++) turn.a[i][k + 2] = p[i - k - 2];
for (int i = k + 3; i <= maxn; i++) turn.a[i - 1][i] = (mod + 1 - p[i - k - 3]);
MATRIX ans = base * (turn ^ n);
int res = 0;
for (int i = 0; i <= k; i++) MOD(res += ans.a[1][i + 1]);
cout << res << '\n';
return 0;
}
T4 大群·树
题目
斯宝突破了大群的封锁，登录了大群的一个小岛据点。
天色阴沉了下来，那些美丽而危险的、发光的潮水在此刻逐渐清晰，它们悄然蔓延到了岛上的岩洞口，我们的脚边。
干员们在小岛的岩洞口里发现了一个树状洞穴结构，斯宝决定派三个高级资深干员前往洞穴中侦察。
巨船上有一个基于源石技艺的传送法阵，可以将三名干员传送至洞穴的三个节点中。可是，斯宝的源石工匠发现岩洞内有剧烈的干扰源，巨船上的通信装置无法和岩洞里通讯。
船上的每个干员都有一个便携式通讯器，经测算，它们能在距离小于等于 \(k\) 的时候互相通讯（通讯的距离就是两个节点在树上的最短路径的边数）。由于通讯器没有中继装置，要求三个干员的通讯器两两距离不超过 \(k\) 才能互相通讯。
现在，巨船上的雷达以扫描出洞穴的结构，斯宝想知道，有多少个无序节点三元组满足如果干员传送至这三个不同的节点上，且他们能互相通信？
形式化题意：
一棵树，选 \(3\) 个不同点，两两之间距离小于等于 \(k\) 的方案数（距离是最短路径的边数）。
\(3\le n \le 10^5, 1\le k \le 10^5\)
Solution
看到与树上距离相关的东西都可以用淀粉质或者淀粉树试试。
对于一组点，会发现距离最大的一对点中一定会有一个点是在这组点中深度最大的。所以就得到了一种做法：按照深度从小到大加入节点，新加入节点的时候查询有多少与这个节点的距离小于等于 \(k\) 的，假设这个数量为 \(cnt\)，那么当前点作为深度最大的点的时候对答案的贡献就是 \(\begin{pmatrix}cnt \\ 2\end{pmatrix}\)。
现在问题变成了查询有多少节点与当前节点的距离小于等于 \(k\)，并且会有很多次查询。会发现这就变成了点分树的标准操作了，所以就建出点分树，然后加入点的时候才将当前点的贡献加入树状数组就行了。
因为点分树的深度是 \(\log\) 级别的，因此总的时间复杂度是 \(\mathcal O(n\log^2 n)\)（两个 \(\log\) 分别来自树状数组和点分树跳父亲）。
#include<bits/stdc++.h>
#define ULOOP(i, x, y) for (int i = x; i <= y; i++)
#define DLOOP(i, x, y) for (int i = x; i >= y; i--)
using namespace std;
constexpr int _SIZE = 1e5;
int n, k;
struct EDGE{
int nxt, to;
}edge[(_SIZE << 1) + 5];
int tot, head[_SIZE + 5];
void AddEdge(int x, int y) {
edge[++tot] = {head[x], y};
head[x] = tot;
}
int fa[_SIZE + 5], dep[_SIZE + 5], top[_SIZE + 5], siz[_SIZE + 5], son[_SIZE + 5];
void DfsForSon(int x, int F) {
siz[x] = 1, dep[x] = dep[F] + 1, fa[x] = F;
int maxson = -1;
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (twd == F) continue;
DfsForSon(twd, x);
siz[x] += siz[twd];
if (siz[twd] > maxson) maxson = siz[twd], son[x] = twd;
}
}
void DfsForTop(int x, int topf) {
top[x] = topf;
if (!son[x]) return;
DfsForTop(son[x], topf);
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (twd == fa[x] || twd == son[x]) continue;
DfsForTop(twd, twd);
}
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
int DIS(int x, int y) {
return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}
vector<int> C[2][_SIZE + 5];
int root, sum, ban[_SIZE + 5], nfa[_SIZE + 5];
bool vis[_SIZE + 5];
void getroot(int x, int F) {
siz[x] = 1, ban[x] = 0;
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (twd == F || vis[twd]) continue;
getroot(twd, x);
siz[x] += siz[twd];
ban[x] = max(ban[x], siz[twd]);
}
ban[x] = max(ban[x], sum - siz[x]);
if (ban[x] < ban[root]) root = x;
}
void build(int x) {
vis[x] = 1;
C[0][x].resize(sum + 2);
C[1][x].resize(sum + 2);
for (int i = head[x]; i; i = edge[i].nxt) {
int twd = edge[i].to;
if (vis[twd]) continue;
sum = siz[twd], root = 0;
getroot(twd, x);
nfa[root] = x;
build(root);
}
}
#define lowbit(_) (_ & -_)
void update(int opt, int x, int i, int v) {
i++;
int sz = C[opt][x].size();
assert(i > 0);
for (; i < sz; i += lowbit(i)) C[opt][x][i] += v;
}
int query(int opt, int x, int i) {
int res = 0; i++;
i = min((int)C[opt][x].size() - 1, i);
if (i <= 0) return res;
for (; i; i -= lowbit(i)) res += C[opt][x][i];
return res;
}
pair<int, int> node[_SIZE + 5];
long long ans = 0;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
ULOOP (i, 1, n - 1) {
static int u, v;
cin >> u >> v;
AddEdge(u, v), AddEdge(v, u);
}
dep[1] = 1;
DfsForSon(1, 0); DfsForTop(1, 1);
sum = n, ban[0] = INT_MAX;
getroot(1, root = 0);
build(root);
ULOOP (i, 1, n) node[i] = make_pair(dep[i], i);
sort(node + 1, node + n + 1);
ULOOP (i, 1, n) {
int cur = node[i].second, temp = 0, s = 0;
for (int i = cur; i; s = i, i = nfa[i]) {
int D = k - DIS(cur, i);
temp += query(0, i, D);
if (s) temp -= query(1, s, D - 1);
}
ans += (long long)temp * (temp - 1) / 2;
for (int i = cur; i; i = nfa[i]) {
update(0, i, DIS(cur, i), 1);
if (nfa[i]) update(1, i, DIS(cur, nfa[i]) - 1, 1);
}
}
cout << ans << '\n';
return 0;
}