Blog
0%

PKUSC & PKUWC 2018 选解

发表于

Winter Camp Min-Max

题目大意

给定 $n$ 个节点的二叉树，给定叶节点的权值，非叶节点的权值有 $p$ 的概率为子节点的最大值，否则为子节点的最小值。

求根节点取到任意值的概率。

$1\le n\le 3\times 10^5$。

题解

考虑 DP，设 $f(i,j)$ 表示 $i$ 节点选到 $j$ 的概率，可以从子节点 $l,r$ 转移，有
$$
f(i,j)=f(l,j)\left(p_i\sum_{k=1}^{j-1}f(r,k)+(1-p_i)\sum^{m}_{k=j+1}f(r,k)\right)+f(r,j)\left(p_i\sum_{k=1}^{j-1}f(l,k)+(1-p_i)\sum^{m}_{k=j+1}f(l,k)\right)
$$
这样直接转移是 $\mathcal O(n^2)$ 的，考虑优化。

注意到这些和式都是前缀或后缀和的形式，显然可以在 DFS 的过程中用线段树合并优化，时间复杂度 $\mathcal{O}(n\log n)$。细节较多，可以参见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct SegmentTree {
	int ls[maxN << 5], rs[maxN << 5], tol;
	Z val[maxN << 5], mul[maxN << 5];
#define mid ((l + r) >> 1)
	void PushUp(int x) {
		val[x] = val[ls[x]] + val[rs[x]];
	}
	void Pushdown(int x) {
		if (mul[x].x == 1) return;
		if (ls[x]) mul[ls[x]] *= mul[x], val[ls[x]] *= mul[x];
		if (rs[x]) mul[rs[x]] *= mul[x], val[rs[x]] *= mul[x];
		mul[x] = 1;
	}
	void Update(int &x, int l, int r, int p, Z w) {
		if (!x) mul[x = ++tol] = 1;
		if (l == r) return val[x] = w, void();
		Pushdown(x);
		if (p <= mid) Update(ls[x], l, mid, p, w);
		else Update(rs[x], mid + 1, r, p, w);
		PushUp(x);
	}
	int Merge(int x, int y, int l, int r, Z wx, Z wy, Z w) {
		if (x + y == 0) return 0;
		if (x == 0) {
			mul[y] *= wy, val[y] *= wy;
			return y;
		}
		if (y == 0) {
			mul[x] *= wx, val[x] *= wx;
			return x;
		}
		Pushdown(x); Pushdown(y);
		Z lsx = val[ls[x]], rsx = val[rs[x]], lsy = val[ls[y]], rsy = val[rs[y]];
		ls[x] = Merge(ls[x], ls[y], l, mid, wx + (1 - w) * rsy, wy + (1 - w) * rsx, w);
		rs[x] = Merge(rs[x], rs[y], mid + 1, r, wx + w * lsy, wy + w * lsx, w);
		PushUp(x);
		return x;
	}
	Z Query(int x, int l, int r) {
		if (!x) return 0;
		if (l == r) return a[l] * val[x] * val[x] * l;
		Pushdown(x);
		return Query(ls[x], l, mid) + Query(rs[x], mid + 1, r);
	}
} st;
int n, m, son[maxN][2], cnt[maxN], rt[maxN];
void DFS(int x) {
	if (!cnt[x]) return st.Update(rt[x], 1, m, w[x].x, 1);
	DFS(son[x][0]);
	if (cnt[x] == 1) rt[x] = rt[son[x][0]];
	else DFS(son[x][1]), rt[x] = st.Merge(rt[son[x][0]], rt[son[x][1]], 1, m, 0, 0, w[x]);
}
int main() {
	std::vector<int> a(1);
	io >> n >> son[0][0];
	for (int i = 2, p; i <= n; i++) {
		io >> p;
		son[p][cnt[p]++] = i;
	}
	for (int i = 1, x; i <= n; i++) io >> x, w[i] = x;
	for (int i = 1; i <= n; i++) {
		if (cnt[i] > 0) w[i] *= 796898467;
		else a.emplace_back(w[i].x);
	}
	std::sort(a.begin(), a.end());
	m = a.size() - 1;
	for (int i = 1; i <= n; i++)
		if (cnt[i] == 0) w[i] = std::lower_bound(a.begin(), a.end(), w[i].x) - a.begin();
	DFS(1);
	io << st.Query(rt[1], 1, m).x;
	return 0;
}

Winter Camp 随机游走

题目大意

给定 $n$ 个节点的树，$Q$ 次询问，每次给出一个点集 $S$，求从 $x$ 出发随机游走经过点集中的所有点的期望步数。

$n\le 18$，$Q\le 5\times 10^3$。

题解

首先注意到，题目要求经过所有点，不妨考虑 min-max 容斥，即转化为至少经过一个点的期望步数，有
$$
E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T))
$$
转化后，考虑 DP，设 $f(S,u)$ 表示从 $u$ 出发，经过 $S$ 中至少一个点的期望步数，显然当 $u\in S$ 时，$f(S,u)=0$。当 $u\notin S$ 时，有转移
$$
f(S,u)=\frac{1}{d_u}\left(f(S,fa_u)+\sum_{v\in son(u)}f(S,v)\right)+1
$$
其中 $d_u$ 表示点 $u$ 的度数。

显然这个 DP 有后效性，可以高斯消元解决。但这是一个树上问题，考虑从父亲转移到儿子，设 $f(u)=a_uf(fa_u)+b_u$（将 $f(S,u)$ 简写成 $f(u)$，下同），带入上式可得
$$
\begin{aligned}
f(u)&=\frac 1{d_u}\left(f(fa_u)+\sum_{v\in son(u)}a_vf(u)+b_v\right)\\
&=\frac 1{d_u}\left(f(fa_u)+\text{sum}a_uf(u)+\text{sum}b_u\right)
\end{aligned}
$$
把未知项移到左边，有
$$
(d_u-\text{sum}a_u)f(u)=f(fa_u)+\text{sum}b_u
$$
整理得到
$$
f(u)=\frac{1}{d_u-\text{sum}a_u}f(fa_u)+\frac{\text{sum}b_u}{d_u-\text{sum}a_u}
$$
即
$$
a_u=\frac{1}{d_u-\text{sum}a_u}\quad b_u=\frac{\text{sum}b_u}{d_u-\text{sum}a_u}
$$
答案 $f(x)$ 不能从父亲转移，即 $f(x)=b_x$。

这部分的时间复杂度为 $\mathcal{O}(2^nn\log \bmod)$。

至此，我们求得了 $(-1)^{|T|+1}\min(T)$，接下来的问题即求子集和，可以直接对 $f$ 做一次 FWT，即可做到 $\mathcal{O}(1)$ 查询。

Tip：为什么这样做是对的？

考虑或卷积 $c_i=\sum_{i=j|k}a_jb_k$

设 $\hat a=\mathcal F a$ 表示 $a$ 的 FWT，根据或卷积的 FWT 为乘积，得到 $\hat c_i=\hat a_i\hat b_i$。而或运算相当于子集求并，则 $i$ 的子集都会对 $\hat a_i$ 产生贡献，即 $\hat a_i=\sum_{j\subseteq i}a_j$

总时间复杂度为 $\mathcal{O}(2^nn\log \bmod+\sum |S|)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n, Q, rt;
io >> n >> Q >> rt; rt--;
std::vector<std::vector<int>> e(n);
std::vector<int> deg(n);
std::vector<Z> f(1 << n);
for (int i = 1, u, v; i < n; ++i) {
	io >> u >> v; --u; --v;
	++deg[u]; ++deg[v];
	e[u].push_back(v);
	e[v].push_back(u);
}
for (int s = 0; s < (1 << n); ++s) {
	std::vector<Z> a(n), b(n);
	std::function<void(int, int)> DFS = [&](int u, int fa) {
		if (s >> u & 1) return;
		Z _a, _b = 0;
		for (auto v : e[u]) {
			if (v == fa) continue;
			DFS(v, u);
			_a += a[v], _b += b[v];
		}
		a[u] = Z(1) / (Z(deg[u]) - _a);
		b[u] = a[u] * (Z(_b) + deg[u]);
	};
	DFS(rt, -1);
	if (__builtin_popcount(s) & 1) f[s] += b[rt];
	else f[s] -= b[rt];
}
for (int i = 0; i < n; ++i)
	for (int j = 0; j < (1 << n); j += (1 << (i + 1)))
		for (int k = 0; k < (1 << i); ++k)
			f[j | k | (1 << i)] += f[j | k];
for (int k, u; Q--;) {
	int s = 0;
	for (io >> k; k--;) {
		io >> u;
		s |= (1 << (u - 1));
	}
	io << f[s].x << "\\n";
}
return 0;

Winter Camp 猎人杀

题目大意

有 $n$ 个猎人，第 $i$ 个人的权值为 $w_i$，依次对猎人射击，第 $i$ 个人被击杀的概率是 $\frac{w_i}{\sum_{k\in S}w_k}$，其中 $S$ 表示当前存活猎人的集合。

求 $n-1$ 次射杀后，一号猎人存活的概率。

$\sum w\le 10^5$。

题解

考虑一次射击时假定所有人都活着，一直打，直到打到了确实活的人为止，这样做显然对最终的答案没有影响（活人之间的概率比没有改变）。

则考虑容斥，设 $f(S)$ 表示 $S$ 中的人都死在 $1$ 之后的概率，即开无限枪，不能打到 $S\cup\{1\}$ 中的人，直到打到 $1$ 为止。则
$$
f(S)=\sum_{i\ge 0}\left(\frac{\sum_{k\in (U\setminus (S\cup\{1\}))}w_k}{\sum w}\right)^i\frac{w_1}{\sum w}
$$
根据等比数列求和公式，得到
$$
f(S)=\frac{1-\lim\limits_{x\to \infty}\left(\frac{\sum_{k\in (U\setminus (S\cup\{1\}))}w_k}{\sum w}\right)^x}{1-\frac{\sum_{k\in (U\setminus (S\cup\{1\}))}w_k}{\sum w}}\frac{w_1}{\sum w}=\frac{1}{\frac{\sum_{k\in (S\cup\{1\})}w_k}{\sum w}}\frac{w_1}{\sum w}=\frac{w_1}{\sum_{k\in (S\cup\{1\})}w_k}
$$
则答案为
$$
\sum_{S\subseteq U\setminus\{1\}}(-1)^{|S|}\frac{w_1}{\sum_{k\in (S\cup\{1\})}w_k}
$$
注意到数据范围中限制了 $\sum w$，考虑枚举这个东西，即求
$$
\sum_{i=0}^{\sum w-w_1}\frac{w_1}{i+w_1}\sum_{\sum_{k\in S}w_k=i}(-1)^{|S|}
$$
右半部分是非常棘手的，但理智分析一下可以发现，右边的和式即
$$
[x^i]\prod_{i=2}^n 1-x^{w_i}
$$
感性理解一下，对于奇数个元素的集合，其对答案的贡献是 $-1$，而奇数个 $-x$ 相乘，其系数也为 $-1$，偶数同理。

至此，这个积式可以分治加 NTT 在 $\mathcal O(n\log ^2n)$ 求得，总时间复杂度为 $\mathcal O(n+\sum w\log^2\sum w)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
io >> n;
std::vector<int> w(n + 1);
for (int i = 1; i <= n; i++) io >> w[i];
std::function<Poly(int, int)> Solve= [&](int l, int r) -> Poly {
	if (l == r) {
		Poly _(w[l] + 1);
		_[0] = 1; _[w[l]] = P - 1;
		return _;
	}
	int mid = (l + r) >> 1;
	Poly a = Solve(l, mid), b = Solve(mid + 1, r);
	return a * b;
};
Poly f = Solve(2, n);
int s = std::accumulate(w.begin(), wend(), 0);
Z ans = 1;
for (int i = 1; i <= s; ++i) ans += f[i] * w[1] / (w[1] + i);
io << ans.x;
return 0;

Summer Camp 神仙的游戏

题目大意

给定由 $\texttt{0 1 ?}$ 组成的字符串 $s$，$\texttt{?}$ 可以任意替换成 $\texttt{0}$ 或 $\texttt{1}$。求在替换过后，$\forall i\in [1,n]$，长度为 $i$ 的前缀能否成为 border。

$|s|\le 5\times 10^5$。

题解

一个长度为 $p$ 的前缀为 border $\iff \forall[1,p],s_i=s_{|s|-p+i}\iff \forall i,j\in [1,n]\land i\equiv j\pmod{n-p},s_i=s_j\iff \forall i,j\in [1,n]\land |i-j|\ |n-p, s_i=s_j$