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

洛谷5106 - dkw的lcm

积性函数的定义: 如果 $(a,b) = 1$ ,那么 $f(ab) = f(a) \times f(b)$ 。 显然欧拉函数是积性函数。

设 $lcm(i_1, i_2, …, i_k) = x$ ,我们把 $x$ 表示成 $x = \prod {p_i ^ {a_i}}$ 的形式。对每个 $p_i ^ { a_i }$ 分开考虑,枚举每个质数与幂次,用简单容斥统计出每个 $\varphi({p_i ^ {a_i}})$ 在答案中出现的次数,通过欧拉定理 + 快速幂计算答案。

假设我们当前枚举的质数为 $p^k$ ,我们把 $[1..n]$ 的数分成三个集合 $A, B, C$

  • 对于每个 $x \in A$ ,当且仅当 $p^k \not\mid x$;
  • 对于每个 $x \in B$ ,当且仅当 $p^k \mid x$ 且 $p^{k + 1} \not\mid x$ ;
  • 对于每个 $x \in C$ ,当且仅当 $p^{k+1} \mid x$。

则答案中 $\varphi({p^k})$ 的幂次相当于给 $k$ 个空位,只能放集合 $A$ 和 $B$ 中的元素且集合 $B$ 中的元素至少放一次的方案数,即 $(|A| + |B|)^k - |A|^k$,此处的值可能会超过 int 的存储范围,因而根据欧拉定理,对 $\varphi(10^9+7) $ (即 $ 10^9+6$ )取模。

洛谷5104 - 红包发红包

在 $[0,w]$ 中等概率取出的值的期望是 $\frac{1}{2} w$ ,简单观察可以发现,答案就是 $\frac{1}{2} ^ k$ ,快速幂一下就好了。

需要注意的是,根据欧拉定理,若 $p$ 是质数:
$$a^b \equiv a ^ {b \mod \varphi(p)} (\mod p)$$
所以这题如果你直接给 $k$ 模下 $p$ 就会挂啦 233.

20181211 - NOI模拟赛

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分,最多有 4320 种状态,我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分,相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上,计算割的价值就是一边的点的权值的异或和。考虑贪心,把点按照权值从大到小排序,利用线性基维护会不会产生 $0$ ,不会就加上价值,否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列,这样每次操作最多影响十棵树。树套树(树状数组套权值线段树)维护一个后缀高度大于指定值的 dp 值的最大值,每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

原问题等价于询问节点个数为 $ n $ 的完全二叉树形态的二叉堆的个数。

考虑递推,用 $ f(i) $ 表示 $ i $ 个节点时的答案。考虑除去此时的根节点外,根的左右子树大小分别为 $ l $ 和 $ r $ (可由完全二叉树这一性质计算得出)。此时根节点的编号肯定为 $ 1 $ ,而 $ f(l) $ 和 $ f(r) $ 分别是子树中的根节点编号为 $ 1 $ 的情况,若把编号分配,相当于求两个有序数列并成一个的方案数,即 $ C _ { l + r} ^ l $。得出:

$$ f(i) = f(l) \times f(r) \times C _ { l + r } ^ l $$

预处理阶乘递推即可。若 $ n > q $ 则需要卢卡斯定理简单处理。

这题的规律是很好找的,难的就是需要用高精度进行计算。

于是我…厚颜无耻地逃避了高精度,用 Python 打了个表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def locate(x):
a = [1, 3]
for i in range(2, x):
a.append(a[-1] + a[-2])
# print(a)
return a[x - 1]

def solve(x):
t = locate(x)
if x % 2 == 1:
return t ** 2
else:
return t ** 2 - 4

n = int(input())
print(solve(n))

线性基(洛谷3812)

线性基是一种解决异或相关问题的算法。

感谢 mwh 与我分享关于线性基的理解,让我了解线性基。

概念

线性基理论上来说是一种贪心的思路。一般情况下,我们需要从(二进制)高位到低位贪心,然而这样可能会产生其他影响(例如当前数的选择与否会影响到之前已选择的数)。线性基就巧妙的解决了这个问题。

假设我们已经有了一个集合 $S$ ,集合中有一数为 $P$ ,现在我们需要插入 $X$ ,则插入 $X$ 和插入 $ X xor P $ 是等价的,理性证明:

假设集合 $S$ 中任意个数其中包含 $P$ 的异或和的集合为 $S1$ ,不包含 $P$ 的为 $S2$ 。则插入 $X$ 后的 $S$ 中任意数的异或和集合 $S’ = X xor S1 + X xor S2$ ;插入 $X xor P$ 后 $S$ 中任意数的异或集合 $S’’ = (X xor P) xor S1 + (X xor P) xor S2 = X xor (P xor S1) + X xor (P xor S2) = X xor S2 + X xor S1$ 。所以 $S’ = S’’$ 插入 $X$ 和插入 $X xor P$ 等价,证毕。

高斯消元学习笔记

最近的模拟赛出现了一道坑爹的数学题,正解是上一篇博文所讲的数学插值。然而高斯消元还是可以拿到 65 分的成绩,没办法,凭借着我对其原理的依稀记忆我只能考场上手推高斯消元。

原理

高斯消元其实是个很简单的东西,无非就小学奥数的难度罢了。按照小学奥数的加减消元和代入消元即可完成。模板题给了你 n 个的 n 元一次多项式求解。我们可以通过加减消元合并为 n - 1 个 n - 1 元的一次多项式(合并相邻两个);于是,经过 n - 1 次合并我们就可以得到一个一元一次方程,可以很方便的得到解。我们再将解回代,即可解出方程。

给你平面上的 n 个点,可以唯一确定一个多项式。

现在告诉你这些点的坐标和 k ,请你求出多项式在 k 的取值。

思路

显然我们可以根据题意列出 n 个方程,利用高斯消元求解后带入。时间复杂度O(n ^ 3)

我们可以利用插值法求解并使得时间复杂度降至O(n ^ 2)

欧拉筛求质数

欧拉筛是一种优秀的筛质数方法。

Your browser is out-of-date!

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

×