本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-10 12:31:31

如果质因数数量非常少，比如 $n \le 30$，那么我们就可以直接状压，把质因数是否出现压起来。设 $f(i, S, T)$ 表示前 $i$ 个人，一个选了状态 $j$，另一个选了 $k$ 的方案数。

很难不注意到刷表转移

$$ \begin{aligned} f(i, S \cup K_i, T) \gets f(i, S, T) \iff S\cup K_i \cap T = \arnothing \ f(i, S, T \cup K_i) \gets f(i, S, T) \iff T\cup K_i \cap S = \arnothing \end{aligned} $$

但是问题来了，$n \le 500$，我们连这玩意儿压都压不起来。

很难不注意到，一个数 $x$ 大于 $\sqrt x$ 的质因数最多只有一个。我们要让两个集合所选的质因数交空，实际上就是保证小因子交空的前提下，让大因子不同。

我们可以把每一个数分解，然后按大因子排序，也就是把相同的一段放在了一起。

这个大因子只有三种可能：给 $S$，给 $T$ 和都不给。

设 $g(i, S, T)$ 表示这个大因子不在 $T$ 中的方案数，也就是可以在 $S$ 中的方案数，那么 $g$ 的转移是类似的；同理，我们可以算出可能在 $T$ 中的方案数。

合并解时候，要容斥掉一个 $f(i, S, T)$，因为 $g$ 和 $h$ 都可以表示都不给的情况。

之前想过质因子状压的 idea，但是正是因为会让值域太小而没想到解决方案。这题真的不错。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-11 19:08:04

很多数数题听是听懂了，写也写完了，但是自己想是绝对想不出来的。

所以整理一下

错排

考虑 $f(i)$ 表示 $1$ 到 $n$ 的排列中错排的数量，那么对于第 $i$ 个数，我们要把它插入到前面 $1$ 到 $i - 1$ 个数中。

可以把它放到 $f(i - 1)$ 中的里，这是 $(i - 1) f(i - 1)$ 种方案；

也可以把它放到一个缺一错排里，也就是只有一个 $i$ 满足 $a_i = i$，这个的方案数是 $(i - 1)f(i - 2)$。

最终的转移就是 $f(i) = (i - 1)(f(i - 1) + f(i - 2))$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-12 15:18:28

一个点儿子形成的链，在整个树上只能是两种情况，要么是往上连接成一条链，要么是和儿子形成一条链。

考虑怎么实现。首先 DFS，所返回的是儿子剩下的那条链。我们把它放到 multiset 里头，每次加入的时候看里面有没有和它匹配的。如果没有就加入，否则就匹配掉。最后没匹配到的就返回。

注意 multiset.erase 不能直接删数，否则会全部删掉。要用 q.erase (q.find (x))。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-13 08:22:32

设 $g(i)$ 表示选出恰好 $i$ 个元素进行组合的方案数，$f(i)$ 表示选出至少 $i$ 各元素组合的方案数，那么有

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

有些时候 $f(i)$ 好计算，而 $g(i)$ 由于恰好的那个限制，不好计算，我们考虑怎么反推。

事实上，有

$$g(n) = \sum\limits_{i=0}^n {n \choose i}(-1)^{n-i}$$

这个用组合数的性质是好证的。

于是我们就可以将 $f(i)$ 转化为 $g(i)$，例题，也是我接触这玩意儿的第一道题是 P10596 集合计数。

$k$ 个元素已经确定了为交，这里有 $n \choose k$ 种方案，那么还剩下 $n - k$ 个数状态仍待确定。我们要把这 $n - k$ 个数划分为

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 13:32:23

轮廓线，做 P1896 和 P1879，把枚举整一列的状态优化到枚举点。

并且发现状态数并不一定是满的，可以用 map 或者 umap 优化掉

cf1209e2

另外有 sosdp，可以利用包含关系优化转移。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-18 15:36:26

7 月 18 日模拟赛

A

题目里头说 $S_i = 1$ 当且仅当 $i \equiv b \pmod m$，我们就知道一个串中如果两个 $1$ 的距离不是 $m$ 就肯定无解。场上没有理解这个充要条件，以为是必要，被捆爆了。

判完段内的无解，我们就把问题转化为了：对于每个 $S_i$ 有一个 $z_i$ 表示其第一个 $1$，这显然是小于 $m$ 的。我们于是建出 $[0, m)$ 的所有点，表示当前长度模掉 $m$ 的值。

对于每一个串，我们需要从 $b - z_i \bmod m$ 转移过来，然后转移到 $b - z_i + \lvert S\rvert\bmod m$。

于是问题就转化为了一条从 $0$ 到 $0$ 的欧拉回路。跑就完了。

B 跳蚤市场

题意：给定 $l_i, r_i, v_i$，对方可任取 $w_i\in [l_i, r_i]$，我们可以选一个集合 $S$，这之后 $v_i$ 被选中的概率是

$$\dfrac {w_i}{w_0 + \sum_S w_i}$$

我们要求最大化这个 $v_i$ 的总期望。

我们考虑如果选某个数 $j$ 更优，就说明

$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt \dfrac{\sum_S v_iw_i + v_jw_j}{\sum_S w_i + w_j}$$

整理一下得到

$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt v_j$$

非常美妙的柿子！我们于是得知，如果 $v_i$ 不能选，那么小于 $v_i$ 的所有肯定也不选；反之不一定。

因为值域小，我们可以用线段树二分来完成。

C 约会

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-21 16:15:04

$n\choose m$，从一个大小为 $n$ 的集合中选出 $m$ 个，不考虑选出顺序的方案数。

很明显，集合大小如果增加一，那么这个新元素要么选要么不选，即

$${n\choose m} = {n-1\choose m}+{n-1\choose m - 1}$$

插板法：

$n$ 个人，分成 $k$ 组的方案数量。

用插板法，相当于总共 $n - 1$ 个间隔中选出 $k$ 个，相邻两个间隔是一组，即 $n-1\choose k - 1$。

用 dp，设 $f(i, j)$ 为前 $i$ 个元素，分成 $j$ 组的方案数，有显然转移

$$f(i, j) = \sum\limits_{k=0}^{i-1} f(k, j - 1)$$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 19:49:53

ABD 都是基本题，加起来就打了 150 值得反省。

主要说一下 C 题。

$\mathcal{O}(nm\log V)$ 的做法是比较显然的。我们从最高位枚举就可以了。

注意这个做法的本质，就是我们不断的根据最高位将当前的边集合 $E$ 分为 $E_0$ 和 $E_1$。

如果 $E_0$ 就能让图连通，我们肯定是选 $E_0$ 的，并在这上面继续这个过程；否则，我们当前的边集仍然是 $E$。

我们的答案就是按照这个过程走得到的答案。

我们发现很难独立考虑新边对每一位的贡献。

考虑每一位

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-25 07:30:51

$n$ 个球，$m$ 个盒子，

盒相同，球相同，允许空

设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的方案数，有

$$f(i, j) = f(i - j, j) + f(i, j - 1)$$

由于球是不同的，所以我们不能单独考虑每个球的状态。这 $i$ 个球，要么每个都要放，也就是 $f(i - j, j)$，要么是至少一个不放，也就是 $f(i, j - 1)$。

最后答案是 $f(n, m)$。

盒相同，球相同，不许空

我们提前取出 $n$ 个球不放，于是方案数就是上一问的 $f(n - m, m)$。

盒相同，球不同，允许空

设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的放置

盒相同，球不同，不许空

盒不同，球相同，允许空

盒不同，球相同，不许空

盒不同，球不同，允许空

盒不同，球不同，不许空

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-26 19:55:03

我们可以用类似点边容斥的东西，也即点的贡献是正的，边的贡献是负的，然后统计区间和，即得到总贡献。

点的贡献是显然的，那么怎么统计边的贡献呢？

边的贡献，来源于开关状态的变化。

考虑在开关管辖大小上根号分治。我们设阈值 $B$，管辖小于 $B$ 的叫做小开关，否则叫做大开关。

开关之间只有三种：对小，对大和大带小。

小开关之间的贡献，可以枚举其管辖范围暴力算；大开关由于只有 $\dfrac N B$ 个，所以可以预处理出每个大开关和哪几个相邻，然后暴力统计就可以了；

小开关和大开关带起来就不一样了。一个大开关对的小开关数量可能很多，因此不能直接做。但是我们可以考虑从小开关那里算贡献。

小开关状态变化的时候，我们枚举了它管辖的所有点；这时候，如果这个管辖的点旁边是个大开关的话，我们就在这个大开关的贡献上加一，表示它状态翻转会增加一条边。

大概就是这样，细节好像不少，写一下。

估计可以到紫了。紫并不恐怖。

更新一下细节。

如果更新的是一个小点，我们就暴力扫它的管辖范围，然后看看构成了多少个新边。同时，如果某个点旁边是一个大开关，我们需要将这个大开关的贡献加上一。

否则如果更新的是大点，我们就先看和它相邻的所有大点，然后看小点维护出来的和它的贡献即可。