260404 - 260417
P6276 [USACO20OPEN] Exercise P
P14834 [THUPC 2026 初赛] 庭中有奇树
P10786 [NOI2024] 百万富翁
CF2161F SubMST
qoj17256 Keep or Gamble
拆贡献，对于一个局面 \((u,t,c)\)，我们知道进行下一步游戏的期望收益，如果该值为正那么继续游戏否则立刻停止。由于肯定是越玩收益越小，所以进入一个局面的方案数就是一个组合数。然后枚举 \(u+t\)，里面形如一个枚举 \(u\) 的 \(\sum \binom{U}{u}\binom{T}{s-u}\) 再乘以一些和 \(u\) 有关的和和 \(u\) 无关的。然后 \(s\) 变化的时候可以根据组合意义递推上面的和式。
uoj52 元旦激光炮
同时对三个序列二分，每次可以丢掉一个序列的一半，所以是 \(3\log n\) 的。
P1117 [NOI2016] 优秀的拆分
P5279 [ZJOI2019] 麻将
KH 题单
AT_agc021_e [AGC021E] Ball Eat Chameleons
qoj14691 Killing Bits
其实只要存在匹配就一定有解，可以调整证一下。匹配用高维前缀和优化建图跑 Dinic。
AT_agc059_e [AGC059E] Grid 3-coloring
P5644 [PKUWC2018] 猎人杀
AT_arc204_c [ARC204C] Maximize Sum of Mex
首先贡献可以拆成 \(0\) 产生贡献 \(2\)，\(01\) 产生贡献 \(1\)，\(00\) 产生贡献 \(-1\)。如果我们决策了 \(0\) 的位置，那么剩余的每个位置放 \(1\) 都会产生对应的贡献，肯定贪心从大往小取。这样放 \(0\) 的策略其实是很显然的。
字符串专题
AT_abc452_g [ABC452G] 221 Substring
插入分隔符或者不插，然后 SA。
P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3
P4384 [八省联考 2018] 制胡窜
转化成用两个端点切割所有出现位置。分讨第一个端点的位置然后计算第二个端点的数量，差不多是形如 \((p_{i+1}-p_i)(p_{i+1}+len-p_k-1)\)，将它展开后只需要维护一些 \(\sum p_ip_{i+1},~\sum p_i,~\sum p_i^2\)，边界处有些不同，用线段树上二分找到边界，特殊算一下就行。
P6793 [SNOI2020] 字符串
lcp 可以直接上树，可以进一步观察到许多性质。问题转化为每次我们选择两个 lcp 最大的子串进行匹配，其实可以不用写堆什么的，直接按 ht 从大往小合并维护连续段即可，本质上就是对后缀树逆 bfs 序遍历。
260414 模拟赛 T1
有一个长为 \(n\) 的序列 \(a\)，你要支持三种操作：
- 对所有 \(i\in [1,n)\)，同时进行 \(a_i\gets a_i\oplus a_{i+1}\)；
- 对所有 \(i\in (1,n]\)，同时进行 \(a_i\gets a_i\oplus a_{i-1}\)；
- 查询区间异或和；
\(n\le 3\times 10^5,~a_i\le 10^9\)
感觉线段树等是没有前途的，于是考虑操作分块，发现查询是差不多能做到 \(O(B)\)，因为贡献系数差不多就是组合数 \([j\subseteq i]\)。但是两边的东西会出锅，发现两边一共只有 \(O(n)\) 个点，所以每个块直接暴力把两边算一下。然后重构还是会爆，发现取 \(B=2^k\) 将只有两个位置有贡献，所以是对的。
场切是强大的。
260416 模拟赛 T1
有 \(4n\) 张牌，有 \(n\) 种颜色，每种颜色有 \(4\) 张。称一个牌的集合是胡的当且仅当有 \(4\) 种不同的颜色出现过 \(3\) 次以上，以及 \(5\) 种不同的颜色出现过 \(2\) 次以上。求随机发牌，胡牌次数期望。
\(n\le 2\times 10^6\)
肯定先拆贡献。由于牌有标号所以我们需要对每个 \(k\) 求出有多少个集合 \(|S|=k\) 是不胡的。枚举出现 \(3,4\) 次的牌有多少种，对应的生成函数如下：
当然还需要乘组合数。考虑如何求 \([x^k](1+4x+6x^2)^n\)，这种东西直接求导，然后列出一个线性微分方程，直接做即可。