专栏文章

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

KKSCD_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min53ff3
此快照首次捕获于
2025/12/01 20:42
3 个月前
此快照最后确认于
2025/12/01 20:42
3 个月前
查看原文

11.12 图论

  • 局部：枚举最小图，按照是否含有该局部将所有图分类。
比如平面图不含 K5,K3,3K_5,K_{3,3}，半平面图不含 K4,K2,3K_4,K_{2,3}。
  • 生成树（DFS 树 / BFS 树 / 最小生成树）

杂题

题意

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

题解

将定义过程倒过来，每次从原图和补图中选一个，递归进每个连通块分别判断。注意到原图和补图至少有一个连通，对这个图拆连通块递归下去。这需要对原图和补图分别进行搜索，原图显然可以 O(m)\mathcal O(m) 搜索，对于补图可以 BFS，使用链表维护所有没搜过的点，这样额外复杂度是所有点度数之和，也是 O(m)\mathcal O(m) 的。
分析一下复杂度，有 T(m)=O(m)+T(m−m)T(m)=\mathcal O(m)+T(m-\sqrt m)，这样的话总复杂度为 O(mm)\mathcal O(m\sqrt m)。至于为啥能使边数减少 m\sqrt m，首先每次所用的图一定是上次的补图，于是每两轮就会用一次原图的补图。而每次用原图的补图划分连通块时，上轮同一连通块内的边若两端被划分进了不同连通块，则之后就没用了。感性理解这个过程中废弃的边是比较多的，因为不同连通块间的完全 kk 部图边全没了。具体不会证，没题写不了，不管了。

P11762 [IAMOI R1] 走亲访友

题意

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

题解

由于要求保留生成树，直接先跑出一棵来，不妨以 ss 为根，现在要求路径经过非树边至少一次，这应该是欧拉路径状物，为方便直接做欧拉回路，这样要求每个点度数均为偶数。初步想法是树边可以不走，于是决策一下树边是否经过就可以满足度数限制了，然后做到了路径长度不超过 mm？
并非，因为欧拉回路还需要图连通，而断掉若干树边后图不一定连通了。于是每条树边也得经过至少一次，在此基础上决策若干树边多走一次即可。路径长度不超过 n+m−1n+m-1，复杂度 O(n+m)\mathcal O(n+m)。

典题

  • 给定无向图，求所有点度数均为偶数的边生成子图个数。
找一棵生成树，非树边任意选之后合法树边是存在且唯一的，于是一个连通图方案数为 2m−n+12^{m-n+1}，总方案数为 2m−n+k2^{m-n+k}，其中 kk 为连通块个数。
  • 给定无向图，求所有点度数均为奇数的边生成子图个数。
若连通图点数为奇数，则方案数一定为 00，否则方案数仍为 2m−n+12^{m-n+1}，推理相同。总方案数为 2m−n+k2^{m-n+k} 或 00，且只在存在点数为奇数的连通块时为 00。
  • 给定无向图，每个点限制度数为偶数 / 奇数 / 无限制，求满足条件的生成子图个数。
对于一个连通图，若所有点均有限制，直接判断总度数是否为偶数即可，是则答案为 2m−n+12^{m-n+1}，否则为 00。若存在点无限制，考虑枚举每个点度数奇偶性，一定恰有一半方案奇偶性是对的。设存在 tt 个无限制点，则方案数为 2m−n+t2^{m-n+t}，将所有连通块的答案乘起来即可。

P7624 [AHOI2021初中组] 地铁

题意

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

题解

考虑如何判断环长 xx 是否合法，可以把限制建成差分约束，只要没有负环就存在解。此时 u<vu\lt v 的限制只有值，而 u>vu\gt v 的限制里含 xx。考虑对于图中的一个环，若 xx 的系数和为正则限制 xx 为一个后缀，为负则限制 xx 为一个前缀，这说明合法 xx 形成一个区间。
于是二分，对于 x=midx=mid 跑差分约束，若存在负环再判一下环上系数和，从而实现找到合法区间左右端点。注意此处途径边数超过 nn 的点不一定在负环上，也可能在负环延伸出去的链上，所以要先跳 nn 次前驱再求负环。总复杂度 O(nmlog⁡V)\mathcal O(nm\log V)。

P3645 [APIO2015] 雅加达的摩天楼

题意

nn 个点上有 mm 个人，每个人有参数 dd，从 pp 点可移动到 p+d,p−dp+d,p-d 之一。现要从 00 传递情报到 11，只有拿到情报的人才能移动，求最少移动次数。n,m≤3×104n,m\le 3\times 10^4。

题解

考虑暴力，从 pp 向 p+kdp+kd 连权为 ∣k∣\left|k\right| 的边后直接跑最短路即为答案。可以优化建图，令 B=nB=\sqrt n，则所有 d>Bd\gt B 的边共 O(mn)\mathcal O(m\sqrt n) 条。对于 d≤Bd\le B 的边，按 dd 和 p mod dp\bmod d 分类，每类中向前的边连到上一个有人的点即可，于是每类有 O(nd)\mathcal O(\frac nd) 条边，共 dd 类，总边数为 O(nn)\mathcal O(n\sqrt n)。这样只能跑 Dijkstra，可能要带个 log，没有写。
考虑换一种方式，设 fi,df_{i,d} 表示当前参数为 dd 的人在 ii 点需要的最少移动次数。d≤Bd\le B 的状态数不超过 O(nn)\mathcal O(n\sqrt n)，d>Bd\gt B 的状态数不超过 O(mn)\mathcal O(m\sqrt n)，总状态数是有保证的。另外这样转移只有在某个点上转到别的人，或者向前后跳一步，边权只有 0,10,1，可以 0101 BFS 解决，复杂度 O((n+m)n)\mathcal O((n+m)\sqrt n)。

11.12 思考题 复读机

以下问题中给定一个序列，可以重复读入，但只有 O(1)\mathcal O(1) 内存。序列中的值均为正整数。（当然原题是自然数，此时给所有数加上 11 即可）
  • 序列中只有一种数出现奇数次，找出这种数。
直接求序列所有值的异或值即为答案，读入 11 遍，记录 11 个数。
  • 序列中只有两种数出现奇数次，找出这种数。
确定性算法：先求出所有值的异或值 x⊕yx\oplus y，找到其中某个 11，按照这一位的值分成两个集合，对两个集合各做一种数的情况即可，这可以在同一遍读入中求。读入 22 遍，记录 22 个数。
非确定性算法：每轮可通过哈希将所有种类的值随机分成 cc 个集合，只要 x,yx,y 分到不同集合就能求出答案，错误率 1c\frac 1c。可以进行常数 tt 轮，多轮求解可在同一遍读入中求，读入 11 遍，记录 tctc 个数，错误率 1ct\frac 1{c^t}。一般来说 cc 取距 ee 最近的整数 33 最优。
还有一种做法，准备 2k2k 个集合，其中 kk 为奇数。设计一个函数 f(x)f(x)，返回 [1,2k][1,2k] 的一个大小为 kk 的子集，将该子集内的集合值均异或上 xx。这样当且仅当 x,yx,y 随机出来的子集完全相同时求不出答案，否则可以通过 x,y,x⊕yx,y,x\oplus y 中 x,yx,y 出现次数相同求出答案。读入 11 遍，记录 2k2k 个数，错误率 (2kk)−1{2k\choose k}^{-1}。LCA 说这种方法已经接近信息论的错误率下界了，不懂。
  • 序列中只有两种数出现次数不为 33 的倍数，找出这种数。
首先若只有一种数出现次数不为 33 的倍数，可以直接在三进制下每一位求和再对 33 取模，再按 cx mod 3c_x\bmod 3 分讨即可，这个值与 n mod 3n\bmod 3 相等。读入 11 遍，记录 11 个数。
确定性算法：将所有值转化为二进制，记录每个二进制位 11 的个数对 33 取模的结果。之后可以根据 cx+cy≡n(mod3)c_x+c_y\equiv n\pmod 3 分讨，找到某个 x,yx,y 不同的二进制位，再按这一位分组进行一种数的情况，同样可以同一遍求。读入 22 遍，记录 22 个数。
非确定性算法：与上个题次数奇偶性的做法相同，可能会多一些对出现次数的分讨，记录数字个数可能要乘上一个常数，不再赘述。

U498564 找不同

题意

给定长为 2n+32n+3 的序列，其中 nn 种数出现两次，33 种数只出现一次。只有 O(1)\mathcal O(1) 空间，找出只出现一次的三种数，序列输入四次。n≤7×105n\le 7\times 10^5。

题解

考虑分离出一个数，转化成两种数的情况。将序列所有值异或起来可得 X=x⊕y⊕zX=x\oplus y\oplus z，定义 bi=ai⊕Xb_i=a_i\oplus X，则 bb 中出现奇数次的只有 x⊕y,x⊕z,y⊕zx\oplus y,x\oplus z,y\oplus z 三个数。显然三者两两不同，且异或值为 00，这说明每个二进制位上均全 00 或恰有两个 11。
于是考虑最低位的 11，设 xx 最低位的 11 为 f(x)f(x)。根据上面的结论，三个数的 ff 值恰有两个相同。于是先求出全局 ff 值的异或和，就得到了其中一个数的 ff 值 YY。按照 ff 值是否等于 YY 将序列分成两部分，各有 1,21,2 个出现一次的数，套用上面的做法即可。读入 44 遍，粗糙实现可以记录 77 个数。

LOJ6537. 毒瘤题加强版再加强

题意

给定长为 nn 的序列，其中恰有 kk 个数出现奇数次。只有 O(1)\mathcal O(1) 空间，找出这 kk 个数。n≤3×106,k≤5000n\le 3\times 10^6,k\le 5000，空间限制 3MiB。

题解

太难了，直接考虑非确定性算法。考虑设计哈希函数 f(x)f(x)，开 tt 个大小为 O(m)\mathcal O(m) 的哈希表，每输入一个 xx 就向所有哈希表的 f(x) mod mif(x)\bmod m_i 位置异或上 f(x)f(x)。最后取出哈希表所有未冲突位置的值 f(x)f(x)，将其转换回 xx 输出。
首要问题是，需要设计一个这样的函数 ff，需要大致随机，能以较高正确率判断一个值是否是该函数值，且能快速转换回 xx。采用 f(x)=kx+bf(x)=kx+b，kk 取大质数，这样判断 yy 就可以检查 y mod ky\bmod k 的值是否为 bb 了，转换回 xx 只需要除以 kk 下取整即可。
这样就得到了一个算法。分析一下错误率，需要 kk 个数均被找到，这需要每个数都在 tt 个哈希表中的至少一个不冲突，单个冲突概率为 O(km)\mathcal O(\frac km)，于是单个数正确概率约为 1−(km)t1-(\frac k m)^t，于是正确率为 (1−(km)t)k(1-(\frac km)^t)^k，当然这是忽略哈希值转换错误率的结果。对于本题，大概可以取 t=7,m=30000t=7,m=30000，有 0.980.98 左右的正确率。

11.14 字符串

问题：
  • 子串匹配
  • 子串约束（Border / 周期、回文）
  • 其他（子序列等）
算法：自动机（字典树）、“莫队”思想、Hash。
用 Trie 树刻画字符串集合，若只判断某串是否在集合内，可以按未来可以走的串缩等价类得到 DFA。同样用 DFA 刻画所有包含串 SS 的串，自动机的不同状态分别为串后缀为 SS 前缀的长度。
考虑转移，发现关心 SS 所有前缀的 Border。注意到一个串的 Border 由于传递性具有全序，于是记录最大真 Border 即可。然后就发明了 MP 算法，当然这也就是一般说法中的 KMP。若预处理 tri,jtr_{i,j} 表示状态 ii 加上字符 jj 到的状态，就得到了 KMP 自动机（Trie 图）。
有一些结论，比如最大周期等于长度减最小 Border 之类，手推可知。
若求多个前缀的公共 Border，可在失配树上求 LCA。扩展到多串变成 AC 自动机了，超纲。使用“莫队”思想还可以推出扩展 KMP 和 manachar，略过不表。
Hash，B,PB,P 取质数，也可以将每种字符随机映射之后计算，在减法之类的东西上有奇效。一般来说要使得哈希空间比比较次数的平方略大，双哈希一般够了。集合哈希可以使用异或之类。其他哈希可以尽量转化成序列或集合哈希。

LOJ502. 「LibreOJ β Round」ZQC 的截图

没太懂这个题，之后可能会做。

P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

一顿转化之后需要对每个连通块维护根节点对于所有串的 0/10/1 信息，在这里使用哈希。之后应该会做。

11.19 组合计数

判定型计数（唯一判定、最小表示、取补集、容斥拆贡献）
“证书”定义为某种使方案合法的方案，最小表示即找到某个特定“证书”并对其计数，取补集即统计无“证书”的方案数。
考虑局部信息，大概意思是判定相邻元素合法，从而整个方案合法。

CF559C Gerald and Giant Chess

题意

给定长宽分别为 h,wh,w 的网格，有 nn 个障碍，求从左上到右下不经过障碍的路径条数。h,w≤105,n≤2000h,w\le 10^5,n\le 2000。

题解

考虑取补集。考虑设 fif_{i} 表示不经过其他障碍走到 (xi,yi)(x_i,y_i) 的方案数，初值为 (xi+yi−2xi−1){x_i+y_i-2 \choose x_i-1}。另外对于所有 xj≤xi,yj≤yix_j\le x_i,y_j\le y_i 的 jj，要减掉实际上首个障碍为 jj 的方案数，即 fi←fi−fj×(xi−xj+yi−yjxi−xj)f_i\leftarrow f_i-f_j\times {x_i-x_j+y_i-y_j\choose x_i-x_j}。最后用 (h+w−2h−1)h+w-2\choose h-1 减掉所有 ff 的和即可，复杂度 O(max⁡(h,w)+n2)\mathcal O(\max(h,w)+n^2)。

P11588 [KTSC 2022 R2] 彩色括号序列

题意

给定一个带颜色的括号序列，要求选出一个子序列，使得相邻括号和匹配括号颜色均不同，求能选出的本质不同合法子序列数量。n≤700n\le 700。

题解

如果是下标不同子序列，可以设 fl,rf_{l,r} 表示在 [l,r][l,r] 内选，强制选 l,rl,r 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于每种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 x,yx,y 满足 prey≤xpre_y\le x，其中 preypre_y 表示 yy 上次出现的位置。这样是局部限制，可以在 DP 过程中满足，最终只对不存在 prelpre_l 的 fl,rf_{l,r} 统计即可。
考虑转移，分为 l,rl,r 匹配和不匹配两种。前者枚举内部选的左右端点 x,yx,y ，不要求 x,yx,y 匹配，限制为 cl≠cr,cl≠cx,cr≠cy,prex≤l,prer≤yc_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y；后者枚举与 ll 匹配的 xx，再枚举 xx 之后第一个左括号 yy，要求 l,xl,x 匹配，不要求 y,ry,r 匹配，限制为 cl≠cx,cx≠cy,prey≤xc_l\ne c_x,c_x\ne c_y,pre_y\le x，复杂度 O(n4)\mathcal O(n^4)，常数很小。
注意到对于方案中相邻的 x,yx,y，固定 yy 时后缀 xx 合法，但固定 xx 时合法的 yy 没有规律，似乎不太容易直接前缀和优化。注意到转移时 yy 的限制只与 x,rx,r 有关，于是设 gx,r,hx,rg_{x,r},h_{x,r} 分别表示固定 x,rx,r 时，两种转移的合法 yy 对应值之和。此时 fl,r,1f_{l,r,1} 只会贡献到 gl,tg_{l,t} 和 ht,rh_{t,r}，也就是 O(n)\mathcal O(n) 个值中。转移时枚举 xx 后可以 O(1)\mathcal O(1)，于是总复杂度为 O(n3)\mathcal O(n^3)，好像常数还是不大啊。

P14364 [CSP-S 2025] 员工招聘

暂时不想做这题，没听。或许 NOIP 前会回来补掉。
  • 子集容斥
有 nn 条限制，求所有限制均满足，即不合法限制集合为空集的方案数，当容易算某子集强制不合法，其余不作限制的方案数时可使用子集容斥。
具体地，枚举集合 SS 内的限制均不满足，设 f(S)f(S) 表示方案数，则答案为 ∑(−1)∣S∣f(S)\sum (-1)^{\left|S\right|}f(S)。

P6076 [JSOI2015] 染色问题

题意

给定 n×mn\times m 网格和 cc 种颜色，要求每行每列不能全无色，且每种颜色均出现，求方案数。n,m,c≤400n,m,c\le 400。

题解

直接子集容斥，枚举 i,j,ki,j,k 表示 ii 种颜色不出现，jj 行 kk 列全无色，答案为 ∑i≤c(∑j≤n(∑k≤m(c−i+1)(m−k)(n−j)×(−1)k×(mk))×(−1)j×(nj))×(−1)i×(ci)\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}，也就是 ∑i≤c,j≤n,k≤m(c−i+1)k×(ci)×(nj)×(mk)×(−1)i+j+k\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}，枚举 ii 后先预处理 (c−i+1)(c-i+1) 的若干次方即可做到 O(nmc)\mathcal O(nmc)。
或者可以只容斥两层，对于最后一层不枚举 kk，而是直接计算出 (c−i)(c-i) 种颜色填 (n−j)×m(n-j)\times m 网格的方案数，要求每列不全无色，答案为 ((c−i+1)(n−j)−1)m((c-i+1)^{(n-j)}-1)^m，再套上前两层的容斥系数即可，这里好像只能快速幂了，复杂度 O(cnlog⁡m)\mathcal O(cn\log m)。

P1450 [HAOI2008] 硬币购物

题意

给定四种钱币，价值分别为 cic_i。qq 次询问给出 di,md_i,m，表示有 did_i 个价值为 cic_i 的钱币，求和为 mm 的方案数。q≤1000,ci,di,m≤105q\le 1000,c_i,d_i,m\le 10^5。

题解

所用个数不超过 did_i 有点难做，考虑容斥变成所用个数超过 did_i。具体地，枚举 SS 内的种类一定超出限制，其余任意。求出 SS 内 ci(di+1)c_i(d_i+1) 的和，若其不超过 mm 则方案数为 fm−sf_{m-s}，其中 ff 为任意取所有钱币的方案数，可以提前完全背包预处理。总复杂度为 O(km+q×2k)\mathcal O(km+q\times 2^k)，本题中 k=4k=4。
  • 二项式反演
大概是若有 bi=∑j≤iaj×(ij)b_i=\sum_{j\le i} a_j\times {i\choose j}，则 aj=bj−∑j<iaj×(ij)a_j=b_j-\sum_{j<i} a_j\times{i\choose j}，可以顺序求出。
  • min-max 容斥
式子是 min⁡x∈Sx=∑T∈S(max⁡x∈Tx)×(−1)∣T∣+1\min_{x\in S} x=\sum_{T\in S}(\max_{x\in T} x)\times (-1)^{\left|T\right|+1}，两者反过来也是成立的，证明可以考虑只有空集的偶数子集比奇数子集多一个，其余集合的奇偶子集数量相同。感觉主要应用是求期望啊。
  • 点边容斥
对于统计合法连通块数量，枚举所有点统计并对方案数求和，再枚举所有边中点统计并减去方案数的和，这样每个连通块会被统计点数减边数次，次数恰为 11。
比如在圆方树上令圆点为 −1-1，方点为点双点数，u,vu,v 路径经过的所有点双点的并集（不包括 u,vu,v）大小即为圆方树上路径和。
  • 反射容斥
大概是在坐标系里将不合法的路径反射回去，变成两种路径数相减，典型应用是卡特兰数。
有一些拓展，比如有上下界限制时可以套多次反射容斥，状态数大概是 O(nm)\mathcal O(\frac nm) 的，其中 mm 为上下界之差。

P4769 [NOI2018] 冒泡排序

转化转化之后变成不存在三元下降子序列，然后画画图发现所有逆序对之间要递增，大概能用卡特兰数计算，之后可能会做。
下面这题是 LCA 讲思考题的时候讲的，由于这个思考题的前缀和差分比较基础，不开新标题了。

CF1097F Alex and a TV Show

题意

维护 nn 个可重集，支持将 xx 集合变为 y,zy,z 集合的并或者 y,zy,z 集合两两 GCD 形成的可重集，单点修改一个集合为单值集合，查询某集合内某数出现次数奇偶性。n≤105,q≤106,v≤7000n\le 10^5,q\le 10^6,v\le 7000。

题解

由于只关心奇偶性，个数 ai,ja_{i,j} 之类均对 22 取模存储即可。另外由于有变为两集合 GCD 的操作，考虑记录 bi,j=∑j∣kai,kb_{i,j}=\sum_{j\mid k}a_{i,k}，这样合并操作即 bx,j=by,jbz,jb_{x,j}=b_{y,j}b_{z,j}，取并集时即 bx,j=by,j+bz,jb_{x,j}=b_{y,j}+b_{z,j}，用 bitset 按位与和按位异或即可。
对于修改为单值集合，可以预处理出所有 xx 对应的集合状态。对于查询，需要枚举所有 x∣yx\mid y 且 μ(yx)≠0\mu(\frac yx)\ne 0 的位置异或和，也对每个 xx 预处理出这个即可。总复杂度大概是 O(vlog⁡v+qvw)\mathcal O(v\log v+\frac{qv}w)，可以通过。

11.21 组合计数

组合（双射）、代数（生成函数）。

某题

题意

给定 n,an+1n,a_{n+1}，要求 ai∣ai+1a_i\mid a_{i+1}，求合法序列数量，并对每种 aa 序列的数字种类数分别计算方案数。n≤105,an+1≤109n\le 10^5,a_{n+1}\le 10^9。Bonus：an+1≤1018a_{n+1}\le 10^{18}。

题解

将 an+1a_{n+1} 分解质因数为 ∏piki\prod p_i^{k_i}，之后每个质因子独立，且均满足次数不降，于是可分别求方案数再乘起来。对于 kik_i 来说方案数为 (ki+nn){k_i+n\choose n}，这是将 kik_i 分到差分数组的 (n+1)(n+1) 个位置的方案数，全乘起来即为答案 fnf_n。
至于出现 ii 种不同数的方案数，显然数字种类数不超过 O(log⁡V)\mathcal O(\log V) 级别。考虑先求出 gig_i 表示选出长为 ii 的单增序列方案数，一定有 fn=∑igi×(n−1i−1)f_n=\sum_i g_i\times {n-1\choose i-1}，于是先求出 ff 的前 log⁡V\log V 项再反演回 gg 即可，ii 种数的答案即 gi×(n−1i−1)g_i\times {n-1\choose i-1}。
但是 an+1≤1018a_{n+1}\le 10^{18} 没法分解质因数了，然而注意到本题做法只跟 kik_i 有关，于是枚举到 V3\sqrt[3] V 后只剩至多两个大质数乘积，即只可能是 p,p2,pqp,p^2,pq 三种，前两种都是好判的，这样就能得到 kk 序列了。没题写不了。

P2401 不等数列

题意

给定 n,mn,m，求 mm 对相邻值上升的 nn 阶排列个数。
Bonus：n,m≤105n,m\le 10^5，模数为质数。

题解

可以 O(n3)\mathcal O(n^3) DP，设 fi,j,kf_{i,j,k} 表示填了 ii 个数，jj 个上升且 ii 的相对排名为 kk 的方案数，前缀和优化转移即可。注意到有 j,k≤ij,k\le i，常数比较小，可以过。
设 fn,mf_{n,m} 表示答案，尝试递推，考虑排列中 11 的位置，从而从 n−1n-1 阶排列推过来。由于放到开头或某个下降位置会使上升位置增加，放到结尾或某个上升位置时上升位置数不变，有 fn,m=(m+1)fn−1,m−1+(n−m)fn−1,m−1f_{n,m}=(m+1)f_{n-1,m-1}+(n-m)f_{n-1,m-1}，就 O(nm)\mathcal O(nm) 了。fn,mf_{n,m} 称为欧拉数。
有恒等式 xn=∑mfn,m×(x+mn)x^n=\sum_m f_{n,m}\times {x+m\choose n}，于是有 fn,m=∑i=0m(−1)i(n+1i)(m+1−i)nf_{n,m}=\sum_{i=0}^m (-1)^i {n+1\choose i} (m+1-i)^n，可以做 Bonus。有点困难，先不管了。

P3403 跳楼机

同余最短路，由于 pp 可达则 p+xp+x 一定可达，于是按对 xx 取模的结果分类，每一类找到最小的可达 pp 即可，这可以使用最短路求。通过同余最短路也可以证明小凯的疑惑一题。

[ARC147D] Sets Scores

题意

对于 nn 个集合 SiS_i，定义其合法当且仅当相邻两个集合对称差大小恰为 11。对所有合法的 nn 个集合，求所有数出现次数的乘积之和。n,m≤2×105n,m\le 2\times10^5。

题解

拆乘法贡献，即对每个值枚举某次出现的集合编号 aia_i，这样的编号 nn 元组数量就是某种集合方案的答案。另外描述一种方案可以使用 S1,diS_1,d_i，其中 did_i 表示 i,i−1i,i-1 的对称差。注意到对于某种 a,da,d 序列，使其合法的 S1S_1 存在且唯一。于是答案为 a,da,d 序列的方案数乘积，即 nmmn−1n^mm^{n-1}。快速幂，O(log⁡n+log⁡m)\mathcal O(\log n+\log m)。

P1758 [NOI2009] 管道取珠

平方拆贡献，即对每个 ai2a_i^2，将整个过程同时做两次，结果序列相同的方案数即为每种结果的方案数平方和，复杂度 O(n3)\mathcal O(n^3)。

11.21 思考题 正难则反

  • 求多少个 nn 阶排列 pp 满足不存在分界点 1≤k<n1\le k\lt n，使得 ∀i≤k,j>k,pi<pj\forall i\le k,j\gt k,p_i\lt p_j。
设 fnf_n 表示 nn 阶排列的答案，考虑取补集，枚举第一个合法分界点 jj，则有 ∑j<ifj×(i−j)!+fi=i!\sum_{j<i}f_j\times (i-j)!+f_i=i!，于是 fi=i!−∑j<ifj×(i−j)!f_i=i!-\sum_{j\lt i}f_j\times (i-j)!，可以 O(n2)\mathcal O(n^2) 求出。
  • 求有多少个点数为 nn 的有标号无向简单连通图。
设 fnf_n 表示 nn 个点的答案，仍然取补集，枚举 11 所在的连通块大小，则有 ∑j<ifj×2(i−j2)×(i−1j−1)+fi=2(i2)\sum_{j\lt i} f_j\times 2^{i-j\choose 2}\times {i-1\choose j-1}+f_i=2^{i\choose 2}，还是可以 O(n2)\mathcal O(n^2) 递推出来。
  • 求有多少个点数为 nn 的有标号无向简单边双连通图。
太困难，没有听懂，似乎需要 Prufer 序列 + 前缀和推一推。n≤105n\le 10^5 版本是 P5828。

CF1750F Majority

题意

对于一个 0,10,1 序列，每次操作可选择两个 11 的位置 l<rl\lt r，要求区间 [l,r][l,r] 内的 11 不少于 00，之后将该区间覆盖为 11。一个序列合法当且仅当可以通过该操作变为全 11，求长为 nn 的合法序列数量，对输入的 mm 取模。n≤5000n\le 5000。

题解

首先考虑如何判断一个序列是否合法，发现可以不断任意操作，直到无法进行，可以注意到最终序列是唯一的。于是可以根据最终序列计数，同时考虑正难则反，尝试对不合法序列分类计数。
于是设 fi,jf_{i,j} 表示长为 ii 且两端为 11 的序列，且最终序列最后一段 11 长为 jj 的方案数，答案为 fn,nf_{n,n}，根据总方案数有 ∑fi,j=2i−2\sum f_{i,j}=2^{i-2}。于是可以先求 j<ij<i 的部分，剩下的就是 fi,if_{i,i}。转移考虑枚举上一段 00 和再上一段 11 的长度 m,km,k，有 fi,j=fj,j×∑m>k+jfi−j−m,kf_{i,j}=f_{j,j}\times \sum_{m\gt k+j} f_{i-j-m,k}。
考虑优化转移，令 p=i−j−m,m=i−j−pp=i-j-m,m=i-j-p，则有 i−j−p>k+ji-j-p\gt k+j，即 p+k<i−2jp+k\lt i-2j。于是转化为 fi,j=fj,j×∑p+k<i−2jfp,kf_{i,j}=f_{j,j}\times \sum_{p+k\lt i-2j} f_{p,k}，后面这个容易前缀和优化，于是转移变成 O(1)\mathcal O(1) 的，可以做到 O(n2)\mathcal O(n^2) 的复杂度。

[AGC067B] Modifications

CF1605F PalindORme

均为正难则反思想的应用，之后应该会做。

11.23 杂题

CF1543E、CF1548D2、CF1552E 被弃了，太抽象。

P13494 【MX-X14-T4】分门别类

二分，可以 O(n2)\mathcal O(n^2) DP 来 check。或者整体维护 DP，复杂度可以优化。之后应该会做。

CF1548C The Three Little Pigs

生成函数推导 / 组合意义推，可以得到递推式，之后应该会做。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...