【听课记录】25.11-LCA-Week7.8

· · 个人记录

11.12 图论

比如平面图不含 K_5,K_{3,3}，半平面图不含 K_4,K_{2,3}。

杂题

题意

定义单点合法，若干个合法图放在一起合法，合法图对边取补集合法。给定无向图，判断该图是否合法。n,m\le 10^5。

题解

将定义过程倒过来，每次从原图和补图中选一个，递归进每个连通块分别判断。注意到原图和补图至少有一个连通，对这个图拆连通块递归下去。这需要对原图和补图分别进行搜索，原图显然可以 \mathcal O(m) 搜索，对于补图可以 BFS，使用链表维护所有没搜过的点，这样额外复杂度是所有点度数之和，也是 \mathcal O(m) 的。

分析一下复杂度，有 T(m)=\mathcal O(m)+T(m-\sqrt m)，这样的话总复杂度为 \mathcal O(m\sqrt m)。至于为啥能使边数减少 \sqrt m，首先每次所用的图一定是上次的补图，于是每两轮就会用一次原图的补图。而每次用原图的补图划分连通块时，上轮同一连通块内的边若两端被划分进了不同连通块，则之后就没用了。感性理解这个过程中废弃的边是比较多的，因为不同连通块间的完全 k 部图边全没了。具体不会证，没题写不了，不管了。

P11762 [IAMOI R1] 走亲访友

题意

给定 n 点 m 边连通无向图，要求走一条从 s 出发长不超过 k 的路径，走的过程中可以选择删掉经过的边，走完后未删除的边形成一棵生成树。n\le 1000,m\le \frac {n(n-1)}2,k=n+m。

题解

由于要求保留生成树，直接先跑出一棵来，不妨以 s 为根，现在要求路径经过非树边至少一次，这应该是欧拉路径状物，为方便直接做欧拉回路，这样要求每个点度数均为偶数。初步想法是树边可以不走，于是决策一下树边是否经过就可以满足度数限制了，然后做到了路径长度不超过 m？

并非，因为欧拉回路还需要图连通，而断掉若干树边后图不一定连通了。于是每条树边也得经过至少一次，在此基础上决策若干树边多走一次即可。路径长度不超过 n+m-1，复杂度 \mathcal O(n+m)。

典题

找一棵生成树，非树边任意选之后合法树边是存在且唯一的，于是一个连通图方案数为 2^{m-n+1}，总方案数为 2^{m-n+k}，其中 k 为连通块个数。

若连通图点数为奇数，则方案数一定为 0，否则方案数仍为 2^{m-n+1}，推理相同。总方案数为 2^{m-n+k} 或 0，且只在存在点数为奇数的连通块时为 0。

对于一个连通图，若所有点均有限制，直接判断总度数是否为偶数即可，是则答案为 2^{m-n+1}，否则为 0。若存在点无限制，考虑枚举每个点度数奇偶性，一定恰有一半方案奇偶性是对的。设存在 t 个无限制点，则方案数为 2^{m-n+t}，将所有连通块的答案乘起来即可。

P7624 [AHOI2021初中组] 地铁

题意

有一个环，要求相邻点距离为正整数，有 m 条 u,v 顺时针距离不小于或不大于 w 的限制，求合法环长个数。n,m\le 500。

题解

考虑如何判断环长 x 是否合法，可以把限制建成差分约束，只要没有负环就存在解。此时 u\lt v 的限制只有值，而 u\gt v 的限制里含 x。考虑对于图中的一个环，若 x 的系数和为正则限制 x 为一个后缀，为负则限制 x 为一个前缀，这说明合法 x 形成一个区间。

于是二分，对于 x=mid 跑差分约束，若存在负环再判一下环上系数和，从而实现找到合法区间左右端点。注意此处途径边数超过 n 的点不一定在负环上，也可能在负环延伸出去的链上，所以要先跳 n 次前驱再求负环。总复杂度 \mathcal O(nm\log V)。

P3645 [APIO2015] 雅加达的摩天楼

题意

#### 题解 考虑暴力，从 $p$ 向 $p+kd$ 连权为 $\left|k\right|$ 的边后直接跑最短路即为答案。可以优化建图，令 $B=\sqrt n$，则所有 $d\gt B$ 的边共 $\mathcal O(m\sqrt n)$ 条。对于 $d\le B$ 的边，按 $d$ 和 $p\bmod d$ 分类，每类中向前的边连到上一个有人的点即可，于是每类有 $\mathcal O(\frac nd)$ 条边，共 $d$ 类，总边数为 $\mathcal O(n\sqrt n)$。这样只能跑 Dijkstra，可能要带个 log，没有写。 考虑换一种方式，设 $f_{i,d}$ 表示当前参数为 $d$ 的人在 $i$ 点需要的最少移动次数。$d\le B$ 的状态数不超过 $\mathcal O(n\sqrt n)$，$d\gt B$ 的状态数不超过 $\mathcal O(m\sqrt n)$，总状态数是有保证的。另外这样转移只有在某个点上转到别的人，或者向前后跳一步，边权只有 $0,1$，可以 $01$ BFS 解决，复杂度 $\mathcal O((n+m)\sqrt n)$。 ## 11.12 思考题 复读机 以下问题中给定一个序列，可以重复读入，但只有 $\mathcal O(1)$ 内存。序列中的值均为正整数。（当然原题是自然数，此时给所有数加上 $1$ 即可） - 序列中只有一种数出现奇数次，找出这种数。 直接求序列所有值的异或值即为答案，读入 $1$ 遍，记录 $1$ 个数。 - 序列中只有两种数出现奇数次，找出这种数。 确定性算法：先求出所有值的异或值 $x\oplus y$，找到其中某个 $1$，按照这一位的值分成两个集合，对两个集合各做一种数的情况即可，这可以在同一遍读入中求。读入 $2$ 遍，记录 $2$ 个数。 非确定性算法：每轮可通过哈希将所有种类的值随机分成 $c$ 个集合，只要 $x,y$ 分到不同集合就能求出答案，错误率 $\frac 1c$。可以进行常数 $t$ 轮，多轮求解可在同一遍读入中求，读入 $1$ 遍，记录 $tc$ 个数，错误率 $\frac 1{c^t}$。一般来说 $c$ 取距 $e$ 最近的整数 $3$ 最优。 还有一种做法，准备 $2k$ 个集合，其中 $k$ 为奇数。设计一个函数 $f(x)$，返回 $[1,2k]$ 的一个大小为 $k$ 的子集，将该子集内的集合值均异或上 $x$。这样当且仅当 $x,y$ 随机出来的子集完全相同时求不出答案，否则可以通过 $x,y,x\oplus y$ 中 $x,y$ 出现次数相同求出答案。读入 $1$ 遍，记录 $2k$ 个数，错误率 ${2k\choose k}^{-1}$。LCA 说这种方法已经接近信息论的错误率下界了，不懂。 - 序列中只有两种数出现次数不为 $3$ 的倍数，找出这种数。 首先若只有一种数出现次数不为 $3$ 的倍数，可以直接在三进制下每一位求和再对 $3$ 取模，再按 $c_x\bmod 3$ 分讨即可，这个值与 $n\bmod 3$ 相等。读入 $1$ 遍，记录 $1$ 个数。 确定性算法：将所有值转化为二进制，记录每个二进制位 $1$ 的个数对 $3$ 取模的结果。之后可以根据 $c_x+c_y\equiv n\pmod 3$ 分讨，找到某个 $x,y$ 不同的二进制位，再按这一位分组进行一种数的情况，同样可以同一遍求。读入 $2$ 遍，记录 $2$ 个数。 非确定性算法：与上个题次数奇偶性的做法相同，可能会多一些对出现次数的分讨，记录数字个数可能要乘上一个常数，不再赘述。 ### U498564 找不同 #### 题意 给定长为 $2n+3$ 的序列，其中 $n$ 种数出现两次，$3$ 种数只出现一次。只有 $\mathcal O(1)$ 空间，找出只出现一次的三种数，序列输入四次。$n\le 7\times 10^5$。 #### 题解 考虑分离出一个数，转化成两种数的情况。将序列所有值异或起来可得 $X=x\oplus y\oplus z$，定义 $b_i=a_i\oplus X$，则 $b$ 中出现奇数次的只有 $x\oplus y,x\oplus z,y\oplus z$ 三个数。显然三者两两不同，且异或值为 $0$，这说明每个二进制位上均全 $0$ 或恰有两个 $1$。 于是考虑最低位的 $1$，设 $x$ 最低位的 $1$ 为 $f(x)$。根据上面的结论，三个数的 $f$ 值恰有两个相同。于是先求出全局 $f$ 值的异或和，就得到了其中一个数的 $f$ 值 $Y$。按照 $f$ 值是否等于 $Y$ 将序列分成两部分，各有 $1,2$ 个出现一次的数，套用上面的做法即可。读入 $4$ 遍，粗糙实现可以记录 $7$ 个数。 ### LOJ6537. 毒瘤题加强版再加强 #### 题意 给定长为 $n$ 的序列，其中恰有 $k$ 个数出现奇数次。只有 $\mathcal O(1)$ 空间，找出这 $k$ 个数。$n\le 3\times 10^6,k\le 5000$，空间限制 3MiB。 #### 题解 太难了，直接考虑非确定性算法。考虑设计哈希函数 $f(x)$，开 $t$ 个大小为 $\mathcal O(m)$ 的哈希表，每输入一个 $x$ 就向所有哈希表的 $f(x)\bmod m_i$ 位置异或上 $f(x)$。最后取出哈希表所有未冲突位置的值 $f(x)$，将其转换回 $x$ 输出。 首要问题是，需要设计一个这样的函数 $f$，需要大致随机，能以较高正确率判断一个值是否是该函数值，且能快速转换回 $x$。采用 $f(x)=kx+b$，$k$ 取大质数，这样判断 $y$ 就可以检查 $y\bmod k$ 的值是否为 $b$ 了，转换回 $x$ 只需要除以 $k$ 下取整即可。 这样就得到了一个算法。分析一下错误率，需要 $k$ 个数均被找到，这需要每个数都在 $t$ 个哈希表中的至少一个不冲突，单个冲突概率为 $\mathcal O(\frac km)$，于是单个数正确概率约为 $1-(\frac k m)^t$，于是正确率为 $(1-(\frac km)^t)^k$，当然这是忽略哈希值转换错误率的结果。对于本题，大概可以取 $t=7,m=30000$，有 $0.98$ 左右的正确率。 ## 11.14 字符串 问题： - 子串匹配 - 子串约束（Border / 周期、回文） - 其他（子序列等） 算法：自动机（字典树）、“莫队”思想、Hash。 用 Trie 树刻画字符串集合，若只判断某串是否在集合内，可以按未来可以走的串缩等价类得到 DFA。同样用 DFA 刻画所有包含串 $S$ 的串，自动机的不同状态分别为串后缀为 $S$ 前缀的长度。 考虑转移，发现关心 $S$ 所有前缀的 Border。注意到一个串的 Border 由于传递性具有全序，于是记录最大真 Border 即可。然后就发明了 MP 算法，当然这也就是一般说法中的 KMP。若预处理 $tr_{i,j}$ 表示状态 $i$ 加上字符 $j$ 到的状态，就得到了 KMP 自动机（Trie 图）。 有一些结论，比如最大周期等于长度减最小 Border 之类，手推可知。 若求多个前缀的公共 Border，可在失配树上求 LCA。扩展到多串变成 AC 自动机了，超纲。使用“莫队”思想还可以推出扩展 KMP 和 manachar，略过不表。 Hash，$B,P$ 取质数，也可以将每种字符随机映射之后计算，在减法之类的东西上有奇效。一般来说要使得哈希空间比比较次数的平方略大，双哈希一般够了。集合哈希可以使用异或之类。其他哈希可以尽量转化成序列或集合哈希。 ### LOJ502. 「LibreOJ β Round」ZQC 的截图 没太懂这个题，之后可能会做。 ### P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？ 一顿转化之后需要对每个连通块维护根节点对于所有串的 $0/1$ 信息，在这里使用哈希。之后应该会做。 ## 11.16 数学？ 去 CCPC 了，没听。 ## 11.19 组合计数 判定型计数（唯一判定、最小表示、取补集、容斥拆贡献） “证书”定义为某种使方案合法的方案，最小表示即找到某个特定“证书”并对其计数，取补集即统计无“证书”的方案数。 考虑局部信息，大概意思是判定相邻元素合法，从而整个方案合法。 ### CF559C Gerald and Giant Chess #### 题意 给定长宽分别为 $h,w$ 的网格，有 $n$ 个障碍，求从左上到右下不经过障碍的路径条数。$h,w\le 10^5,n\le 2000$。 #### 题解 考虑取补集。考虑设 $f_{i}$ 表示不经过其他障碍走到 $(x_i,y_i)$ 的方案数，初值为 ${x_i+y_i-2 \choose x_i-1}$。另外对于所有 $x_j\le x_i,y_j\le y_i$ 的 $j$，要减掉实际上首个障碍为 $j$ 的方案数，即 $f_i\leftarrow f_i-f_j\times {x_i-x_j+y_i-y_j\choose x_i-x_j}$。最后用 $h+w-2\choose h-1$ 减掉所有 $f$ 的和即可，复杂度 $\mathcal O(\max(h,w)+n^2)$。 ### P11588 [KTSC 2022 R2] 彩色括号序列 #### 题意 给定一个带颜色的括号序列，要求选出一个子序列，使得相邻括号和匹配括号颜色均不同，求能选出的本质不同合法子序列数量。$n\le 700$。 #### 题解 如果是下标不同子序列，可以设 $f_{l,r}$ 表示在 $[l,r]$ 内选，强制选 $l,r$ 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于每种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 $x,y$ 满足 $pre_y\le x$，其中 $pre_y$ 表示 $y$ 上次出现的位置。这样是局部限制，可以在 DP 过程中满足，最终只对不存在 $pre_l$ 的 $f_{l,r}$ 统计即可。 考虑转移，分为 $l,r$ 匹配和不匹配两种。前者枚举内部选的左右端点 $x,y$ ，不要求 $x,y$ 匹配，限制为 $c_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y$；后者枚举与 $l$ 匹配的 $x$，再枚举 $x$ 之后第一个左括号 $y$，要求 $l,x$ 匹配，不要求 $y,r$ 匹配，限制为 $c_l\ne c_x,c_x\ne c_y,pre_y\le x$，复杂度 $\mathcal O(n^4)$，常数很小。 注意到对于方案中相邻的 $x,y$，固定 $y$ 时后缀 $x$ 合法，但固定 $x$ 时合法的 $y$ 没有规律，似乎不太容易直接前缀和优化。注意到转移时 $y$ 的限制只与 $x,r$ 有关，于是设 $g_{x,r},h_{x,r}$ 分别表示固定 $x,r$ 时，两种转移的合法 $y$ 对应值之和。此时 $f_{l,r,1}$ 只会贡献到 $g_{l,t}$ 和 $h_{t,r}$，也就是 $\mathcal O(n)$ 个值中。转移时枚举 $x$ 后可以 $\mathcal O(1)$，于是总复杂度为 $\mathcal O(n^3)$，好像常数还是不大啊。 - 子集容斥 有 $n$ 条限制，求所有限制均满足，即不合法限制集合为空集的方案数，当容易算某子集强制不合法，其余不作限制的方案数时可使用子集容斥。 具体地，枚举集合 $S$ 内的限制均不满足，设 $f(S)$ 表示方案数，则答案为 $\sum (-1)^{\left|S\right|}f(S)$。 ### P6076 [JSOI2015] 染色问题 #### 题意 给定 $n\times m$ 网格和 $c$ 种颜色，要求每行每列不能全无色，且每种颜色均出现，求方案数。$n,m,c\le 400$。 #### 题解 直接子集容斥，枚举 $i,j,k$ 表示 $i$ 种颜色不出现，$j$ 行 $k$ 列全无色，答案为 $\sum _{i\le c}(\sum_{j\le n}(\sum_{k\le m} (c-i+1)^{(m-k)(n-j)}\times (-1)^k\times {m\choose k})\times (-1)^j\times {n\choose j})\times (-1)^i\times {c\choose i}$，也就是 $\sum_{i\le c,j\le n,k\le m} (c-i+1)^k\times {c\choose i}\times{n\choose j}\times {m\choose k}\times (-1)^{i+j+k}$，枚举 $i$ 后先预处理 $(c-i+1)$ 的若干次方即可做到 $\mathcal O(nmc)$。 或者可以只容斥两层，对于最后一层不枚举 $k$，而是直接计算出 $(c-i)$ 种颜色填 $(n-j)\times m$ 网格的方案数，要求每列不全无色，答案为 $((c-i+1)^{(n-j)}-1)^m$，再套上前两层的容斥系数即可，这里好像只能快速幂了，复杂度 $\mathcal O(cn\log m)$。 ### P1450 [HAOI2008] 硬币购物 #### 题意 给定四种钱币，价值分别为 $c_i$。$q$ 次询问给出 $d_i,m$，表示有 $d_i$ 个价值为 $c_i$ 的钱币，求和为 $m$ 的方案数。$q\le 1000,c_i,d_i,m\le 10^5$。 #### 题解 所用个数不超过 $d_i$ 有点难做，考虑容斥变成所用个数超过 $d_i$。具体地，枚举 $S$ 内的种类一定超出限制，其余任意。求出 $S$ 内 $c_i(d_i+1)$ 的和，若其不超过 $m$ 则方案数为 $f_{m-s}$，其中 $f$ 为任意取所有钱币的方案数，可以提前完全背包预处理。总复杂度为 $\mathcal O(km+q\times 2^k)$，本题中 $k=4$。 - 二项式反演 大概是若有 $b_i=\sum_{j\le i} a_j\times {i\choose j}$，则 $a_j=b_j-\sum_{j<i} a_j\times{i\choose j}$，可以顺序求出。 - min-max 容斥 式子是 $\min_{x\in S} x=\sum_{T\in S}(\max_{x\in T} x)\times (-1)^{\left|T\right|+1}$，两者反过来也是成立的，证明可以考虑只有空集的偶数子集比奇数子集多一个，其余集合的奇偶子集数量相同。感觉主要应用是求期望啊。 - 点边容斥 对于统计合法连通块数量，枚举所有点统计并对方案数求和，再枚举所有边中点统计并减去方案数的和，这样每个连通块会被统计点数减边数次，次数恰为 $1$。 比如在圆方树上令圆点为 $-1$，方点为点双点数，$u,v$ 路径经过的所有点双点的并集（不包括 $u,v$）大小即为圆方树上路径和。 - 反射容斥 大概是在坐标系里将不合法的路径反射回去，变成两种路径数相减，典型应用是卡特兰数。 有一些拓展，比如有上下界限制时可以套多次反射容斥，状态数大概是 $\mathcal O(\frac nm)$ 的，其中 $m$ 为上下界之差。 ### P4769 [NOI2018] 冒泡排序 转化转化之后变成不存在三元下降子序列，然后画画图发现所有逆序对之间要递增，大概能用卡特兰数计算，之后可能会做。 下面这题是 LCA 讲思考题的时候讲的，由于前缀和差分比较基础，不开新标题了。 ### CF1097F Alex and a TV Show #### 题意 维护 $n$ 个可重集，支持将 $x$ 集合变为 $y,z$ 集合的并或者 $y,z$ 集合两两 GCD 形成的可重集，单点修改一个集合为单值集合，查询某集合内某数出现次数奇偶性。$n\le 10^5,q\le 10^6,v\le 7000$。 #### 题解 由于只关心奇偶性，个数 $a_{i,j}$ 之类均对 $2$ 取模存储即可。另外由于有变为两集合 GCD 的操作，考虑记录 $b_{i,j}=\sum_{j\mid k}a_{i,k}$，这样合并操作即 $b_{x,j}=b_{y,j}b_{z,j}$，取并集时即 $b_{x,j}=b_{y,j}+b_{z,j}$，用 bitset 按位与和按位异或即可。 对于修改为单值集合，可以预处理出所有 $x$ 对应的集合状态。对于查询，需要枚举所有 $x\mid y$ 且 $\mu(\frac yx)\ne 0$ 的位置异或和，也对每个 $x$ 预处理出这个即可。总复杂度大概是 $\mathcal O(v\log v+\frac{qv}w)$，可以通过。 ## 11.21 组合计数 组合（双射）、代数（生成函数）。 ### 某题 #### 题意 给定 $n,a_{n+1}$，要求 $a_i\mid a_{i+1}$，求合法序列数量，并对每种 $a$ 序列的数字种类数分别计算方案数。$n\le 10^5,a_{n+1}\le 10^9$。Bonus：$a_{n+1}\le 10^{18}$。 #### 题解 将 $a_{n+1}$ 分解质因数为 $\prod p_i^{k_i}$，之后每个质因子独立，且均满足次数不降，于是可分别求方案数再乘起来。对于 $k_i$ 来说方案数为 ${k_i+n\choose n}$，这是将 $k_i$ 分到差分数组的 $(n+1)$ 个位置的方案数，全乘起来即为答案 $f_n$。 至于出现 $i$ 种不同数的方案数，显然数字种类数不超过 $\mathcal O(\log V)$ 级别。考虑先求出 $g_i$ 表示选出长为 $i$ 的单增序列方案数，一定有 $f_n=\sum_i g_i\times {n-1\choose i-1}$，于是先求出 $f$ 的前 $\log V$ 项再反演回 $g$ 即可，$i$ 种数的答案即 $g_i\times {n-1\choose i-1}$。 但是 $a_{n+1}\le 10^{18}$ 没法分解质因数了，然而注意到本题做法只跟 $k_i$ 有关，于是枚举到 $\sqrt[3] V$ 后只剩至多两个大质数乘积，即只可能是 $p,p^2,pq$ 三种，前两种都是好判的，这样就能得到 $k$ 序列了。没题写不了。 ### P2401 不等数列 #### 题意 给定 $n,m$，求 $m$ 对相邻值上升的 $n$ 阶排列个数。 Bonus：$n,m\le 10^5$，模数为质数。 #### 题解 可以 $\mathcal O(n^3)$ DP，设 $f_{i,j,k}$ 表示填了 $i$ 个数，$j$ 个上升且 $i$ 的相对排名为 $k$ 的方案数，前缀和优化转移即可。注意到有 $j,k\le i$，常数比较小，可以过。 设 $f_{n,m}$ 表示答案，尝试递推，考虑排列中 $1$ 的位置，从而从 $n-1$ 阶排列推过来。由于放到开头或某个下降位置会使上升位置增加，放到结尾或某个上升位置时上升位置数不变，有 $f_{n,m}=(m+1)f_{n-1,m-1}+(n-m)f_{n-1,m-1}$，就 $\mathcal O(nm)$ 了。$f_{n,m}$ 称为欧拉数。 有恒等式 $x^n=\sum_m f_{n,m}\times {x+m\choose n}$，于是有 $f_{n,m}=\sum_{i=0}^m (-1)^i {n+1\choose i} (m+1-i)^n$，可以做 Bonus。有点困难，先不管了。 ### P3403 跳楼机 同余最短路，由于 $p$ 可达则 $p+x$ 一定可达，于是按对 $x$ 取模的结果分类，每一类找到最小的可达 $p$ 即可，这可以使用最短路求。通过同余最短路也可以证明小凯的疑惑一题，做过不管了。 ### [ARC147D] Sets Scores #### 题意 对于 $n$ 个集合 $S_i$，定义其合法当且仅当相邻两个集合对称差大小恰为 $1$。对所有合法的 $n$ 个集合，求所有数出现次数的乘积之和。$n,m\le 2\times10^5$。 #### 题解 拆乘法贡献，即对每个值枚举某次出现的集合编号 $a_i$，这样的编号 $n$ 元组数量就是某种集合方案的答案。另外描述一种方案可以使用 $S_1,d_i$，其中 $d_i$ 表示 $i,i-1$ 的对称差。注意到对于某种 $a,d$ 序列，使其合法的 $S_1$ 存在且唯一。于是答案为 $a,d$ 序列的方案数乘积，即 $n^mm^{n-1}$。快速幂，$\mathcal O(\log n+\log m)$。 ### P1758 [NOI2009] 管道取珠 平方拆贡献，即对每个 $a_i^2$，将整个过程同时做两次，结果序列相同的方案数即为每种结果的方案数平方和，复杂度 $\mathcal O(n^3)$。做过不管了。 ## 11.21 思考题 正难则反 - 求多少个 $n$ 阶排列 $p$ 满足不存在分界点 $1\le k\lt n$，使得 $\forall i\le k,j\gt k,p_i\lt p_j$。 设 $f_n$ 表示 $n$ 阶排列的答案，考虑取补集，枚举第一个合法分界点 $j$，则有 $\sum_{j<i}f_j\times (i-j)!+f_i=i!$，于是 $f_i=i!-\sum_{j\lt i}f_j\times (i-j)!$，可以 $\mathcal O(n^2)$ 求出。 - 求有多少个点数为 $n$ 的有标号无向简单连通图。 设 $f_n$ 表示 $n$ 个点的答案，仍然取补集，枚举 $1$ 所在的连通块大小，则有 $\sum_{j\lt i} f_j\times 2^{i-j\choose 2}\times {i-1\choose j-1}+f_i=2^{i\choose 2}$，还是可以 $\mathcal O(n^2)$ 递推出来。 - 求有多少个点数为 $n$ 的有标号无向简单边双连通图。 太困难，没有听懂，似乎需要 Prufer 序列 + 前缀和推一推。$n\le 10^5$ 版本是 P5828。 ### CF1750F Majority #### 题意 对于一个 $0,1$ 序列，每次操作可选择两个 $1$ 的位置 $l\lt r$，要求区间 $[l,r]$ 内的 $1$ 不少于 $0$，之后将该区间覆盖为 $1$。一个序列合法当且仅当可以通过该操作变为全 $1$，求长为 $n$ 的合法序列数量，对输入的 $m$ 取模。$n\le 5000$。 #### 题解 首先考虑如何判断一个序列是否合法，发现可以不断任意操作，直到无法进行，可以注意到最终序列是唯一的。于是可以根据最终序列计数，同时考虑正难则反，尝试对不合法序列分类计数。 于是设 $f_{i,j}$ 表示长为 $i$ 且两端为 $1$ 的序列，且最终序列最后一段 $1$ 长为 $j$ 的方案数，答案为 $f_{n,n}$，根据总方案数有 $\sum f_{i,j}=2^{i-2}$。于是可以先求 $j<i$ 的部分，剩下的就是 $f_{i,i}$。转移考虑枚举上一段 $0$ 和再上一段 $1$ 的长度 $m,k$，有 $f_{i,j}=f_{j,j}\times \sum_{m\gt k+j} f_{i-j-m,k}$。 考虑优化转移，令 $p=i-j-m,m=i-j-p$，则有 $i-j-p\gt k+j$，即 $p+k\lt i-2j$。于是转化为 $f_{i,j}=f_{j,j}\times \sum_{p+k\lt i-2j} f_{p,k}$，后面这个容易前缀和优化，于是转移变成 $\mathcal O(1)$ 的，可以做到 $\mathcal O(n^2)$ 的复杂度。 ### [AGC067B] Modifications ### CF1605F PalindORme 均为正难则反思想的应用，之后应该会做。 ## 11.23 杂题 CF1543E、CF1548D2、CF1552E 被弃了，太抽象。 ### P13494 【MX-X14-T4】分门别类 #### 题意 给定 $n$ 个数的可重集，将其分成若干个子集，要求每个子集内没有相同数且大小为偶数。判断无解，构造一组子集数量最小的方案。多测，$\sum n\le 10^3$。 #### 题解 答案显然可二分，直接增加空集合即可。考虑 DP check $x$ 个集合是否合法，设 $f_{i,j}$ 表示填了前 $i$ 种数，当前 $j$ 个集合大小为奇数是否可行，则 $f_{i-1,j}\rightarrow f_{i,j+a_i-2k},k\in[\max(0,j-x+b_i),\min(j,b_i)]$。由于转移过程中 $k\le b_i$，所以 $(i,k)$ 的数量为 $\mathcal O(n)$，单轮复杂度 $\mathcal O(n^2)$，乘上外层二分是 $\mathcal O(n^2 \log n)$，可以通过。 注意到这个 DP 能整体维护，即 $f_i$ 中合法的奇数 $j$ 和合法的偶数 $j$ 分别是连续段，可以优化复杂度。另外还有去二分做法，不过都没研究。 ### CF1548C The Three Little Pigs #### 题意 给定 $n$，$q$ 次询问 $\sum_{i=1}^n{3i\choose x}$。$n\le 10^6,q\le 2\times 10^5$。 #### 题解 考虑按 $n$ 对 $3$ 取模的结果分类，从而求出所有 $x$ 的答案。设 $f_{x,i}=\sum _{j=0}^{n-1} {3j+i\choose x}$，答案即为 $f_{x,0}+{3n\choose x}$。尝试递推出 $f$ 的值，首先有 $f_{x,0}+f_{x,1}+f_{x,2}=\sum_{j=0}^{3n-1}{j\choose x}={3n\choose x}$。另外有 ${n\choose m}={n-1\choose m-1}+{n-1\choose m}$，根据这个可以写出 $f_{x,j}+f_{x-1,j}=f_{x,j+1},j\in\{0,1\}$。于是有了三个方程表示 $f_{x,i}$ 三个数，可以从 $f_{x-1}$ 递推到 $f_x$，总复杂度 $\mathcal O(n+q)$。 另外还有生成函数做法，根据二项式定理有 ${3i\choose t}=[x^t](x+1)^{3i}$，于是 $t$ 的答案为 $[x^t]\sum_{i=1}^n(x+1)^{3i}$，后面这个可以等比数列求和，分母是两个组合数，分子次数只有 $3$，可以暴力除。总复杂度 $\mathcal O(n+q)$，常数略大，没写。