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)$ 求解

100 篇文章纪念

memset0 的博文终于有 100 篇啦,要继续坚持下去哦…

(然后又偷偷从老博客里搬了几篇回来…)

与上一题类似,我们可以考虑生成函数。但是由于本题是 $\mod m$ 意义下的乘法,所以我们可以把原来的乘法转换为与 $m$ 的原根的对数的加法。再用上题目类似的思路即可。

定义生成函数 $f$ :

$$
f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i
$$

其中 $tag(i) = 1$ 当且仅当存在 $x \in S$ 使得 $\log_g x = i$ 。

最后答案为:

$$
[x^k]f^n(x)
$$

CF1096G - Lucky Tickets

一道生成函数板题,定义生成函数 $f$:
$$
f(x) = \sum\limits_{i=0}^{\infty} tag(i) \times x^i
$$

若集合中有 $i$ 则,$tag(i) = 1$ ;否则 $tag(i) = 0$ 。

则 $[x^i]f^n(x)$ 表示选 $n$ 项时和为 $i$ 的方案数。

容易发现答案即:

$$
\sum\limits_{i=0}^{\infty} ([x^i] f^n(x))^2
$$

多项式快速幂即可。

一道 bitset 傻逼题。随便乱搞一下就好了,跑的飞快。

考虑到原问题等价于以下行列式的值:

$$
第 i 行的 l_i 到 r_i 的值为 1 ,其他为 0 。
$$

我们采用高斯消元,复杂度 $O(n ^ 3)$ ,可以获得 70 pts.

考虑优化,由于 $1$ 的位置是连续的区间,采用左偏树维护每个左端点的右端点最小值即可。

注意行列式中交换两列,行列式的值取相反数;如果不能消成单位矩阵,则行列式的值为 $0$ 。

之前特别喜欢那种动态博客,因为它能够提供一种更加简洁直观的编辑页面,而不是像 Hexo 一样,要从一堆 .md 文件中找出自己需要编辑的那个。

当然, Hexo 下这个问题也不是无解,所以这篇文章就来简单的介绍下在 Hexo 的文章管理插件。

BZOJ5404 - party

和其他题解不太一样,这里没有用线段树……

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 $O(n ^ 2)$ 的,所以限制树链的长度至多为 $S$ ,则复杂度为:$O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32})$ ,取 $S = \sqrt n$ 。

然后跑的飞快 233333.

Your browser is out-of-date!

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

×