APIO

APIO2024

Day1-概率论

AGC060C

考虑拿出最左边和最右边两条链共 $2(n-1)$ 个点, 归并它们, 然后以钦定顺序得到一棵新树(合并成一条链), 于是设 $f_{i, j}$ 为左边链到第 $i$ 个右边到第 $j$ 个答案, 看起来贡献计算简单.

复杂度 $n^2$.

Pro

数据范围都是 $10^7$

首先原问题你直接就会了, 枚举最大值个数和最大值的值然后上一个二项式反演.

但是重点是怎么处理从最大值中等概率选一个这件事, 设最大值位置随机选一个选到 $1$, 问题相当于算 $\dfrac{P(x=1, a_1\ge r, sum_i a_i=s)}{P(a_1\ge r, sum_i=s)}=\dfrac{P(x=1, \max a_i\ge r, sum_i a_i=s)}{P(a_1\ge r, sum_i=s)}$, 发现此时分子对每个元素是等价的, 于是直接分子等于 $\dfrac{1}{p}P(\max a_i\ge r, \sum_i a_i=s)$, 剩下部分简单线性.

ARC150D

考虑每个点被选的次数之和, 先认为是从所有点中选且跳过不合法的, 那么对于一个点 $u$, 从根到 $u$ 上这 $d$ 个点每个点概率相等, 所以对于任意时刻这 $d$ 个点被选的期望次数相等, 于是只要求总次数, 然后设前 $i$ 个已经被选过(剩下的可能选过), 于是选到下一个的概率是 $\dfrac{1}{d-i}$

ABC270Ex

操作可以转化成, $T$ 时给一个位置 $i$ 打一个时间标记 $e_i=T$, 要求 $T-e_i\ge a_i$ 时可以结束. 则对于长度为考虑一个位置可以结束的限制就是 $\forall i$, $(T-a_i, T]$ 不能选 $i$.

考虑设答案PGF是 $F(x)=\sum_i p_ix^i$, 但问题是一个前缀 $1\ldots i$ 有若干可能成为结束的前缀, 所以容斥, 答案是 $\sum_{S, a_n\le s_1<s_2\ldots <s_n} (-1)^{S} \prod_i g_{s_i-s_{i-1}}$(看上一段的限制, 发现一段的答案只和长度相关, 且长度大于 $a_n$ 时都和 $a_n$ 一样).

于是写GF就好了:

$$
\begin{gathered}
Q(x)=\sum_i x^i g_i\
G(x)=Q(x)+g_{a_n}\dfrac{x^{a_n+1}}{1-x}\
F(x)=\dfrac{1}{1-x}-\dfrac{1}{1-x}\cdot g_{a_n}\dfrac{x^{a_n}}{1-x}\dfrac{1}{1+G(x)}\
F(1)
=\dfrac{1}{1-x}(1-\dfrac{g_{a_n}x^{a_n}}{1-x}\dfrac{1}{1+G(x)})\
=\dfrac{1}{1-x}(1-g_{a_n}x^{a_n}\dfrac{1}{(1+Q(x))(1-x)+g_{a_n}x^{a_n+1}})\
=\dfrac{1}{1-x}(\dfrac{(1+Q(1))(1-x)+g_{a_n}x^{a_n}(x-1)}{(1+Q(1))(1-x)+g_{a_n}x^{a_n+1}})\
=\dfrac{1+Q(1)-g_{a_n}}{g_{a_n}}
\end{gathered}
$$

注意只要算 $F(1)$, 则只要算 $g_{a_n}$ 和 $Q(1)$. 这两部分是平凡的.

但是这题有直接dp的做法啊! 发现对于任意状态, 答案只和 $s=\max a_i-b_i$ 有关, 然后调下顺序发现dp式子是线性递推就做完了.

ARC113F

考虑把概率拆分成 $f(m)$ 表示最小值大于等于 $m$ 的概率, 则对 $f$ 积分就是期望.

考虑求 $f$, 要求任意两个间距大于 $m$ 的概率, 相当于 $a_i-mi$ 递增的概率, 于是转化成有若干个区间, 每个变量在区间内均匀随机, 要求递增的概率, 则设二元函数 $g_i(m, x)$, 表示前 $i$ 个, 最后一个数值为 $x$ 的概率, 然后这个是关于 $m$ 有 $n^2$ 段, 关于 $x$ 有 $n$ 段的函数, 看起来可以直接维护!

qoj6413

todo

寻找图的包含至少一半边的二分子图

随机黑白染色. todo

Day1-组合计数

LOJ177 生成子群计数

考虑 $a_1=x$, 那么只考虑这个可以对每个置换 $p$ 让 $i\to p_i$ 连无向边(复合若干次一定能得到 $p^{-1}$ 所以有反向边), 于是一种复合方案对应一个 $1\to x$ 的路径, 而任意拿出图一个生成树, $1\to x$ 路径一定可以拆分成一个树上路径和一个经过 $1$ 的可能非简单圈(可能重复走边), 而对于一条非树边可以唯一确定一个简单环, 发现这些圈又可以由简单环生成, 把每个环依次复合应该可以得到一个首位是 $1$ 的排列, 而就要求这些排列任意复合的结果数, 于是问题到了 $n-1$ 规模.

但是直接做的话 $m$ 上升很快

[trick] $n$ 阶置换群最多取 $n$ 个排列使得不能各自复合出, 于是只保留 $n$ 个即可.

一个智慧法说的是随机 $n$ 种对当前 $k$ 个排列的复合方式, 把它们作为生成元做下去.

CF1909I

对每个 $m$ 分别做.

对 $k=n-1$ 的情况, 考虑把所有数按 $\min(i, m-i)$ 排序, 则有任意两个数和大于 $m$ 只取决于前面那个数的位置, 这个条件让你想到插入连续段的方式dp排列, 于是从小到大扫值, 一开始有 $t=1$ 空, 插入大于 $m$ 的数时 $T$ 每次加 $1$, 然后空交替减 $1$ 加 $1$, 而方案数就是过程中 $t$ 的乘积.

对 $k\ne n-1$ 的时候, 二项式反演, 钦定有 $i$ 个位置满足条件, 则剩下 $n-i$ 满足条件, 相当于最后插入出 $t$ 个连续段不需要合并. 然后需要再次容斥避免空段.

两个反演直接做复杂度是 $n^2$, 需要NTT加速是经典的, 最后复杂度 $n^2\log n$

CF1896H

令 $n$ 是题目中的 $2^n$

若要求两个串是好的, 即对每个循环为恰好相等的 $1$ 数量都少于 $\dfrac{n}{2}$(恰好相等的 $0$ 数量与 $1$ 相等).

用多项式刻画 $f$, 设 $A(x)=\sum_{i=0}^{2n-1} a_ix^i$, $B(x)=\sum_{i=0}^{2n-1} b_{2n-1-i} x^i$, $I(x)=\sum_{i=0}^{2n-1} x^i$, 则 $(a, b)$ 为好的当且仅当 $A(I-B)+B(I-A)=2^nI$, 即 $AB=2^{n-1}I$. 注意到右边DFT后为全 $0$, 则左边DFT后为全 $0$.

喵的啥? todo

CF1774G

先考虑一次怎么做

容斥, 钦定 $k$ 个关键点未被覆盖, 则一个区间包含至少一个关键点则不可选, 而若存在一个区间不包含关键点则这个区间变一下会更改区间数奇偶性, 对答案贡献 $0$, 所以变成要求每个区间包含至少一个关键点, 贡献 $(-1)^{k}$

于是考虑dp, 设 $f_i$ 为考虑 $1\ldots i$, $i$ 必须选的情况下, 前 $i$ 个的带系数方案和, 则 $f_i=\sum_{j\ge p_i} -f_j$, $p_i$ 为右端点小于 $i$ 的区间中左端点最大值. 因为是简单求和形式于是令 $s_i=\sum_{j=0}^i f_j$, 有 $s_i-s_{i-1}=-(s_{i-1}-s_{p_i-2})$, 即 $s_i=s_{p_i-2}$.

于是直接倍增处理每个 $i$ 往前跳的位置求 $s$ 即可处理多次询问.

CF1889E

考虑限制是, 若 $T_1$ 上 $e_1=(u, v)$, 若 $e_1$ 选则所有 $T_2$ 上的边 $e_2$ 满足 $u\to v$ 经过 $e_2$ 也要被选.

于是建立新图, 若存在限制”若选 $T_1$ 上 $e_1$ 则选 $T_2$ 上 $e_2$”则连边 $e_1\to e_2$, 然后缩点得到一个DAG, 每次可以选择一个点及其所有可达点交换. 而一次交换边集后, $e_1\to e_2$ 的边会反转成 $e_2\to e_1$, 但这种操作并不影响缩点结构. 发现我们可以得到DAG的任意局面, 即答案是 $2^{\text{SCC个数}}$, 然后需要特殊处理一些原边集和新边集完全相同的SCC, 换/不换是一种方案.

Qoj8049

见sdptt1

Qoj5016

考虑如果给定一个 $b$, 可以按值从小到大, 每次把当前值填入所有当前值能填的位置, 则可以唯一生成一个 $a$, 形成双射.

那么考虑这样的 $a$ 的特点, 对于 $a$ 一个极长的, 值 $\ge v$ 的段 $[l, r]$, 必然要满足所有被 $[l, r]$ 包含的区间的并恰好为 $[l, r]$, 于是预处理所有这样的区间, 然后dp设 $f_{l, r, i}$ 表示 $[l, r]$ 的值都要 $\ge i$ 的情况下对应合法 $a$ 数量, 转移考虑枚举 $i$ 第一次出现位置 $x$ 要求 $[l, x-1]$ 要求合法然后两边拼, 复杂度 $n^3c$

容易发现答案是 $n$ 次多项式, 于是拉格朗日插值做完了.

Qoj7759

考虑把 上升 和 上升段 对应起来, 显然若有 $c$ 个上升则有 $n-c$ 个极长上升段.

那么容斥, 钦定 $p, p^{-1}$ 排列分别有 $a, b$ 个上升段, 但这里容斥系数得用上升推(按照上升段的话, 真正的上升段可能是已有的上升段向两边延伸, 还可能合并等, 但按照上升推的话直接是二项式反演).

考虑从左到右加入 $p^{-1}$ 的上升段, 那么在 $p$ 中相当于按值域从小到大插入, 每个上升段会被填一个前缀. 容易发现若设 $a\times b$ 的矩阵 $w_{i, j}$ 表示插入 $p^{-1}$ 中第 $i$ 段上升段时在 $p$ 的第 $j$ 个上升段插入了 $w_{i, j}$ 个数, 则可以唯一确定排列 $p$, 而对 $w$ 的限制为, 不存在一行/一列全为 $0$ 且总和为 $n$.

于是只要数 $w$, 再二项式反演有 $i$ 行 $j$ 列全为 $0$ 即可.

复杂度 $n^3$

Agc061F

建模到图上, 相当于下标取模的情况下不能碰到重复点且最后回到原点.

令发生取模后到的点(左下角为 $(0, 0)$, 左边和下边上的点)为关键点, 则能对应出右上方边角处的点, 此时要数互不相交路径数, 想到LGV, 但发现此时可能会连出多个环. 然后分析出只有一个环当且仅当左边和下边上关键点数量互质.

于是问题变成有 $n+m$ 阶方阵, 前 $n$ 个表示下边, 后 $m$ 个表示左边, 则要求选 $k_1+k_2$ 阶子方阵, 其中 $k_1, k_2$ 分别为前 $n$ 个, 后 $m$ 个中选的行列数量, 要求 $\gcd(k_1, k_2)=1$.

于是在对角线前 $n$ 个元素加 $x$, 后 $m$ 个元素加 $y$, 行列式变成二元多项式最后提取系数就是答案, 插值做到 $n^5$, 特征多项式做到 $n^4$.

Contest

A

模拟.

B

赛时想了一个单根号但一直T, 赛后过了.

肯定考虑点边互换, 容易发现 $(u_i, v_i, a_i, b_i, c_i)$ 要想更新 $(u_j, v_j, a_j, b_j, c_j)$ 会满足 $a_i\lt b_i\lt a_j\lt b_j$, 于是可以扫时间去更新. 同时饭肯定尽量在车上吃, 所以设到第 $i$ 条边终点的花费为 $w_i$, 转移是 $w_j=w_i+c_j+\mathrm{cost}(b_i, c_j)\cdot T_{b_i}$, $\mathrm{cost}(l, r)$ 表示被 $l, r$ 完全包含的吃饭区间数量.

于是扫描线扫边的起点时间 $a$, 则每次会:

• 插入一条边, 即单点修改某个 $w_i$.
• 加入一个新的吃饭区间 $[l, r] (r\lt a)$ 的贡献, 即所有 $b_i<l$ 的区间 $\mathrm{cost}$ 值加一.
• 算当前边的答案, 即给定 $k$ 查 $\min_{b_i=k} w_i+\mathrm{cost}(b_i+c_j)T_{b_i}$.

没有 $k$ 的限制的话是KTT板子, 即可以把每个 $i$ 的贡献看成 $T_{b_i}x+w_i$ 的一次函数, 要支持单点修改和区间对函数平移, 查询最小值. 有的话看着很难Poly log考虑分块, 对序列分块, 仿照KTT对每个块维护每个 $k$ 的答案和这个块发生线段切换的时间, 单点修改直接重构, 区间加如果超过切换时间暴力重构, 就是对的.

诶但这个势能怎么分析? 显然对一个颜色, 答案关于平移的值 $x$ 是一个下凸壳, 最多有 $O(n)$ 段, 再发现每次修改都是把函数向下平移, 不可能露出新的段, 所以一个块最多切换 $\sqrt n$ 次, 复杂度 $n\sqrt n$.

如果可能向上平移呢? 相当于再支持删线段, 发现相当于每个线段有一个 $x<lim_i$ 的范围限制. 由上包络线结论切换次数仍然是线性的.

C

考虑exCRT, $i\to i+j$ 连边表示模 $i$ 余 $j$, 再加上一些随机化即可.

Day2-网络流

CF1662J

让 $(i, j)$ 向同行/同列所有比自己小的位置连边, 题目转化为选择 $n$ 个点使得不存在一个被选的点可以走一步/两步到另一个被选的点.

注意到你不会连续走两次横着/竖着的边, 于是实际上相当于不存在一个可以到另一个, 即选一个长 $n$ 的反链要求价值最大.

然后dilworth说的是不带权的情况, 你发现我把一个点直接复制点权份就是带权情况(若你可选这个点, 那么拆出来的点一定都可选, 所以一定一起选/不选), 于是变成带权最小链覆盖, 你发现就是最小链覆盖改改边权就结束了吧.

CF1630F

首先注意到图是偏序集, 二分图等价于不存在三元环, 于是每个点要么没有入度要么没有出度.

拆点, 令 $x, x’$ 分别表示 $x$ 被选入无入度集合或无出度集合. 若 $x\to y$($y\vert x$), 要求 $(x, x’), (x, y), (x’, y’), (x’, y)$ 不同时出现, 于是是最大独立集问题.

可以把边定向让它变成偏序集, 定向 $x’\to x, x\to y’, x\to y, x’\to y$, 于是求最小链覆盖.

CF1416F

一定会连成内向基环树, 环上点 $S$ 值必须一样, 其他位置父亲必须比自己小.

一个位置周围存在一个位置比自己小则可以在树上, 否则必须在环上.

发现一个大环不如若干个小环, 于是直接拆成若干个长度为 $2$ 的偶环, 于是成了求匹配.

这就能做了! 黑白染色, 若一个点必须在环上, 根据黑白连向S/T连 $[1, 1]$(流量上下界)的边, 否则连 $[0, 1]$, 就做完了.

CF513F2

考虑通配符没有用, 可以直接知道红蓝都有 $k$ 个.

二分答案, 考虑让红子匹配和它最后在一个点的蓝子, 于是每个红子连到能在时间内走到的点, 每个篮子能在时间内走到的点连到篮子, 而这些中间被走到的点拆成流量为 $1$ 的边即可.

CF1835F

图好是有完美匹配, 紧指对于图的一个完美匹配 $i\to p_i$, 集合 ${p_i\vert i\in S}$

CF1383F

最大流的局部性质不好, 考虑最小割, 考虑处理出 $2^k$ 种特殊边割掉的集合对应的其他边代价.

暴力跑流复杂度比较爆炸, 考虑先跑出一个解, 然后剩下每种状态都是在一个已有状态下加一条边, 加边复杂度是FF的 $O(mw)$, 总复杂度 $q2^k+2^kwm$

CF704D

容易想到网格图行列匹配的套路, 而数量相差不超过相当于限制这一行的红点个数在 $[l_i, r_i]$ 之间, 也就是流量限制, 然后根据 $r>d$ 还是 $r<d$ 做有源汇上下界可行最大流或最小流.

CF925F

上下界可行流可以通过补流转化成最大流, 存在可行解的条件是最大流满流, 满流的值是一个一次函数, 最大流可以转化到最小割, 最小割一定是关于 $t$ 的下凸分段一次函数.

Day3-构造

Eg. 1

n个点完全图划分成边集不交的生成树

之字形, 旋转

Eg. 2

2n个点划分成边集不交的匹配

一个点放中间, 对称着连, 旋转

Eg. 3

完全图边的排列, 使得任意连续 $n-1$ 条边是一棵生成树

奇数时, 用Eg. 1的做法, 发现可以做到把一个之字形逐条边的转化成一个旁边的之

偶数时, 用Eg. 2的做法, 相邻两个匹配是一个生成树, 发现也可以

. . .

不懂

试机赛T1

tocheck: 转化成后缀minmax段数上单侧递归线段树