NOIWC
NOIWC2024
Day1-lxl
基础知识
部分持久化, 完全持久化, 可合并的持久化: 只能在最后一个版本改/可以在任意版本改/可以合并历史版本, 版本之间连有向边分别是链, 树, 图
离线建操作树可以解决完全持久化
实现可持久化的三种方式: 路径复制, 肥节点和节点分裂. 设修改和查询次数分别为 $m_1$ 和 $m_2$
路径复制类似主席树状物
可以支持可合并的持久化
肥节点
对每个节点用可持久化数组记录不同时间的版本, 查询时在这个节点的版本序列上二分, 可以实现部分可持久化, veb可以平衡到 $(m_1, m_2)\log \log m_1$
对于完全可持久化, 考虑版本树的括号序, 相当于可以插入一对括号和在括号序列上二分, 查询某个版本的值这三个操作, 因为有二分要求插入log查询 $O(1)$, 方法是开重量平衡树(深度 $\log n$, 每次调整 $\log n$ 个点), 每个点维护值域区间, 父亲区间 $[l, r]$ 则两个儿子分别是 $[l, mid]$ 和 $[mid+1, r]$, 另一个点的标号为 $\dfrac{l+r}{2}$, 则修改时修改区间和标号, 查询时只要比较两个点的标号. 平衡树treap/替罪羊即可.
感觉就是如何在不打标记的情况下解决平衡树在有key的情况下动态插入点.
另一种解决刚才的问题的方案是一个链表, 每次插入元素取前驱后继平均值比较标号, 复杂度 $O(1)-O(1)$, 但是精度要求节点数不超过 $O(w)$, 嵌套 $O(1)$ 层复杂度 $O(w^{O(1)})$, 于是把序列按 $B$ 分块, 块间平衡树块内用刚才链表的方法去一个log.
感觉还挺问号, 再想想.
节点分裂
就是, 一种波尔方式是直接可持久化数组记录所有指针
然后它每 $w$ 个版本分一块, 每次改边的时候只把边指向对面的节点版本所在块, 每次新增块的时候修改连向当前块的点们, 给它们增加一个修改操作
可持久化平衡树
除了splay, 都行/cf
替罪羊树可以部分持久化(均摊)
其他的都可以完全持久化
可合并持久化的平衡树
这里定义合并是序列拼接
可以用路径复制实现平衡树的分裂合并, 于是可以支持区间复制
但是复杂度仍然是 $\log len$, 于是受限
treap的合并可持久化: 不能存随机值否则反复复制一个点随机值是一样的, 于是按子树大小随机就行了, 复杂度未知反正没人会卡
P8263 [Ynoi Easy Round 2020] TEST_8
倍增合并, treap显然复杂度是 $\log^2 n$ 的, 过不了, 但是WBLT合并大小为 $a, b$ 的树复杂度是 $\log \dfrac{a}{b}$. 于是复杂度变为单log
P8524 [Ynoi2078] <A theory of consciousness from a theoretical computer sciencepers
直接做的化, 用可合并持久化平衡树, 然后对除以 $2$ 维护每个数除了 $1, 2, \ldots$ 次的 $\log n$ 个数, 就复杂度单log\了.
然而空间俩log爆炸了, 考虑因为我们不需要维护之前的版本于是直接每 $\dfrac{n}{\log n}$ 次重构, 或者直接智能指针就做完了.
CF702F T-Shirts
设 $f_{i, j}$ 为从 $i$ 开始往后走有 $j$ 元最后的答案, 转移发现是区间复制和区间加, 结束啦.
Hdu5118 Gre Words Once More
同上, 可持久化平衡树的区间复制维护dp
DAG链剖分!
树套可持久化平衡树
可持久化作为标记: BZOJ3946
开两个可持久化平衡树分别维护当前节点所有字符串都被加了序列 $s$ 和当前节点序列的lcp序列 $t$, 下传直接区间复制, 于是外层线段树序列, 查询在内层多个持久化平衡树二分. 复杂度 $q\log^3 n$
可以优化到俩log, 考虑差分, 维护相邻两个字符串的lcp长度, 答案就是区间 $\min$, 仍然用上面方法维护字符串, 每次修改只需要重新计算边界的 $f$, 中间的是区间加.
可持久化作为信息: CF1340F Nasty and CBs
可持久化平衡树维护区间括号hash, 合并就是区间查询相等和区间拼接拆分
可持久化可并堆
斜二项堆介绍. . .
BZOJ3489
强制在线
每个数贡献一个区间, 变成了二维平面上矩形取max单点求值, 于是可以线段树套堆给它可持久化掉
Luogu7651
考虑对单个点求直接持久化线段树扫描线就行, 求前 $k$ 近就不断删最小的即可.
Day1-xtq
不听了
Day1-营员交流内容
浅谈一种互质数对与最大公约数的维护算法
算法
互质数对与最大公约数的维护算法?
$P(x)$ 为 $x$ 最大质因子
基本解决问题是, 要求初始全为 $0$ 的序列 $a_n$, 要求你进行 $m$ 次修改, 使得对于任意 $i\in [1, n]$ 存在时刻 $t$ 满足 $\forall j, b_j=[i \perp j]/\gcd(i, j)$, 应用类似莫队的一个玩意.
基本思想是拆贡献, $[i\perp j]=1-[\exists p\ne 1, p\vert i, p\vert j]$, $\gcd(i, j)=\prod_p p^c [p^c\vert i, j][p^{c+1}\not \vert i, j]$
于是直接爆搜决定 $p$, 对于互质的情况, dfs状态为 $(i, x)$ 表示小于 $x$ 的部分决定乘上的乘积为 $i$, 当前要决定 $p_x$ 是否被乘上. 当乘上素数 $p_x$ 的时候把 $p_x$ 的倍数 $a_j(j=kp_x)$ 设为 $0$, 回溯时撤销, 当 $ip>n$ 的时候直接退出, 得到一个爆搜算法. 正确性显然.
对于 $gcd$ 的情况一样爆搜, 只不过对 $p$ 应该枚举 $c$ 表示 $p$ 的次数, 剩下的完全一样.
对于复杂度显然两个复杂度都低于 $\sum_i \dfrac{n}{P(i)}\approx n\sqrt n$(在 $10^6$ 附近, 只维护互质对的情况常数较小)
例题
给定 $a_n$, $q$ 次给定 $l, r, x$ 询问 ${a_{\gcd(x, i)}, i\in[l, r]}$ 的最大子段和.
直接用上面的方法转化成单点改区间最大子段和即可. 复杂度 $n\sqrt n\log n$
浅谈一些信息合并的处理方式
典
无旋treap带值域交合并
基本就是, 要合并两棵树, 考虑两个根节点 $a, b$, 设 $a$ 的优先级高(作为根), 则把 $b$ 按 $a$ 的权值分裂, 左右递归下去.
线段树合并卡空间
线性拟阵奇偶
啥玩意? ? ? ? ? ?
浅谈静态数据结构的合并与分裂
点分树, 边分树合并, 静态toptree合并
点分树先建哈夫曼树二度化, 然后两个都直接照抄线段树合并即可.
静态toptree深度也是 $\log n$ 的, 现在要合并 $u\to v$ 的链, 要分情况讨论:
- $u, v$ 有祖先关系
- $u, v$ 无祖先关系
- $u, v$ 分别在重儿子左右的两个 rake tree 上.
- $u, v$ 其中一个是重儿子, 即不在 rake tree 上.
- $u, v$ 在同一个rake tree 上
要处理一个叶子和一个子树的合并, 维护簇界点之间路径的标记和簇其他部分的标记.
点分树, 边分树, toptree分裂
点分树, 边分树因为到重心这一信息的不可分裂性通常不能分裂, 能分裂当且仅当信息可以分裂, 如信息是线段树用线段树分裂
toptree按子树分裂: 设关于 $u$ 分裂, $u$ 的子树表现为compress tree在他右侧的点, 以及这些点的rake tree, 那直接对它所在compress tree分裂是简单的, 对自己所在的rake tree把自己分出来也只要 $O(\log n)$ 的修改量, 于是就分裂了.
对于链的分裂, 他说只用compress的双层toptree, 感觉是直接造了一个leafy的全局平衡二叉树/cf, 而全局平衡二叉树拿走一条链是简单的.
范围修改查询问题相关算法及其应用
线段树能维护修改和区间信息都为半群的问题
lxl的离线范围修改查询算法
问题描述为给定若干点, 若干次针对某个集合的修改和查询, 都是半群信息
定义等价关系为两个点所属的修改和查询集合相同. 由此定义出等价类. 定义一个划分 $R_{l, r}$ 为仅考虑 $[l, r]$ 中的修改查询得出的等价类集合的集合.
考虑维护有根森林, 即每个叶子为原问题中的点, 一个等价类为一棵子树, 每个节点子树和, 子树修改标记, 合并等价类就是建一个父亲把等价类挂上去, 拆分就是把父亲删掉并下传修改标记, 而可以用这种方式在不同的 $R_{l, r}$ 划分之间移动. 假设现在要处理 $R_{l, r}$ 这个问题, 先移动森林状态到 $R_{l, mid}$ 递归, 再移动到 $R_{mid+1, r}$ 递归即可.
然后设 $F(x)$ 是 $x$ 个操作最多可以把点分成多少等价类, $B$ 是最大的 $x$ 满足 $F(x)\le n$, 于是可以 $B$ 个操作分一块, 复杂度 $T(n, m)=\dfrac{m}{B}T_1(B), T_1(n)=2T_1(\dfrac{n}{2})+O(F(n))$, 对于半平米, 圆可以做到 $m\sqrt n$, 对任意集合可以做到 $\dfrac{nm}{\log n}$, 对序列可以 $m\log n$
分块旋转扫描线
略
浅谈一类树上范围相关问题
树剖
理解为树上链分治结构
单点询问, 树链距离 $d$ 以内的点加. 范围都是 $10^5$
重链剖分, 考虑一次操作的影响, 发现会对重链上的区间的点的轻子树作前 $d$ 层加, 此外端点处有对当前点的子树前 $d$ 层加或向祖先方向的前 $d$ 层加.
那么后两种都相当于给定 $u$, 对范围内点 $v$ 加 $d-dis(u, v)$, 于是能做了: 用树套树维护标记, 查询时要查到根的路径上每个链头的标记, 子树内点的标记, 祖先点的标记三种, 直接做3log, 把树剖换成全局平衡二叉树是2log.
毛毛虫剖分
对一条链距离为 $d$ 以内的点加, 对一条链距离为 $d$ 以内的点求和, 子树加子树和链加链和.
$d$ 为常数且 $d\le 3$
原来只见过距离为 $1$ 的毛毛虫剖分, 不过容易发现扩展是平凡的, 假设距离为 $d$, 要给当前重链标号, 自然先给重链标号, 再给挂在当前重链的所有轻儿子的前 $d$ 级后代标号, 再递归下去, 则每条链只有前 $d$ 个标号不连续. $d$ 一般很小不然复杂度就爆了.
点分树维护传递性问题
$n$ 点树, 一开始均未激活, 若 $i$ 激活会激活距离 $r_i$ 以内的点, $q$ 次询问激活一点后被激活点的点权和.
todo
Toptree: P8498 树上邻域数点
建toptree, 设 $f_{u, 0/1, d}$ 表示距离簇 $u$ 内距离左/右界点 $d$ 以内的信息, $g_{u, 0/1, d}$ 表示簇 $u$ 外距离左/右界点距离为 $d$ 以内的点的信息, 则询问 $u$ 时, 找到任意一条边 $u, v$, 然后找到最浅的完全被询问的区域包含的簇 $x$, 则答案就是 $x$ 的两个界点各向外一部分以及簇 $x$ 自身合并出来的, 于是可以先把自身和一个端点的合起来, 查询时只需要一次.
问题变成如何求 $f$ 和 $g$, $f$ 根据 $f$ 的定义显然可以直接用rake和compress得到, 而 $g$ 考虑对簇换根, 假设现在祖先的 $g$ 已经求出, 则簇 $u$ 的内容就是父亲的 $g$ 和兄弟的 $f$ 的合并.
$f$ 的 $d$ 只要开到簇路径长度, $g$ 的 $d$ 只要开到父亲的簇路径长度, 总复杂度 $n\log n$
Day2-qlr
CF1753C
nfls里面有
Yogyakarta Elevators
考虑 $m$ 很小, 而且图的边集是若干团, 于是考虑线图把点边互换, 以电梯为点, 每个楼把所有经过这个楼的电梯连起来, 于是一个区间连通的条件是只保留这个区间中的边只有一个不为单点的连通块.
然后直接枚举 $r$, 从大到小加 $[1, r]$ 之间的楼的边, 我们只关心连通性变化, 于是不断加边的过程中一共只有 $O(m)$ 种本质不同的情况, 总复杂度 $nm\alpha(n)$.
如何做到只枚举这 $O(m)$ 种情况? 每次加的边是图的最大生成树, 于是只要从小到大加边不断维护最大生成树即可(树只有 $m$ 个点)
CF1753D
对这种题想到看成格子移动的模型, 则对每个砖块 $(a, b), (a, b+1)$, 连边 $(a, b-1)\to (a, b+1), (a, b)\to (a+1, b+1), (a, b)\to (a-1, b+1)$, 各个方向连起来, 跑最短路即可. 注意到黑白染色黑白格独立, 找两个相邻格子最短路相加就是答案.
然后为什么是对的, 即证明一个格子不会移动两次, 若出现过这种情况, 则一定存在某个时刻它已经空出这个位置, 就不会有后面的移动了.
CF1750F
见count
ARC148D
考虑 $2n$ 为偶数, 所以最后两布一定是ALice先Bob后, 于是若最后两个数 $x, y$ 满足 $y-x\ne x-y$ 即 $2x\ne 2y$ 不相等Alice的两种方案总能赢一个, 于是最后两个数相等, 那么照着归纳, 假设已经有最后 $2k$ 步必须 $2x=2y$ 的数可以匹配, 则对于倒数 $2k+1$ 和 $2k+2$ 两个数, 显然如果不相等则交换这两个数的情况就不一样了, 于是Bob想获胜必然满足开始状态可以一一配对, 每对满足 $2a=2b\pmod M$.
而当前所有数都满足之后, 直接模拟, 看最后会得到 $\dfrac{M}{2}$ 或 $0$ 即可, 做完了.
ARC151E
注意不能删成空
则发现如果没有公共子串那么先转到它一定是最优的, sam即可
如果没有相当于先删到一个字符, 然后不断变成另一个字符变到 $Y$ 有的最后再变回去, 那就是相邻两字符连边跑最短路.
BJOI2018 染色
容易发现奇环无解, 现在是二分图.
容易把连通块分别判断, 同时一度点不影响任何事, 现在是无一度点的连通图.
然后现在一个连通块应该有一些环, 发现对于一个长 $n$ 的偶环我们可以确定其上的 $n-2$ 个点, 选一条长 $n-2$ 的链全放 ${1, 2}$, 剩下两个点放 ${1, 3}$ 和 ${2, 3}$, 设链与 ${1, 3}$ 相连的头为 $u$, 则容易发现 $u$ 若选 $1$ 则链尾是 $2$, 与 $u$ 相连的另一个点只能是 $3$, 最后一个点 ${2, 3}$ 就没有可选的了, 于是固定了一条链.
由此可以得到, 一个连通块不可能有两个交的点数小于等于 $2$ 的环, 否则分别固定一条链就给它搞死了. 于是现在是彼此之间交路径长度大于 $1$ 的环.
再看, 度数大于等于 $4$ 意味着两个环的唯一交点肯定寄了, 同样发现多于两个三度点也无解, 最后只有两个三度点的情况, 图的形态是两个点之间三条路径.
最后, 如果存在 $\ge 2$ 条路径边数 $>2$ 也无解, 考虑任意一个偶环可以确定 $n-2$ 个点, 于是把两个 $n-2$ 个点的部分重合一下就死了. 这样路径长度为奇数的不能是大于 $2$ 的就不存在了(重边应该扔了), 路径长度为偶数的只能是恰好两条路径长恰为 $2$, 就做完了.
有解情况: 删完一度点后啥也不剩, 环, 三度点且两条路径长度为 $2$.
IOI2023 封锁时刻
第一种情况是没有点贡献 $2$, 则 $x, y$ 独立, 中间切开, 直接贪心就是对的.
第二种情况是存在点贡献 $2$, 那么如果是序列应该是把每个点看成投入 $d_1$ 获得代价 $1$, 再投入 $d_2-d_1$ 的物品做贪心, 此时可以分成两组, 对于 $d_2-d_1>d_1$ 的部分直接是凸函数max+卷积, 对于 $d_2-d_1<d_1$ 因为是上凸容易证明最多只有一个没有选满, 排序后枚举选了多少个 $2$ 即可.
而对于当前树形的问题则有依赖要求. 考虑如果儿子比父亲劣(代价比父亲高)则依赖被贪心满足, 则发现只有 $x\to y$ 的链上这个条件不满足, 而如果存在有点贡献 $2$ 这条链上一定每个点都至少贡献 $1$, 于是就做出来了.
P9605 [IOI2023] 机器人比赛
考虑把 $0, 1$ 单独拿出来, $2, 3, 4, 5$ 分别看作上下左右标记.
首先要求最短路, 作为第一阶段, 考虑bfs, 需要有一种方法逐层扩展节点. 从左上角开始bfs, 先把左上角指向下(或右)并朝该方向移动一格. 每当第一次到大一个节点, 将移动到的格子向回指向父亲(唯一一个指向自己的格子)并移动到父亲; 若当前节点不是第一次到达, 不断将指针逆时针旋转, 若指向格子未访问过就访问, 若是父亲就退回去, 于是每次最靠右下的所有格子会向外扩展一个距离, 同时机器人最终回到左上角, 是一个逐层加深的dfs过程, 并且任意时刻所有格子的指针为边构成机器人为根的根向树, 按照访问顺序构成以左上角为根的bfs树. 当机器人到达右下角时到第二阶段.
第二阶段要给最短路染色, 现在是以右下角为根的根向树, 则顺着树边dfs, 到达叶子时如果叶子是左上角就设为 $1$ 否则设为 $0$, 然后开始回溯, 回溯过程若相邻节点为 $1$ 设为 $1$ 否则设为 $0$, 容易发现满足要求.
Day2-量子计算
不听了不听了
Day3-比赛
T1
给定序列 $a_n$, 每个位置有随机类型 $c_i$, 按照类型为第一关键字, 下标为第二关键字排序后前缀和小于 $T$ 的元素 $i$ 会贡献 $b_i$, 求所有 $c_i$ 对应的贡献和的和.
$n\le 200, T\le 3\times 10^5$
简单题, 考虑拆贡献, 对于一个元素 $i$, 如果 $c_i=0$ 则所有后面的元素不可能在他前面, 于是答案就是前面元素的 $1+x^{a_i}$ 卷起来前 $T-t_i$ 项和为方案数, 同理 $c_i=1$ 的前面的一定贡献后面的卷起来前 $T-\sum_{j\le i} t_j$ 项的和为方案数, 复杂度 $nT$.
T2
给定序列 $h_n$, 求有多少区间 $[l, r]$ 满足存在正实数 $L$ 使得存在序列 $r$ 满足 $r_i\in {h_i, 2L-h_i} \forall i \in[l, r]$, 且 $r$ 单调递增.
$n\le 5\times 10^5$
赛时做法事考虑对于一个给定的 $L$, 每个元素使关于 $L$ 对称的两个值 $a_i$ 和 $b_i$, 合法的区间一定是连续的一段取 $a_i$ 接着一段 $b_i$, 于是设相邻两元素 $\vert h_i-L\vert<\vert h_{i+1}-L\vert$ 则它们只能是位于 $b$ 那一段设为 $1$, 否则如果是 $>$ 只能是 $a$ 那一段设为 $0$, 则合法区间一定是连续的一段 $0$ 右边一段 $1$. 同时注意到 $\vert h_i-L\vert$ 和 $\vert h_{i+1}-L\vert$ 的关系只会在 $\dfrac{h_i+h_{i+1}}{2}$ 变化 $1$ 次, 于是直接用数据结构修改 $01$ 同时找到最长合法区间, 最后是一个2side矩形覆盖.
注意到以上内容等价于不存在 $i$ 使得 $i, i+1$ 之间是 $1$ 而 $i+1, i+2$ 之间是 $0$, 而这个可以直接提出一个对 $L$ 的区间限制不属于某区间, 则问题变化为给定 $m$ 个区间问有多少个区间的区间并不是全集, 直接用不带删双指针做就是线性. /bx znb
T3
给定长 $n$ 序列的广义线段树(左闭右开)和 $m$ 个区间, 求有多少个线段树节点集合的子集 $S$(共 $2^{2n-1}$ 种)满足若 $S$ 中节点的和已知则可以已知所有 $m$ 个区间的和.
$n, m\le 2\times 10^5$
首先肯定转化成前缀和, 然后每个区间 $[l, r)$ 连边 $l\to r$, 能表示 $[a, b)$ 的和等价于 $a, b$ 连通
图存在分治结构对应到线段树上是子树
$m=1$ 时, dp, 记录两个区间端点和 $L, R$ 的连通性的 $2^4$ 种状态就dp出来了. 可以根据实现过 $m\le 5$.
关键性质是这个图是一个平面图, 则对于当前线段树节点, 若左右端点不连通, 则一定是左边一部分和左边连右边一部分和右边连, 中间可能剩一些不和两边连的不管它. 设 $f_{u, x}$ 为线段树节点 $u$, $[l, x]$ 与左边连, $[x+1, r]$ 与右边连, $g_u$ 为 $u$ 子树连通的方案数, 则可以做了, 不过当合并 $f_{l, x}$ 和 $f_{r, y}$ 合并的时候可能会中间有一块和两边不连通, 只要要求进行这个转移的时候必然有没有跨过 $x$ 和 $y$ 两处分界的要求必须连通的区间, 则现在把这个状态看成 $f_{u, x}$ 或 $f_{u, y}$ 对答案是没有影响的. 通过树形背包的复杂度可以做到 $n^2$
用线段树合并维护整体dp, 复杂度 $n\log n$
Day4-EI
组合类与生成函数
复习OGF
组合类, 组合对象, 数列, 生成函数
不会打组合类的记号, 下面大写是生成函数或组合类, 小写是数列或组合对象.
数列与生成函数: $A(x)=\sum_i a_ix^i$ 组合类与生成函数 $A(x)=\sum_{a\in A} x^{\vert a\vert}$
然后是组合对象符号化方法
MSET反演
我自己起的名字, 考虑MSET的逆变换是可以快速求的.
MSET是这样的:
$$
\begin{gathered}
\mathrm{MSET} A(x)=\prod (\dfrac{1}{1-x^i})^{a_i}\=\exp \sum_i -a_i\ln (1-x^i)\=\exp \sum_i a_i \sum_{j=1} \dfrac{x^{ij}}{j}
\=\exp \sum_{i=1} \dfrac{A(x^i)}{i}
\end{gathered}\
$$
考虑解这个东西的逆变换
$$
A(x)=\mathrm{MSET}(B(x))\
A(x)=\exp \sum_{i=1} \dfrac{B(x^i)}{i}\
\ln A(x)=\sum_{i=1}\dfrac{B(x^i)}{i}\
[x^n] \ln A(x)=\dfrac{1}{i}\sum_{i\vert n} [x^i] B(x) \
B(x)=\sum_{k=1}\dfrac{\mu(k)}{k}\ln A(x^k)
$$
最后一步是怎么搞的? 考虑 $\ln A$ 是 $B$ 和 $\dfrac{1}{i}$ 的狄利克雷卷积, 所以要求 $\dfrac{1}{i}$ 的逆元, 因为是积性函数可以用质数点值确定, 考虑其狄利克雷生成函数是
$$
F(x)=\sum_i \dfrac{1}{i^{x+1}}
\=\prod_{p\in P} \sum_i \dfrac{1}{p^i(p^i)^x}
\=\prod_{p\in P}\sum_i p^{-i(x+1)}
\=\prod_p \dfrac{1}{1-p^{-x-1}}
\\mathrm{INV} F(x)=\prod_p (1-p^{-x-1})=\prod_p(1-\dfrac{1}{p\cdot p^x})=\sum_i \dfrac{\mu(i)}{i}
$$
于是
$$
[x^n]B(x)=\sum_{i\vert} \dfrac{\mu(i)}{i} [x^{\frac{n}{i}}] A(x)\
B(x)=\sum_i\dfrac{\mu(i)}{i}A(x^i)
$$
考虑什么是 $\mathrm{MSET}$ 关系, 举了两个例子: 字符串和它的lyndon分解, 和多项式和其唯一分解成不可约的因子乘积. 于是要计数后者可以用前者做反演.
$\mathrm{PSET}$ 是不是也可以这么搞啊回去尝试一下.
颁奖典礼来尝试, $\mathrm{PSET}$ 应该是
$$
\begin{gathered}
\mathrm {PSET} A(x))=\prod (1+x)^{a_i}=\exp \sum_i a_i \ln (1+x)\
=\exp \sum_{i=0} a_i \sum_{j=1} \dfrac{(-1)^{j-1}x^{ij}}{j}\
=\exp \sum_{j=1} \dfrac{(-1)^{j-1}}{j}\sum_{i=0}a_ix^{ij}\
=\exp \sum_{j=1}\dfrac{(-1)^{j-1}}{j} A(x^j)
\end{gathered}
$$
也考虑解逆变换
$$
\begin{gathered}
A(x)=\mathrm {PSET}(x)=\exp \sum_{j=1}\dfrac{(-1)^{j-1}}{j} B(x^j)\
[x^n] \ln A(x)=\sum_{i\vert n} \dfrac{(-1)^{i-1}}{i}
[x^i]B(x)
\end{gathered}
$$
也可以用dgf去解 $\dfrac{(-1)^i}{i}$ 的逆, 要对 $p=2$ 分类, 不过其实提取系数可以直接单log递推.
复习EGF
乘法会分配标号, $\mathrm{MSET}(A(x))=\exp(A(x))$.
为啥没听说过EGF的 $\mathrm{PSET}$ 啊, 考虑一下应该是
微分
EGF上微分是给组合对象大小减 $1$, OGF上微分会再乘 $n$.
是我们组合意义的”指定”运算(OGF钦定一个元素拿走有大小种方案, EGF中拿走特定元素有 $1$ 种方案).
然后我们的微分基本法则, 链式法则, 莱布尼茨微分公式都可以拿我们的组合意义推了.
利用微分做EGF多重集的递推式
对应如何 $n^2$ 做多项式exp
经典例子是我们的有标号无向连通图, 方法是先对无向图求导得到无向图的微分方程, 再带到exp的式子去求导就有了微分方程从而递推式.
例题
求长 $n$ 且没有相邻两个数相差为 $1$ 的数量
考虑容斥, 先钦点序列由若干个差为 $1$ 的连续段构成, 则直接对 $-1$ 的个数容斥, 考虑一个长 $n$ 的负一的连续段应该有 $2-[n=1]$ 种方案系数是 $(-1)^n$ 容易推出带容斥系数的GF $G(x)=x-2x^2+2x^3-2x^4\ldots=\dfrac{x(1-x)}{1+x}$, 则答案的GF的 $F(x)=\sum_{n=0} n! G^n(x)$. 设 $S(x)=\sum_{n=0}n! x^n$
于是可以对 $S$ 求导 $S(x)=1+(xS(x))’x$, 从而 $S(G)=1+GS(G)+G^2(S’(G))$, 替换出 $F=1+GF+\dfrac{G}{G’}F’$ 我们知道($F’=(S(G))’=S’(G)G’$)
带入 $G(x)=x\dfrac{1-x}{1+x}$ 即可.
有标号二正则图计数
EI的思考题, 考虑二正则图就是一些长度大于等于 $2$ 的环, 显然是把它们的EGF exp起来, 一个环的EGF就是 $\dfrac{1}{2}(\sum_{i=1} \dfrac{x^i}{i}-x-\dfrac{x^2}{2})=-\dfrac{1}{2}\ln (1-x)-\dfrac{1}{2}x-\dfrac{x^2}{4}$, 除以 $2$ 是环可以翻转. 于是exp之后就是 $\dfrac{\exp (-\dfrac{1}{2}x-\dfrac{x^2}{4})}{\sqrt {1-x}}$
整式递推
生成函数级别
对于有理生成函数可以 $\log n$ 计算第 $n$ 项, 对于微分有限可以线性或 $M(\sqrt n)$ 做, 对于微分代数可以 $R(N)$(半在线卷积复杂度)做.
微分有限: 可以被自己的有限阶导数线性表示. 微分代数: 可以被有限阶导数用多项式方程表示.
例子
整数拆分是微分代数的. 具有禁止结构子排列的一般问题不能多项式时间计算.
微分有限
若果 $F(x)$, $G(x)$ 微分有限, 则 $F+G, FG, F/G$ 均为微分有限. 如果 $F$ 是代数的而 $G$ 是微分有限的则 $F(G)$ 微分有限. $exp, ln$ 是微分有限.
例子: $\exp(-dfrac{x}{2}-\dfrac{x^2}{4})\dfrac{1}{\sqrt{1-x}}$ 是微分有限的.
二元有理分式的对角线
是微分有限的, 如 $\dfrac{1}{1-x-y}=\sum_{n, m} binom{n+m}{n} x^ny^m$
证明: 设为 $Q(x, y)$, 带入 $x, a/x$ 求 $x$ 的 $0$ 次项然后分式分解, 提取常数项, 都是代数的.
Day4-核仁
P9601 [IOI2023] 最长路程
直接考虑 $D=1$, 因为图很稠密考虑哈密顿路, 不过容易发现可能出现图不连通, 此时考虑选取一个连通块中点 $u, v$ 与另外连通块中的点 $w$, 则因为 $w$ 与 $u, v$ 无边则 $u, v$ 有边, 另一个连通块一定为完全图.
考虑如何维护哈密顿路, 常见套路是不断加点, 但是维护一整条哈密顿路会寄, 不能保证已经加入的哈密顿路部分和当前点之间一定有边. 考虑实时维护两条哈密顿链, 然后每次问当前点和两个端点, 如果有边显然加上, 如果和这两个点之间都没有边则这两个点之间一定有边则把这两条链可以合成一个, 当前点作为第一个. 最后要合并两条链, 显然直接问端点, 端点不连只能是两条环, 再在两条环之间二分即可做到 $2n+2\log n$ 次.
考虑继续优化比如 $1. 5n$, 考虑 $3$ 次加 $2$ 个点, 想到这个基本就赢了, 考虑两点 $u, v$, 链头 $a, b$. 此时 $u, a, b$ 之间一定有边, $u, v, a$ 之间一定有边.
- 问 $u\to v$ 有边, 则因为 $a, b, u$ 之间一定有一条边两次问出来赢了.
- 否则 $u\to v$ 没边, 问 $u\to a$ 如果没边则 $v\to a$ 一定右边, 搞定另一个也一次.
于是就是 $1. 5n+2\log n+O(1)$ 了.
P9602 [IOI2023] 足球场
考虑合法图形的样子, 显然不能出现两个空位中间一个障碍的情况(至少 $3$ 次), 于是每行一个连续段, 容易发现如果两行的区间不是包含的肯定不行, 于是中间的最大向两边递减.
于是一个朴素dp是 $f_{u, d, l, r}$ 表示考虑 $[u, d]$ 之间的行, 当前对行的区间的最小限制是 $[l, r]$, 转移显然就是扩展 $u/d/l/r$.
考虑优化, 固定 $l, r$ 显然 $u, d$ 一定顶到头上于是只可能有 $n$ 组, 再考虑 $l$ 固定时 $r$ 也一定是极大的, 且当 $r$ 不断右移时, $u, d$ 的可行区间不断分裂. 于是遂着 $r$ 的增加可以把 $u, d$ 组按照区间包含关系连出树, 于是固定 $l$ 只有 $r$ 极大, $u, d$ 为树节点对应区间的 $O(n)$ 个状态, 状态数变成了 $n^2$.
转移预处理后做到 $O(1)$.
CF1175G Yet Another Partiton Problem
核仁提示: 这个函数没有四边形不等式.
那你瞪着这个 $k\le 100$ 容易想到每个 $k$ 跑一遍, 然后考虑上数据结构, 扫描当前的 $i$, 则这个 $\max$ 显然考虑单调栈, $j$ 的贡献可以表示为 $D_j(i-j)+f_j=(f_j-jD_j)+iD_j$(其中 $D_j$ 为 $\max_{k\in [j, i]} a_k$), 则贡献是关于 $i$ 一次函数. 显然每个连续段只需要保留贡献最大的一个. 而因为是单调栈只要支持插入一次函数和撤销一次函数. 可撤销李超树秒了. 复杂度单log.
TopCoder 14379 RPSRobots
剪子包袱锤前两天是不是做过一个ARC132F.
感觉这个东西不变的性质很难被人脑想象. 上技术.
考虑剪子包袱锤分别设为 $0, 1, 2$, 则结果对应模 $3$ 意义下的差. 看到模转单位根, 于是 $A, B$ 两个人在没转情况的值是 $v=\sum_i w_3^{a_i}w_3^{b_i}$, 发现不同的值对应不同的结果, 于是只要考虑值相等. 同时设 $p_i=w_3^{a_i}, q_i=w_3^{-b_{-i}}$, $h=p*q$(长度为 $k$ 的循环卷积), 则 $h_i$ 就是移动 $i$ 位的结果.
于是要求 $h$ 全相等, 因为循环卷积考虑做dft转点积, 就要考虑什么东西idft后全相等. 众所周知idft是对单位根倒数多点求值, 则是常函数, 则要求 $p, q$ 做dft后点积在 $i>0$ 的部分有值的集合无交.
此时应该想到子集卷积就是有交的不贡献, 但问题是 $p_i$ 和 $q_i$ 定义不同. 需要进一步发现性质, 观察dft后 $p$ 得到序列的 $p’$ 和 $q$ 得到的序列 $q’$, $q’i=\sum_j w_k^{ij} w_3^{-b{-j}}=\sum_j w_k^{-ij}w_3^{-b_j}, p’_i=\sum_j w_k^{ij}w_3^{a_i}$, 发现两个结果是共轭的. 又因为我们只关心它们是不是 $0$ 于是可以都用 $p$ 的定义做dft.
于是复杂度是子集卷积的 $k^22^k$
loj2462 完美的集合
容易想到固定 $x$ 后就是包含根, 有一些点不能选的连通块个数, 但直接去子树内去卷积是 $nm^2$ 的. 关键暴力卷积合并是不如逐个加入的, 不如按照dfs序每次逐个加入元素. 容易做到 $nm$
而最后若干个连通块的交一定是一个连通块. 树上的连通块满足 $V-E=1$, 于是考虑容斥, 求出每个点的答案和每个边两个点同时被包含的答案, 即可容斥出 $K=1$ 的答案 $ans$.
对于 $K$ 很大时, 发现就是要求 $\binom{ans}{k}$($ans$ 是真实值因为 $n\le 60$ 开ll完全能存下. )
考虑exlucas说的是先对所有 $p^k$ 求答案再crt合并, 其中对所有 $p^k$ 求的时候先提出阶乘中所有 $p$ 的倍数, 把 $p$ 提出, 有等式 $n! =p^{c}(\dfrac{n}{p})! M$, 其中 $M$ 是所有不是 $p$ 倍数的数的乘积, 中间的是子问题, 左边的显然好处理. 于是要处理 $M$.
$$
M=\prod_{i}^{n/5}\prod_{j=1}^4 (5i+j)
$$
考虑 $i$ 分成两半, 则一边是 $\prod_i^{n/5/2}\prod_{j=1}^4 (5i+j)$, 一边是 $\prod_i^{n/5/2}\prod_{j=1}^4 (\dfrac{5}{2}n +5i+j)$, 于是考虑维护多项式 $\prod_i^n \prod_{j=1}^4 (x+5j+4)$, 则可以用多项式乘法和多项式平移的倍增合并出 $\prod_i^{2n}$ 的情况, 就做完了.
loj2461 完美的队列
从询问的颜色数出发, 考虑某次修改什么时候全都没了. 但这个还是不好做, 于是分块, 一个修改拆成 $O(\sqrt n)$ 个, 则只要解决 整块/单个数 的情况.
考虑整块, 有若干整块插入和若干单点修改, 先给每个位置都减去 $a_i$, 相当于以每个整块插入时间作为左端点插入问最小的右端点使得进行中间这段时间的操作后所有位置大于等于 $0$, 容易考虑出双指针, 则现在要支持单点加减 $1$ 和全局最小值, 可以用开桶做到单次 $O(1)$.
对于散点询问要考虑复杂度要只能关于对于当前点的修改, 于是对每个整块先处理出时间上关于操作上的前缀和, 则可以容易的只扫对于当前散点修改做相同的双指针.
现在复杂度是 $n\sqrt n$, 可以进一步优化, 发现整块和散块结构有相似性, 考虑分治结构, 上线段树, 每个修改拆成 $\log n$ 个, 现在对一个节点, 修改有祖先上的, 子树中的和自身的 $3$ 种, 而子树中的和自身的总数是 $n\log n$ 的, 于是对于当前节点可以拿所有自身的和子树中的元素跑双指针, 对于祖先上的修改记录前缀和, 复杂度 $n\log^2 n$
loj2339 通道
考虑两棵树怎么做, 有很多种方法:
- 对第一棵树点分治, 然后对当前分治的点集在第二棵树上的对应点建虚树, 枚举虚树上的 lca.
- 枚举第一棵树上路径lca $u$, 考虑现在 $a, b$ 答案是 $dep_a+dep_b-2dep_u+dist_2(a, b)$, 于是在第二棵树上点 $u$ 挂深度为 $dep_u$ 的叶子, 则问题就是子树点集中叶子距离最大值, 可以用经典的维护点集直径方法解决.
现在三棵树只要合并两种方法, 第一棵树点分治, 第二棵树建虚树并枚举lca, 在第三棵树建虚树并按照 $d_u+dep_u$ 挂叶子, 则 $u, v$ 的答案是 $dist_3(u, v)$.
然后现在看起来复杂度是俩log, 但lca都可以 $O(1)$, 建虚树的排序可以在点分治时归并, 复杂度仍然是 $n\log n$
想到一个暴躁做法, 第一棵树点分治, 第二棵树建虚树, 再在虚树上点分治, 再在第三棵树对应第二棵树点分治区域建虚树, 再在虚树上枚举lca, 复杂度应该是俩log吧!
CF506E Mr. Kitayuta’s Gift
相当于填长 $m=n+\vert s\vert$ 的回文串要求 $s$ 是子序列. 容易想到暴力dp, 因为是回文串所以考虑从两边往中间填, 设 $f_{i, j, k}$ 表示填了两边的前 $i$ 个, 匹配长度分别是 $j, k$, 显然过不了.
实际上可以去优化建图, 后面两维就是要一个能表示 $s$ 双向匹配且匹配完整截止的自动机, 直接建图是一个二维网格图, 每个点 $(i, j)$ 连向 $(i+1, j), (i, j+1)$ 或连向 $(i+1, j+1)$, 长这样:
因为 $m$ 是 $10^9$ 想矩阵? 但是后面的状态太大, 这时候感觉dfa minimize很有道理直接过了?
好吧实际上是过不了的, 最小化后仍然很大. 因为这个dfa是用来匹配的而不是用来数数的有很多无用信息. 注意到每条起点到终点的链的答案只和红点/绿点个数相关而和位置无关, 再优化建图即可.
然后偶数的时候直接做, 奇数的时候只有最后一步走的是由长度为 $2$ 的绿点到终点的边的情况下不合法减去即可.
然后这个题可以 $s^3+\log n$ 的, 考虑回到刚才的dp
$$
f_{i, j, k}=
\begin{cases}
f_{i-1, j-1, k-1}+25f_{i-1, j, k}, \ if\ s_i=s_{\vert s\vert-j+1}\
f_{i-1, j-1, k}+f_{i-1, j, k-1}+24f_{i-1, j, k}\ else
\end{cases}
$$
于是写成GF, $[x^k]F_{i, j}=f_{k, i, j}$ 形式, 对 $i, j$ 都有
$$
\begin{gathered}
F_{i, j}=x(AF_{i, j}+BF_{i-1, j}+CF_{i, j-1}+DF_{i-1, j-1})+E\
F_{i, j}=\dfrac{x}{1-Ax}(BF_{i-1, j}+CF_{i, j-1}+DF_{i-1, j-1}+E-AEx)\
\end{gathered}
$$
其中 $A, B, D, C, E$ 为常数. 并且 $A$ 只能是 $24, 25, 26$ 中的.
Day4-营员交流内容
感觉很不可听
PGF
基础知识
EGF很适合在时间轴上分配标号, 但PGF的性质参照OGF, 于是定义 $L(F)=\sum_i i! [x^i]F$, 他说 $L$ 是拉普拉斯算子.
简单性质: $L$ 是线性的, $L(x^ae^{bx})=\dfrac{a! x^a}{(1-bx)^{a+1}}$
然后就是PGF基本性质, 代入 $1$ 是概率求导代入 $1$ 是期望.
例题-Gachapon
现有一随机数生成器, 每次生成 $1<i<n$ 的概率为
$A_j/\sum_{i=1}^n A_i$, 使用其不断独立随机生成.
当对任意 $1\le j\le n$ 都有被生成了至少 $B$ 次时过程停时. 求期望停时.
$A_i, B_i\le N^+, 1 \le n, \sum A_i, \sum B_i\le 400.$
$S=\sum_i A_i, P_i=\dfrac{A_i}{S}$, 考虑最后一步选的 $i$, 则 $i$ 选了恰好 $B_i-1$ 步, 其它的 $j$ 选了任意大于 $B_j$ 步, 就是:
$$
1+L\left(\sum_{i=1}^n
\dfrac{(P_ix)^{B_i-1}}{(B_i-1)! }
\prod_j \left(\exp(P_jx)-\sum_{k=0}^{B_j-1}\dfrac{P_j^kx^k}{k! }\right)
\right)’\circ 1
$$
$1$ 是最后一步, 里面枚举选的 $i$, 则 $i$ 被选了 $B_i-1$ 次, $\prod$ 后面是每个其他元素被选任意次再减去少于 $B_j$ 次, 最后转化OGF再求导带入算期望.
例题-猎人杀
给定一个由 $n$ 个人组成的集合, 每个人有一个权值 $w_i$. 在每次操作中, 从剩余的人中以 $\frac{w_i}{\sum w_i}$ 的概率独立随机选择第 $i$ 个人离开, 直到所有人都离开. 求最后离开的人是第一个人的概率, 并对 $998244353$ 取模.
概率变化这件事很困难, 考虑让已经离开的人仍然可以被选只是被跳过, 然后钦点了最后一个人, 和上个题一样的写答案
$$
\dfrac{w_1}{S}L(\prod_{j=2}^n \exp(\dfrac{w_j}{S}x)-1)\circ 1
$$
分治乘法或先 $\ln$ 再 $\exp$
uoj514 通用测评号
$n$ 个变量 $c_i$ 初始为 $0$, 每次随机 $c_i<a$ 的 $i$ 使 $c_i$ 加 $1$, 当所有变量不小于 $b$ 时停止, 求最后期望有多少个 $i$ 满足 $c_i=a$.
$n\le 250, b<a\le250$
和上题一样认为是所有的中随机并跳过不满足条件的. 只要考虑 $c_1$ 爆掉的概率乘 $n$.
可以写PGF, 仍然枚举最后一步选择的变量(肯定不能是 $c_1$):
$$
\dfrac{n-1}{n}L\left(
(\exp \dfrac{x}{n}-\sum_{j=0}^{a-1}\dfrac{x^j}{n^jj! })
(\exp \dfrac{x}{n}-\sum_{j=0}^{b-1}\dfrac{x^j}{n^jj! })^{n-2}
\dfrac{x^{b-1}}{n^{b-1}(b-1)! }
\right)
\circ 1
$$