洛谷4841 - 城市规划

想 LJC00118 NOIP 考前就秒切了这题,memset0 又又又被吊打.jpg

考虑有标号无向图的生成函数:$f(x) = \sum\limits_{i=0}^{\infty} 2^{n \choose i} \frac{x^n}{n!} $。

考虑有标号无向联通图的生成函数 $g(x)$ ,容易证明 $exp(g(x)) = f(x)$ 。

此题需求 $g(x)$ ,那么直接多项式 $\ln$ 即可。

AT2064 - Many Easy Problems

容斥可得:

$$
ans_k = n {n \choose k} - \sum\limits_{u=1}^n ({n - siz_u\choose k} + \sum\limits_{v \in son_u} {siz_v \choose k})
$$

NTT 一波即可。

设 $P(S)$ 为钦点 $S$ 中所有元素都在 1 之后挂掉的概率,显然:

$$
P(s) = \frac{a_1}{sum(S) + a_1}
$$

于是我们可以发现最后答案为:

$$
ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}
$$

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = $+\infty$ qwq!

考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

同理可 Min-Max 容斥:

$$
\min(S) = \frac{1}{1 - \sum\limits_{S’ \subseteq S} \sum\limits_{u \in S’} p_u}
$$

FWT 一波即可。

HDU4336 - Card Collector

考虑 Min-Max 容斥。用 $\min(S)$ 表示 $S$ 中出现至少一个元素的期望时间,用 $\max(S)$ 表示 $S$ 中每一个元素都出现的期望时间。

则:

$$
\begin{aligned}
\min(S) &= \frac{1}{\sum\limits_{i \in S} p_i} \\
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

答案显然是让我们求 $\max(\texttt{全集})$ ,故状压一下即可。

Min-Max 容斥学习笔记

感谢 lyc 哥哥上次给我讲了一下…然而我并没有听懂,只能自己再去学了一遍

Min-Max 容斥:

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
$$

可以用二项式反演证明:构造容斥函数 $f(x)$ 使得

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|)
$$

考虑每个 $S’ \subseteq S$ 中 $\min(S’) = a_{x+1}$ 对答案的贡献为:

$$
g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)
$$

二项式反演得:

$$
\begin{aligned}
f(x + 1) &= \sum\limits_{i=0}^x (-1)^{x-i} {x \choose i} g(i) \\
\Rightarrow \ \ \ f(x + 1) &= (-1)^{x} \\
\Rightarrow \ \ \ f(x) &= (-1)^{x-1}
\end{aligned}
$$

所以:

$$
\begin{aligned}
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|) \\
&= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

二项式反演学习笔记

二项式反演:

$$
\begin{aligned}
f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i
\\
f_n=\sum_{i=0}^{n}{n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}
$$

BZOJ2839 - 集合计数

设 $a(i)$ 表示大于等于 $i$ 的方案数,则:

$$
a(i) = {n \choose i} (2^{2^{n-i}}-1)
$$

设 $f(i)$ 表示容斥系数,使得:

$$
ans = \sum\limits_{i=0}^n f(i) \times a(i)
$$

考虑单个集合并为 $x$ 的选取方案对 $ans$ 的贡献,设:

$$
g(x) = [ x = k ]
$$

则:

$$
g(x) = \sum\limits_{i=0}^x {x \choose i} f(i)
$$

二项式反演得:

$$
\begin{aligned}
f(x) &= \sum\limits_{i=0}^x {x \choose i} (-1)^{x-i} g(x) \\
&= {x \choose k} (-1)^{x-k} [x \ge k]
\end{aligned}
$$

代入得:

$$
\begin{aligned}
ans &= \sum\limits_{i=0}^n f(i) \times a(i) \\
&= \sum\limits_{i=0}^n {i \choose k} (-1)^{i-k} [i \ge k]
\times {n \choose i} (2^{2^{n-i}} - 1) \\
&= \sum\limits_{i=k}^n (-1)^{i-k} (2^{2^{n-i}} - 1) {i \choose k} {n \choose i}
\end{aligned}
$$

即可 $O(n \log n)$ 求解

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×