一场相当有收获的比赛。比赛链接
A – 石老板举世无双
解法一
尝试观察规律。我们发现，在完成$s$次操作以后，左端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]$，右端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)$。假如现在我们达到最终状态，其$l=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}$。那么，在$x$的二进制表示中，如果从高到底第$\mathrm{pos}$位为$1$，则在第$\mathrm{pos}$轮中，有check (mid) == 0，向右区间递归；否则向左区间递归。这是很容易解释的：若向右递归，则右端点不变。而在下一层，右端点表示中$a, b$的所有系数乘$2$，所以体现为二进制位末尾添一个$0$。反之，就变成$(x+(x+1))/2$，在下一层中体现为$2x+1$。如果其有$\operatorname{popc}(x)$位为$1$，则到达该状态的概率为$p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$。
以$s=3$时的状态$l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}$为例。$2$的三位二进制表示为$\text{0b010}$，则推断出在前三轮分别向右、左、右区间递归，到达其的概率为$p_0p_1^2$。
考虑计算一个状态的贡献。有$E(X)=\sum\limits_i p_ix_i$，程序最终输出$(l+r) / 2$，则我们需要求$$\sum_{x=0}^{2^s-1}\frac{(2x+1)a+(2^{s+1}-2x-1)b}{2^{s+1}}p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$$。存在$p_0, p_1$的高次项，不好处理，所以我们考虑合并处理${\operatorname{popc}(x)}$相同的项。我们钦定$\operatorname{popc}(x)=k$，则易得所有这样的$x$的和为$(2^s-1)\dbinom{s-1}{k-1}$（计算每一位对总和的贡献。钦定在$k$个$1$中必须选择第$t$位，其他位位置任选，共有$\dbinom{s-1}{k-1}$种选择；该位的贡献为$2^t\dbinom{s-1}{k-1}$，有$\sum\limits_{t=0}^{s-1}2^t=2^s-1$），这样的$x$共有$\dbinom{s}{k}$个。因此上述式子可以转写为$$\sum\limits_{k=0}^{s}\left(\frac{\left(2(2^s-1)\binom{s-1}{k-1}+\binom{s}{k}\right)(a-b)}{2^{s+1}}+\binom{s}{k}b\right)p_0^kp_1^{s-k}$$
直接代入上述式子计算，可以得到$\textbf{60 pts}$的好成绩。
（实际上在考场上推出的式子略微不同，但本质上只是调换了$a$一项的计算顺序。）
constexpr int N = 1e7 + 10, P = 998244353,
inv100 = 828542813;
ll a, b, s, p0, p1;
int powp1, powp0, invp0, ans, suma, sumb;
int fact[N], finv[N], pow2s1, invpow2s1, pow2s1m2;
inl ll fpow (ll a, ll b) {
ll res = 1; a %= P;
for (; b; b >>= 1) {
if (b & 1) res = res * a % P;
a = a * a % P;
}
return res;
}
inl void calc_inv (int lmt) {
fact[0] = 1;
for (ll i = 1; i <= lmt; ++i)
fact[i] = fact[i - 1] * i % P;
finv[lmt] = fpow (fact[lmt], P - 2);
for (int i = lmt - 1; ~i; --i)
finv[i] = finv[i + 1] * (i + 1ll) % P;
pow2s1 = fpow (2, s + 1);
pow2s1m2 = (pow2s1 - 2 + P) % P;
invpow2s1 = fpow (pow2s1, P - 2);
powp1 = 1, powp0 = fpow (p0, s);
invp0 = fpow (p0, P - 2);
}
inl ll C (int x, int y) {
if (y < 0) return 0; return x < y ? 0
: 1ll * fact[x] * finv[x - y] % P * finv[y] % P; }
int main () {
/* MOCK NOIP 20220514 吴秋实 */
read (a, b, s, p0, p1);
p0 = 1ll * p0 * inv100 % P,
p1 = 1ll * p1 * inv100 % P;
calc_inv (s + 2);
for (int k = 0; k <= s; ++k) {
suma = (C (s - 1, s - k - 1) * pow2s1m2 + C (s, k)) % P;
sumb = (C (s, k) * pow2s1 - suma + P) % P;
(ans += (1ll * suma * a + 1ll * sumb * b) % P * invpow2s1 % P
* (1ll * powp0 * powp1 % P) % P) %= P;
powp0 = 1ll * powp0 * invp0 % P,
powp1 = 1ll * p1 * powp1 % P;
}
print (ans);
return 0;
}能不能对它化简？答案是肯定的。我们继续合并同类项。
$$\begin{aligned}
\textbf{原式} & = \sum_{k=0}^{s}\left(\frac{2^s-1}{2^s}\dbinom{s-1}{k-1}+\frac{a-b}{2^{s+1}}\dbinom{s}{k}+b\dbinom{s}{k}\right)p_0^kp_1^{s-k} \\
& = {\color{blue}\frac{2^s-1}{2^s}\sum_{k=0}^{s}\dbinom{s-1}{k-1}p_0^kp_1^{s-k}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}\sum_{k=0}^{s}\dbinom{s}{k}p_0^kp_1^{s-k}} \\
& = {\color{blue}\frac{2^s-1}{2^s}p_0\sum_{k=0}^{s}\dbinom{s-1}{k-1}p_0^{k-1}p_1^{s-k}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}\sum_{k=0}^{s}\dbinom{s}{k}p_0^kp_1^{s-k}} \\
& = {\color{blue}\frac{2^s-1}{2^s}p_0(p_0+p_1)^{s-1}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}(p_0+p_1)^s} \\
& = {\color{blue}\frac{2^s-1}{2^s}p_0}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}}
\end{aligned}$$
发现两个式子分别可以由二项式定理得到常数和。这样我们就可以在 $\mathrm{O}(\log n)$ 的时间内计算快速幂求和了。
（其实在场上是通过Python暴力打表发现的规律……雾
constexpr int P = 998244353, inv100 = 828542813;
ll a, b, s, p0, p1, ans;
ll fpow (ll a, ll b) {
ll res = 1; a %= P;
for (; b; b >>= 1) {
if (b & 1) res = res * a % P;
a = a * a % P;
}
return res;
}
#define inv(x) fpow((x), P - 2)
int main () {
/* */
read (a, b, s, p0, p1);
ans = (fpow (2, s) - 1) * inv (fpow (2, s)) % P * (a - b + P) % P * (p0 * inv100 % P) % P
+ (a + (fpow (2, s + 1) - 1) * b % P) * inv (fpow (2, s + 1)) % P;
print (ans % P);
return 0;
} 解法二
实际上，根据期望的线性性就可以求解。
设 $E(\Delta l)$ 为 $l$ 在 $s$ 次操作以后期望右移的距离。由于每一轮操作独立，每一轮结束后区间长度一定，故有 $$\begin{aligned}E(\Delta l) & = \sum_{k=1}^{s}p_0\cdot 0+p_1\dfrac{b-a}{2^k}\\ & = p_1(b-a)(1-\dfrac{1}{2^s}) \end{aligned}$$（只有$p_1$的概率右移）。右端点同理，将系数更换为$p_0$即可。所以有 $$\begin{aligned}E(\text{ans}) & = (a+E(\Delta l)+b-E(\Delta r))/2 \\& =\dfrac{1}{2}\left(a+b+(b-a)(p_1-p_0)\dfrac{2^s-1}{2^s}\right)\end{aligned}$$
constexpr int P = 998244353, inv100 = 828542813;
ll a, b, s, p0, p1, ans;
inl ll fpow (ll a, ll b) {
ll res = 1; a %= P;
for (; b; b >>= 1) {
if (b & 1) res = res * a % P;
a = a * a % P;
}
return res;
}
#define inv(x) fpow((x), P - 2)
#define proc(x) (((x) % P + P) % P)
int main () {
/* */
read (a, b, s, p0, p1);
ans = inv (2) * ((a + b + (b - a + P) * proc (p1 * inv100 - p0 * inv100) % P
* (fpow (2, s) - 1) % P * inv (fpow (2, s)) % P) % P);
print (ans % P);
return 0;
} 解法三（题解做法）
考虑DP。设$f(x)$为经过$x$轮操作后$l$的期望位置，$g(x)$为$r$的期望位置，则根据期望的线性性有以下转移：
$$\begin{aligned} f(x)=p_0f(x)+p_1\frac{f(x)+g(x)}{2}\\ g(x)=p_1g(x)+p_0\frac{g(x)+f(x)}{2}
\end{aligned}$$
使用矩阵乘法加速递推即可。代码容易实现。
B – 石老板腾云驾雾
容易发现，设数$x$的因数中，能够找到的最大完全平方数为$g(x)=\sum\limits_{i=1}^{k}p_i^{c_i}, 2 \mid c_i$，且令$x’=\dfrac{x}{g(x)}$，则不能够同时选择两个相同的$x’$，否则其乘积必为完全平方数；两个不同的$x’$相乘，必然会存在次数为奇数的某个质因子，不是完全平方数。因此我们暴力分解其质因数求出不同$x’$的个数就是答案。
赛后翻看他人AC代码，发现一个精妙的优化：我们只需要筛查$\sqrt[3]{x}$以内的质因数。$x$至多存在两个质因数$p_1, p_2>\sqrt[3]{x}$，这时若其二者相同（乘积为完全平方数）则不考虑它们；否则它们的次数均为$1$，将包含在$x’$中。可以使用 sqrt 函数以常数时间判断。
综上，如果作质数筛预处理，时间复杂度为$\mathrm{O}(n \dfrac{\sqrt[3]{\max\{a\}}}{\ln \sqrt[3]{\max\{a\}}}+n \log n)$。
constexpr int N = 1e5 + 10, G = 1e3;
int n, x, fac[G+1], p[G>>2], pcnt;
set <int> g;
void sieve () {
for (int x = 2; x <= G; ++x) {
if (!fac[x])
fac[x] = p[++pcnt] = x;
for (int i = 1; i <= pcnt && p[i] <= fac[x]
&& p[i] * x <= G; ++i)
fac[p[i] * x] = p[i];
}
}
int _defac (int x) {
int c = 0, p = 0, res = 1;
while (x > 1) {
if (fac[x] == p) ++c;
else {
if (c & 1) res *= p;
c = 1, p = fac[x];
}
x /= fac[x];
}
if (c & 1) res *= p;
return res;
}
int defac (int x) {
if (x <= G) return _defac (x);
int res = 1, c = 0, ori = x;
for (int i = 1; i <= pcnt &&
p[i] * p[i] * p[i] <= ori; ++i) {
if (x % p[i]) continue;
c = 0; while (x % p[i] == 0)
x /= p[i], ++c;
if (c & 1) res *= p[i];
if (x <= G) return _defac (x) * res;
}
return ((int) sqrt (x) * (int) sqrt (x) == x)
? res : x * res;
}
int main () {
/* MOCK NOIP 20220514 吴秋实 */
read (n); sieve ();
for (int i = 1; i <= n; ++i)
read (x), g.insert (defac (x));
print (g.size ());
return 0;
}
C – 石老板心肌梗塞
由题意可得，假如$w=1,2,\cdots,\text{ans}-1$的路径均有至少$1$条没有经过边$e$，而有$w=\text{ans}$路径全部经过该边/在图上不存在，则答案就是$\text{ans}$。因此我们要求的就是满足“权值为$w$的路径全部经过边$e$”的最小的$w$。
自然想到，我们可对每一条路径作树上差分，在路径$(u, v)$的两端点和$\operatorname{lca}(u, v)$处分别加入/取消$w$的一次覆盖，则在某一条边上，我们求所有满足上述条件的权值集合的最小值即可。通过动态开点权值线段树、树上差分和线段树合并，在加入/取消$w$的覆盖时检查其计数是否等于$w$的全体路径数并更新该线段树的答案，就可以得到一个空间复杂度为$\mathrm{O}(m \log m)$，时间复杂度为$\mathrm{O}(m \log m+m \log n)$的解。期望得分$\textbf{80 pts}$。（据说如果卡常够好可以AC……
constexpr int N = 5e5 + 10, M = 2e6 + 10, INF = 0x3f3f3f3f;
int n, m, x, y, ecnt = 1, z, head[N];
int fa[N], dfn[N], tot, top[N], gcnt[N], lmt;
int dep[N], siz[N], hson[N], ans[N];
struct path { int x, y, z; } g[M];
struct edge { int v, nxt; } e[N<<1];
inl void add_e (int x, int y) {
e[++ecnt] = { y, head[x] }, head[x] = ecnt; }
void dfs (int x, int fr) {
dep[x] = dep[fa[x] = fr] + 1;
for (int i = head[x]; i; i = e[i].nxt) {
if (e[i].v == fr) continue;
dfs (e[i].v, x);
siz[x] += siz[e[i].v];
if (siz[e[i].v] > siz[hson[x]])
hson[x] = e[i].v;
}
++siz[x];
}
void decomp (int x, int tp) {
dfn[x] = ++tot; top[x] = tp;
if (!hson[x]) return;
decomp (hson[x], tp);
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].v != fa[x] && e[i].v != hson[x])
decomp (e[i].v, e[i].v);
}
int lca (int x, int y) {
while (top[x] != top[y])
dep[top[x]] > dep[top[y]]
? x = fa[top[x]] : y = fa[top[y]];
return dep[x] > dep[y] ? y : x;
}
struct node { int ls, rs, cnt, mn; } t[M*15];
int rt[N], ntot;
#define post(x) (t[x].mn = min (t[t[x].ls].mn, t[t[x].rs].mn))
void upd (int &x, int l, int r, int tar, int dt) {
if (!x) t[x = ++ntot] = { 0, 0, 0, INF };
if (l == r) { t[x].cnt += dt;
t[x].mn = t[x].cnt == gcnt[l] ? l : INF;
return; }
int mid = l + r >> 1;
tar <= mid ? upd (t[x].ls, l, mid, tar, dt)
: upd (t[x].rs, mid + 1, r, tar, dt);
post (x);
}
int merge (int p, int q, int l, int r) {
if (!p || !q) return p | q;
if (l == r) {
t[p].cnt += t[q].cnt;
t[p].mn = t[p].cnt == gcnt[l] ? l : INF;
return p;
}
int mid = l + r >> 1;
t[p].ls = merge (t[p].ls, t[q].ls, l, mid);
t[p].rs = merge (t[p].rs, t[q].rs, mid + 1, r);
post (p); return p;
}
void imple (int x, int fre) { int y;
for (int i = head[x]; i; i = e[i].nxt) {
if ((y = e[i].v) == fa[x]) continue;
imple (y, i);
rt[x] = merge (rt[x], rt[y], 1, m);
}
ans[fre>>1] = min (lmt, t[rt[x]].mn);
}
int main () {
/* MOCK NOIP 20220514 吴秋实 */
#ifdef LOCAL
freopen ("c.in", "r", stdin);
freopen ("c.out", "w", stdout);
#endif
read (n, m); t[0].mn = INF;
for (int i = 1; i < n; ++i)
read (x, y), add_e (x, y),
add_e (y, x);
dfs (1, 0); decomp (1, 1);
for (int i = 1; i <= m; ++i)
read (g[i].x, g[i].y, g[i].z),
++gcnt[g[i].z];
for (int i = 1; i <= m; ++i) {
x = g[i].x, y = g[i].y, z = g[i].z;
upd (rt[x], 1, m, z, 1),
upd (rt[y], 1, m, z, 1),
upd (rt[lca (x, y)], 1, m, z, -2);
}
lmt = 1; while (gcnt[lmt]) ++lmt;
imple (1, 0);
for (int i = 1; i < n; ++i)
print (ans[i]), newl;
return 0;
}
但这还不够，需要空间和时间的利用都更加高效的解法。实际上，对于固定的权值$w$，我们只关心所有权值为$w$的路径的交集，只有这些边的答案有可能是$w$。这就引申出一个经典问题：快速求解两条路径的边的交集。此处给出结论：设两条路径为$(x, y), (a, b)$，有$l_1=\operatorname{lca}(x, a), l_2=\operatorname{lca}(x, b), l_3=\operatorname{lca}(y,a), l_4=\operatorname{lca}(y, b)$，则取$l_{1, 2, 3, 4}$中深度最大的两个点，记作$u, v$。若$u \neq v$，则$(u, v)$即为路径交集；否则两条路径不存在交。可以通过分类讨论验证该结论。
接下来，我们优化答案的更新。假如我们求出所有权值为$w$的路径的交$(x, y)$。我们考虑尽可能不更新该路径上已经确定答案的边。定义$\operatorname{up}(x)$为在上一次访问（并在第一次访问时确定答案）后，在$x$的所有祖先节点中，已知还未确定答案的深度最小的节点编号。由此，我们可以“暴力”遍历$(x, \operatorname{lca}(x, y)), (y, \operatorname{lca}(x, y)$的节点，每次跳到$\operatorname{up}(x)$并尝试更新答案，同时尝试更新$\operatorname{up}(x)$。其本质上是只采用路径压缩的变种并查集，每次操作的均摊时间复杂度为$\Omega(\alpha(n))-\mathrm{O}(\log n)$。
求$\operatorname{lca}$时还可以使用欧拉序列配合RMQ在常数时间内求解，复杂度瓶颈转移到预处理ST表上（$\mathrm{O}(n \log n)-\mathrm{O}(1)$）。（实测比树剖LCA跑得慢
constexpr int N = 5e5 + 10, M = 2e6 + 10;
int n, m, x, y, z, ecnt = 1, head[N], tot;
int up[N], eid[N], dep[N], occ[N], log2s[N<<1];
vector <pint> g[M]; int st[N<<1][21];
array <int, 4> llst; int ans[N];
struct edge { int v, nxt; } e[N<<1];
inl void add_e (int x, int y) {
e[++ecnt] = { y, head[x] }, head[x] = ecnt; }
void dfs (int x, int fr) {
dep[x] = dep[fr] + 1, up[x] = fr;
st[++tot][0] = x;
occ[x] = tot; int y;
for (int i = head[x]; i; i = e[i].nxt) {
if ((y = e[i].v) == fr) continue;
dfs (y, x); eid[y] = i>>1;
st[++tot][0] = x;
}
}
int comp (int x, int y) {
return dep[x] > dep[y] ? y : x; }
void build_st () {
log2s[0] = -1;
for (int i = 1; i <= n<<1; ++i)
log2s[i] = log2s[i>>1] + 1;
for (int w = 1; (1<<w) < (n<<1); ++w)
for (int i = 1; i + (1<<w) - 1 <= n<<1; ++i)
st[i][w] = comp (st[i][w - 1], st[i + (1<<w-1)][w - 1]);
}
int lca (int x, int y) {
x = occ[x], y = occ[y];
if (x > y) swap (x, y);
int w = log2s[y - x + 1];
return comp (st[x][w], st[y - (1<<w) + 1][w]);
}
int main () {
/* */
read (n, m);
for (int i = 1; i < n; ++i)
read (x, y), add_e (x, y),
add_e (y, x);
for (int i = 1; i <= m; ++i)
read (x, y, z),
g[z].emplace_back (x, y);
dfs (1, 0); build_st ();
for (z = 1; z <= m + 1; ++z)
if (!g[z].size ()) {
for (x = 1; x < n; ++x)
if (!ans[x]) ans[x] = z;
break;
} else {
auto [p, q] = g[z].back ();
g[z].pop_back ();
for (const auto [x, y] : g[z]) {
llst = { lca (x, p), lca (x, q),
lca (y, p), lca (y, q) };
sort (all (llst), [] (int x, int y) {
return dep[x] > dep[y]; });
p = llst[0], q = llst[1];
if (p == q) break;
}
int l = lca (p, q);
while (dep[p] > dep[l]) {
if (!ans[eid[p]])
ans[eid[p]] = z;
x = up[p], up[p] = comp (up[p], l), p = x;
}
while (dep[q] > dep[l]) {
if (!ans[eid[q]])
ans[eid[q]] = z;
x = up[q], up[q] = comp (up[q], l), q = x;
}
}
for (int i = 1; i < n; ++i)
print (ans[i]), newl;
return 0;
}D – 石老板魂飞魄散
易得将同色连通块合并后仍然形成树形结构。对于每个连通块，以现存儿子的颜色为键值，记录每个颜色都有哪些儿子。更改颜色时，更新父亲的儿子信息即可，同时检查是否能合并儿子/被父亲合并。如果发生合并，启发式合并两个连通块记录儿子信息的数据结构。
实现时需要注意细节。例如，为了保证每个连通块编号的唯一性，采取其在树上深度最小的节点作为代表元素。使用并查集查询某个连通块实际的父亲的代表元素，并且回答题目中的询问；记录儿子信息时，为了达到均摊常数时间复杂度，可以使用哈希表和链表。（就这么简单
时间复杂度均摊$\mathrm{O}(m\log n)$或$\mathrm{O}(m \log^2 n)$，取决于使用的数据结构。
constexpr int N = 1e6 + 10;
int n, m, fa[N], x, y, z, a[N], opt;
vector <int> e[N], slst;
int rtfa, rep[N], sonc[N];
unordered_map <int, list <int>> conn[N];
list <int>::iterator b[N];
struct dsu {
int fa[N], siz[N];
inl void init (int n) {
for (int x = 1; x <= n; ++x)
fa[x] = x, siz[x] = 1;
}
int get (int x) { return fa[x] == x
? x : fa[x] = get (fa[x]); }
inl void merge (int x, int y) {
// ? 将x合并到y上。
x = get (x), y = get (y);
if (x == y) return;
if (siz[x] > siz[y])
rep[x] = rep[y], swap (x, y);
siz[y] += siz[x], fa[x] = y;
}
} d;
bool vis[N];
void span (int x) {
vis[x] = 1;
for (const int y : e[x])
if (a[y] == a[x] && !vis[y])
span (y), d.merge (y, x);
}
void insert (int bel, int x) {
conn[bel][a[x]].push_front (x);
b[x] = conn[bel][a[x]].begin ();
++sonc[bel];
}
void remove (int bel, int x) {
conn[bel][a[x]].erase (b[x]); --sonc[bel]; }
void merge (int rt, int rtfa) {
remove (rtfa, rt);
d.merge (rt, rtfa);
if (sonc[rt] > sonc[rtfa])
conn[rtfa].swap (conn[rt]);
for (const auto &[col, lst] : conn[rt])
for (const int id : lst)
insert (rtfa, id);
}
int main () {
/* MOCK NOIP 20220514 吴秋实 */
read (n, m); d.init (n);
for (x = 2; x <= n; ++x)
read (fa[x]),
e[fa[x]].push_back (x);
for (x = 1; x <= n; ++x)
read (a[x]);
for (x = 1; x <= n; ++x)
if (!vis[x]) rep[x] = x, span (x),
insert (rep[d.get (fa[x])], x);
for (int i = 1; i <= m; ++i) {
read (opt);
if (opt == 2) read (x),
print (d.siz[d.get (x)]), newl;
else {
read (x, y);
int rt = rep[d.get (x)];
if (fa[rt])
remove (rtfa = rep[d.get (fa[rt])], rt),
a[rt] = y, insert (rtfa, rt);
else a[rt] = y;
if (conn[rt].find (y) != conn[rt].end ()) {
slst.assign (all (conn[rt][y]));
conn[rt].erase (y);
sonc[rt] -= slst.size ();
for (const int son : slst)
merge (son, rt);
}
if (fa[rt] && a[rtfa] == y)
merge (rt, rtfa);
}
}
return 0;
}
发表回复