省选-做题练习

260615

CF2042F Two Subarrays

CF2042F Two Subarrays。

这样不行的话，我们就从左右两个端点思考：

先考虑 $cost(l,r)$：$s_r+b_r-s_{l-1}+b_l$。

然后我们设数组 $L_i=b_i-s_{i-1}$，$R_i=s_i+b_i$。最后的答案就是求 $i,j,x,y$ 使得 $L_i+R_j+L_x+R_y$ 最大。

我们尝试用线段树维护，有亿点点复杂。

反正关键点就是类似线段树的 dp 形式左右区间的相互贡献加上原本的。

CF1721F Matching Reduction

CF1721F Matching Reduction。

容易从最大匹配想到 König 定理，我们就把问题转化成了最小点覆盖大小减一。

CF2215D EXPloration, EXPloitation, and Gain Some EXPerience!

CF2215D EXPloration, EXPloitation, and Gain Some EXPerience!。

我们发现这道题 $n$ 很大，但是 $m$ 很小。我们的切入口应该是枚举 $n$ 操作 $m$，但是显然不行，于是可以想到矩阵快速幂等东西来维护。

比较显然的问题转化是，我们需要保证相邻的列的区间 $l,r$ 有相交。

然后用前缀和优化：

接着我们需要压掉 $i$ 这一维。我们尝试直接转移 $s$ 和 $t$。我们甚至还能发现这玩意儿是对称的，也就是 $s_i=t_{m-i+1}$。

然后我们放进矩阵考虑怎么转移。

20260616

CF1559D2 Mocha and Diana (Hard Version)

CF1559D2 Mocha and Diana (Hard Version)。

首先肯定是贪心。我们先来看看怎么加最多的边，我们可以发现，最后如果两个都不是树，那么我们模拟一下，假如一个森林是两个连通块，那么这两个连通块任意两点间都需要联通，所以和另一个森林不是树矛盾。

所以我们可以得到结论：最后至少有一颗森林是树。

于是我们考虑求方案。

我们从最简单的考虑：对于一个点，我们能连就连。然后就会发现两个森林都可能有点和这个点没有连边，于是考虑处理一下。

我们发现这两个森林与选定的点在同一个连通块的点集可以相互连任意的边，因为连边了不会构成环。

AT_abc248_g [ABC248G] GCD cost on the tree

AT_abc248_g [ABC248G] GCD cost on the tree。

其实这种题是有套路成分的，我们先是按照 $\gcd$ 来进行分类。

$g_i$ 表示是 $i$ 的倍数的时候的情况数，$f_i$ 表示是 $i$ 的时候的情况数。引入 $g$ 是因为我们无法只保留 $a_x=i$ 的。

我们先想办法求 $g$，先尝试只保留 $x|a_i$。

我们需要求出 $\sum res_i$ 表示当前点子树中所有的链长 $>1$ 的长度和。然后过程中需要一些中间量辅助。

CF1635E Cars

CF1635E Cars。

只要是两者之一，就一定方向相异。如果无关紧要，就是背向而行，如果命中注定，就是相向而行的。

我们先钦定一个点的方向，然后与之相关的点看看放左边还是右边。

类似于 2-sat 的思想，我们对一个点建立两个点，一个表示向右走需要满足的条件，一个表示向左走需要满足的条件。

合法性可以先通过方向染色判断。

P7889 「MCOI-06」Eert Tuc Knil

P7889 「MCOI-06」Eert Tuc Knil。

注意这道题会有负数。

选含 $u$ 连通块总和： $\max (val + x\cdot sz)$ 最优解形如 $ans(u,x)=sz_u x + val_u$。

我们需要考虑子块并入父亲的临界： $t_v=\left\lceil \frac{-val_v}{sz_v} \right\rceil$ $x\ge t_v$ 一定会合并，并且不会再分开了。

所以我们询问按 $x$ 升序；单点初始为块，全部 $t_v$ 丢小根堆。

遍历询问，弹出 $t_v\le x$ 的块，并查集合并到父块，重算新块阈值入堆。

DFS 序差分，树状数组子树查询得 $sz_u,val_u$，代入式子得答案。

注意：除法是向 $0$ 取整，所以可以用 ceil。

CF868F Yet Another Minimization Problem

CF868F Yet Another Minimization Problem。

这道题看着就像 dp。

这让我们想起了决策单调性。

我们需要证明这个有决策单调性，回忆一下 $\min$ 的决策单调性：

这个还是很容易证明的，所以这道题有了决策单调性。

然后就可以直接做了。

P4262 [Code+#3] 白金元首与莫斯科

P4262 [Code+#3] 白金元首与莫斯科。

插头 dp：

$f_{i,j,s}$ 表示到了 $(i,j)$，现在轮廓线的状态为 $s$。

分类讨论：

• 如果现在是障碍点，只要没有向右或向下的插头就行了。

• 不是障碍点也没有下/右插头，我们可以创建/不创建插头。

• 有下/右插头，可以直接连成一块。

• 都有就不合法。

枚举每一个点作为障碍点，$O(n^2m^22^m)$，需要优化。

神奇的方法：倒着再做一遍，这样就可以相当于“跳过这个点”。

20260618

CF1473E Minimum Path

CF1473E Minimum Path。

我们发现减去的是最小值，加上的是最大值，所以我们可以想到对于没一条路径，我们需要让其权值更小。

这让我们想到了分层图最短路，是否已经决定了最大/小值。

AT_arc068_d [ARC068F] Solitaire

AT_arc068_d [ARC068F] Solitaire。

相当于制作一个单谷函数，然后再做一个以这个函数的下标为单谷的函数。

然后我们在草稿本上画画图吧。

我们考虑拆分。前 $k-1$ 个是由两个单调递减的序列混合而成的，第 $k$ 个是 $1$，后面的是任意的，$2^{n-k-1}$ 种。

我们现在需要考虑前 $k-1$ 个，需要满足的条件是，两个序列，一个最小值为 $1$，另一个的最小值需要大于剩下的序列的最大值。

我们设左边是最终会加入 $1$ 的。

尝试 dp，设 $f_{i,j}$ 表示拿出了 $i$ 个数，然后最后没有选到 $1$ 的序列的最小值为 $j$。

• 加入左边：$f_{i+1,j}+=f_{i,j}$。

• 加入右边：$f_{i+1,j}=\sum_{j'>j}f_{i,j'}$。

最后的答案：

AT_agc002_f [AGC002F] Leftmost Ball

AT_agc002_f [AGC002F] Leftmost Ball。

$f_{i,j}$ 表示有 $i$ 个白球，$j$ 种其他颜色的球。

需要注意的一点是 -1，表示房钱颜色需要固定到第一个空位，保证不和其他颜色综合起来重复计算。

注意代码需要 inv[0]=1;。

P6383 『MdOI R2』Resurrection

P6383 『MdOI R2』Resurrection。

这道题是结论题，需要发现一个结论：对原树上任意两个有祖先后代关系的点 $u,v$，它们在 $G$ 中的连边对应的原树路径，要么完全嵌套，要么完全相离，绝对不能交叉。

结论可以手搓搓出来，拿链来试。

我们发现如果当前边被断了，那么这个连通块的祖先就变成了这条边上的点，而不是原来的祖先了。

用这个思路去想，我们发现是无法做到交叉的。至于充分怎么证明：

初始决策集合：放入 G 中根的所有直接子节点。重复执行：

• 选出决策集合里编号最小的节点 $u$。
• 将 $u$ 在原树中的父边加入删边序列 $p$。
• 从集合中移除 $u$，将 $u$ 在 $G$ 中的所有直接子节点加入集合。

最终得到的排列 $p$ 即为合法删边顺序。我们发现是可行的。

从下往上 dp，答案延迟计算 dp。

$f_{i,j}$ 表示到了 $i$，祖先有 $j$ 个可以和它连边的时候的答案。

$x$ 是枚举 $i$ 用了哪个祖先节点。

可以前缀和优化 dp。

P6071 『MdOI R1』Treequery

P6071 『MdOI R1』Treequery。

这种点很多的题目我们可以考虑 LCA。

我们尝试求出 LCA，然后可以发现。

• 如果 $p$ 是父亲，答案就是 $dis(p,LCA)$。

• 如果没有关键点是 $p$ 包含祖先和后代，答案就是 $0$。

• 如果没有关键点是 $p$ 的祖先/后代，答案就是 $dis(p,LCA)$。

• 否则就是 $p$ 与其他点最深的 LCA 的距离。

需要普通线段树维护 LCA，还需要可持久化线段树维护一个点子树里面的所有点和 $l,r$ 的交集。

其实这道题的可持久化线段树本质上是线段树合并，只是为了防止空间爆炸，用了可持久化线段树。然后左/右节点是否为空表示是否有值。

写法上注意，一棵树是 dfs 序上的，一棵不是。

P1393 Mivik 的标题

P1393 Mivik 的标题。

这道题容易想到 dp。设 $f_i$ 表示 $i$ 向前 $i-|S|$ 到 $i$ 是 $s$ 第一次出现的位置，那么答案就是：

需要求出来 $f$。我们考虑容斥，荣 $m^{i-|s|}$ 减去不合法的方案，有以下两种：

• 在 $[1,i-|s|]$ 种已经出现了 $s$。

• $s$ 的前缀与之连成 $s$。

第一种情况就可以用之前的 $f$ 消掉就行了，也就是减去 $f_jm^{i-|s|-j}$（重叠情况可能会被多减）。

第二种的转移我们需要利用 KMP 求出 Border 进行转移，也就是减去 $\sum_j f_{i-|s|-j}$，但是是 $O(n^2)$ 的，需要用 Border Theory 优化。

所有 border 长度构成的序列，可以划分为 $O(\log k)$ 个等差数列。

写代码一定需要注意 $l$ 和 $r$ 哪个大哪个小。。。

20260619

P5369 [PKUSC2018] 最大前缀和

P5369 [PKUSC2018] 最大前缀和。

一个前缀如果被选，那么他的后缀一定没有 $<0$ 的，他后面的一定没有 $>=0$ 的。这个是充要条件。

我们考虑 dp。

设 $f_s$ 表示选 $s$ 这个集合，并且满足所有前缀 $<0$ 的方案数。

设 $g_s$ 表示选 $s$ 这个集合，并且满足所有后缀 $>=0$ 的方案数。

枚举第一个元素 $i$（可以为负数），最后的答案就是：

$S$ 表示这个集合所有元素的和。

AT_arc106_e [ARC106E] Medals

AT_arc106_e [ARC106E] Medals。

二分图匹配。二分答案，然后 Hall 定理进行快速判定。

我们需要判定 $mid$ 天内是否可以，我们对于每一个点集判断连向天的边数。

$p_i$ 是第 $i$ 天出勤员工的二进制 $mask$。$f_s$ 表示当天来的人全部都在 $i$ 里面的日子天数。然后答案就是 $mid-i$。

CF1083E The Fair Nut and Rectangles

CF1083E The Fair Nut and Rectangles。

$n^2$ 左右的做法容易想到，枚举 $x$ 和 $y$ 的最大值属于谁，然后计算所有 $\le x,\le y$ 的。

尝试按照 $x$ 从小到大排序。我们发现被包含的区间一定用不上，所以可以发现 $y$ 是从大到小的。

于是 $f_i$ 表示到了 $i$。

可以进行斜率优化。

注意：

#define X(t) (a[t].x)
#define Y(t) (f[t])

不能写成 X(x) 不然会出神秘错误。

AT_agc030_f [AGC030F] Permutation and Minimum

AT_agc030_f [AGC030F] Permutation and Minimum。

看到 feecle 的题解了。套路：寻找充要条件。

我们发现这道题的充要条件形如：

• 填的一个数大于 $x$。

• 填的一个数等于 $x$。

于是可以想到，从大到小排序，进行处理。

可以 dp，设 $f_{i,j,k}$ 表示到了 $i$，还剩 $j$ 个 A 的空位，还剩 $k$ 个 B 的空位。最后的答案是 $f_{0,0,0}$。

目前有一些缺 $1$ 的空位组和缺 $2$ 的。

可列方程：

解得：$p = j - k$，$q = 2k - j$。

转移过程中我们还需要知道还有多少个大于 $i$ 的数没有填。

• 所在对的两个数都已知：$f_{i-1,j,k}=f_{i,j,k}$。

• 所在对还有一个未知数：

  • 让其成为 $b$ 值，$f(i,j,k)\to f(i-1,j-1,k-1)$。
  • 不让其成为 $b$ 值，$f(i,j,k)\to f(i-1,j,k)$。

• 本身就是 $-1$：

  • 不是 $b$，$f(i,j,k)\to f(i-1,j,k)$。
  • 是 $b$ 且放入缺 $2$ 的空位，$pf(i,j,k)\to f(i-1,j-2,k-1)$。
  • 放入还有 $1$ 个数的空位，$\max(q-S,0)f(i,j,k)\to f(i-1,j-1,k-1)$。

这其中 $S$ 是比 $i$ 小的缺 $1$ 的数对，我们不能让他们作为 $i$ 这里的 $B$。

总结一下，我感觉这道题给的启示是 dp 从状态就可以得到很多信息，因此就可以更好地处理。

CF1988F Heartbeat

CF1988F Heartbeat。

对于排列计数，有两种方法，从位置考虑，从值域考虑。

我们考虑值域。

这种一看就觉得是 dp。设 $f_{i,j,k}$ 表示插入了 $i$ 个数，有 $j$ 个前缀最大值，$k$ 个上升点的方案数。

貌似这个不好转移，所以我们考虑插入数，从 $n$ 到 $1$ 插入，转移方程：

• 插到最后面：$f_{i,j,k}\gets f_{i-1,j,k}$。
• 插到最前面：$f_{i,j,k}\gets f_{i-1,j-1,k-1}$。
• 插到上升点前面：$f_{i,j,k}\gets k\times f_{i-1,j,k}$。
• 插到下降点前面：$f_{i,j,k}\gets (i-k-1)\times f_{i-1,j,k-1}$。

整理一下：

然后这道题还有后缀，所以我们对后缀再 dp 一次得出 $g$：

计算答案的时候我们需要把排列按照 $m$ 把前缀最大值和后缀最大值拆分开，让他们不互相影响，最后的答案就是：

$O(n^4)$ 需要优化。

我们发现左边只和 $i$ 有关，右边只和 $j$ 有关，所以我们可以定义 $s$ 和 $t$：

$s_{len,x} = \sum_{i=0}^{len} f_{len,i,x} \cdot a_{i+1}$

$t_{len,y} = \sum_{j=0}^{len} g_{len,j,y} \cdot b_{j+1}$

继续优化：

最后的答案：

20260622

CF1905D Cyclic MEX

CF1905D Cyclic MEX。

我们需要一个 $O(n)$ 的算法，于是想到一直向左循环移位然后算当前贡献。

此时，第一个数会被放到最后，那么所有 $mex$ 大于它的都会变成它。由于 $mex$ 单调不降，用单调队列维护。

CF1326E Bombs

CF1326E Bombs。

我们考虑答案是否可以为 $x$，对于 $x$ 需要保证存在一个下标 $i$ 使得 $i$ 后面 $\ge x$ 的数要比炸弹数多。

所以如果一个 $x$ 不合法，那么对于所有的 $i$，$\ge x$ 的数的个数 $\le$ 炸弹数。

所以由于答案单调，所以我们维护 $x$，如果不合法就减一。考虑用线段树维护，$\ge x$ 的数的个数与炸弹数的差的最大值，如果 $\ge 0$ 就合法。

CF1777F Comfortably Numb

CF1777F Comfortably Numb。

别把 $\max$ 看成 $mex$ 了。

子区间最大值问题可以考虑分治。

我们需要求出来每一个最大值的管辖区间，然后这个区间中目标是求： $\max_{\substack{j\in[l_i,i] \\ k\in[i,r_i]}} \big(a_i \oplus s_{j-1} \oplus s_k\big)$

要支持查询区间 $[L,R]$ 内的数与 $x$ 的最大异或，需要用可持久化 Trie，也就是这个 Trie 包含一个前缀的所有数。其实每次暴力塞也行，就定根就行了。

CF1444C Team-Building

CF1444C Team-Building。

判断二分图的充要条件是没有奇环，可以用扩展域并查集判断。

先排除本身就不是二分图的，然后假设还剩 $cnt$ 个，用为 $\binom{cnt}{2}$ 减去不合法的。因为不合法的情况数是 $O(m)$ 的，最多只有 $m$ 调跨块的边。

if(ct[c[u]])continue;，if(x==y)continue; 这种特判不要漏掉。

CF997E Good Subsegments

CF997E Good Subsegments。

题目要求的是：$(\max-\min)-(r-l)=0$。

询问区间子序列的信息，可以离线移动右指针。我们尝试在当前指针 $r$ 维护 $(max−min)−(r−l)$ 的最小值和最小值个数。

然后线段树还需要维护每一个 $l$ 开头的到当前的 $i$ 中的好的子区间个数。

20260623

CF372C Watching Fireworks is Fun

CF372C Watching Fireworks is Fun。

$f_{i,j}$ 表示第 $i$ 次发射时人在第 $j$ 个区间。

$f_{i,j}=\min(f_{i-1,k})+b_i - \vert a_i - j\vert,k\in[\max(1,j-t\times d),\min(n,j+t\times d)]$

这个需要优化。先把 $b_i$ 给提出来。

可以观察到每一个 $f(j)$ 的折线多都是单谷函数，所以想到了 slope trick。

还有一种方法就是正着和倒着都进行一遍单调队列优化 dp，就是合法区间，然后区间中维护最小值。

CF1093G Multidimensional Queries

CF1093G Multidimensional Queries。

带有绝对值的题目第一眼看着一定是拆绝对值。用 $\max$ 可以拆，我们用二进制拆分，表示每一个点拆分过后每一位的符号变化，然后只需要对于对应的数进行 $\max f_0+f_{31},f_1+f_{30}$ 这种形式的了。

CF1422F Boring Queries

CF1422F Boring Queries。

把 LCM 转换成 GCD，LCA 是乘积之和再除以两两数之间的最大公约数。

然后我们发现可以用线段树，对于每一个 $r$ 维护前面的信息。

这里我们要用到主席树，对于每一个 $r$ 维护前面的所有质因子的次幂，只有最后一次出现需要记录贡献，其余都要乘上逆元抵消掉原有的。

CF940F Machine Learning

CF940F Machine Learning。

带修莫队。

CF321E Ciel and Gondolas

CF321E Ciel and Gondolas。

决策单调性。

20260625

CF240F TorCoder

CF240F TorCoder。

对于每一个字母开一颗线段树，然后按照顺序处理。

所以对于同一个字母位置关系不重要的可以每一个字母开一个线段树维护。

CF813E Army Creation

CF813E Army Creation。

关键点：寻找不变量 $k$，然后问题转化。

相当于求：

我们发现答案就是区间长度减去大于 $k$ 的那一部分，所以每一个数需要处理出前面第 $k$ 个相同的数。答案就相当于询问有多少个 $pre_i \le l$。

这个就是主席树了，跟区间和权值有关的问题可以直接转化成主席树与差分。

分块也可以做，需要一个数组 $num_{i,j}$ 表示块 $i$ 到 $j$ 的答案。

CF1080F Katya and Segments Sets

CF1080F Katya and Segments Sets。

有两个维度，考虑主席树。

我们考虑维护每一个集合对于所有 $l\ge x$ 的线段中，$r$ 的最小值。

线段维度就相当于版本，也就是问题转化成了静态查询，查询这个集合区间内是否符合。因为集合不能作为版本，不可差分。

所以我们按照 $l$ 从大到小排序，二分找到第一个 $l\ge x$ 的版本，然后找到这个版本中 $[a,b]$ 的最大值。

CF1446D2 Frequency Problem (Hard Version)

CF1446D2 Frequency Problem (Hard Version)。

性质：这个子串的众数（设为 $X$）一定包含整个序列的众数。反证法，如果不包含，可以通过一直扩展的方式，得到更好的答案。

和数字值，个数的东西有关的可以想想根号分治。

这种不好处理的东西尝试一下根号分治。我们分治出现次数大于 $\sqrt n$ 和小于 $\sqrt n$ 的。

大于的，种类数 $\le \sqrt n$，可以枚举种类数。我们使用计数器 $cnt$，遇到 $X$ 就 $+1$，遇到 $Y$ 就 $-1$。我们需要找到最长的一段使得开头结尾 $cnt$ 都相同。

小于的，枚举最大出现的次数，双指针保证出现次数 $\le k$。

CF258D Little Elephant and Broken Sorting

CF258D Little Elephant and Broken Sorting。

$f_{i,j}$ 表示 $i$ 位置上大于 $j$ 的概率（$a_i>a_j$）。

交换 $a$ 和 $b$ 就是：

20260626

CF1000F One Occurrence

CF1000F One Occurrence。

莫队做法太显然了，想想别的做法。

线段树做法可以想到，我们需要让一个数值在区间最右边的数的前驱小于 $l$。

CF965E Short Code

CF965E Short Code。

直接贪心（暴力）是错的，所以最深的点需要优先选。

用优先队列维护。

比如有左边两条链，一边长，如果祖先被短的用掉了就不好了。

CF375D Tree and Queries

CF375D Tree and Queries。

子树问题考虑树上启发式合并。

每次合并到一个点可以直接获取到他每个颜色的个数的数组，也不难。

保证不少于的方法就是数加进去只会让新的个数的计数 $+1$，原来的不减去。

注意 dfs 序的 $id$。

CF1580B Mathematics Curriculum

CF1580B Mathematics Curriculum。

***题，$n=100$ 标算 $O(n^3)$。

计数题目先想 dp，排列的问题可以拆分序列。

感觉第一步是发现性质，好数需要怎么判断。我们发现就是就是左右两边的前缀最大值个数相加再 $+1$，所以我们可能需要拆分。然后我们发现最大值刚好可以拆分左右两边互不影响。

这种题显然 dp，尝试设 $f_{i,j,k}$ 表示长度为 $i$，有 $j$ 个最大值恰好有 $k$ 种取值的 $k-好数$。

考虑转移，我们可以拆分序列，枚举最大值的位置：

要加上 if(L&&R)add(now,L*R%P*C[i-1][p-1]%P); 不加 if(L&&R) 就 TLE 慢几十倍？

CF2111G Divisible Subarrays

CF2111G Divisible Subarrays。

最值问题可以枚举最值，然后计算区间。问题转化可以通过类似“一个数左边/右边第一个大于/小于这个数的数”这种形式的来表达。

感觉真的不好想。我们设最大值为 $i$：

• $x$ 为左边第一个大于 $a_i$ 的位置。
• $y$ 为右边第一个大于 $a_i$ 的位置。
• $z$ 为 $y$ 右边第一个小于 $a_i$ 的位置。

分类讨论，第一种的话，合法的区间需要保证：$x<l\le i,y\le r<z$。

然后这个可以转化成举行覆盖问题：

所以我们问题转化成了矩形加，单点查询。

尝试扫描线，按照 $l$ 排序，然后扫到 $l=x+1$ 的时候在 $[y,z-1]$ 加 $1$，然后扫到 $i+1$ 的时候恢复。

但是这是一道在线的题目，所以我们就需要提前用主席树把所有的状态保存下来，可持久化一下，就可以了。

单点查询所以 tag 可以直接保留不用下传，询问下去的时候统计所有父亲 tag 的和。

CF1656F Parametric MST

CF1656F Parametric MST。

注意，可能有负数。

先考虑对于每一个 $t$ 求出值。

让每一个点和与其连边最大的边相连。我们只需要对于 $a_u+t\ge 0$ 的，连接最小的 $a_v+t$，否则连接最大的。

然后判断 $+\infty$ 的时候的值就可以判掉无穷的情况了。

最后的答案一定是一个 $a_i$，因为可以证明树的形态不变，然后这个 $f(t)$ 是在每两个取值之间都是一次函数。

20260629

CF1477A Nezzar and Board

CF1477A Nezzar and Board。

首先我们先看看 $2x-y$ 是什么东西，我们化一下即可发现 $x+(x-y)$，也就是这个数可以一直延伸成一个等差数列。

然后考虑怎么处理。我们先排序，然后差值就全部可以表示出来了，设集合为 $a$。我们最后只需要解出这样的方程：$x+\sum_{i=2}^n v_ia_i=k$。然后用裴蜀定理，有解的充要条件是 $\gcd a_i|(k-x)$。

CF547C Mike and Foam

CF547C Mike and Foam。

这道题我们需要求出对于每一个数和它互质的数。用总数减去不互质的数即可，不互质的数可以用容斥来做，一个数的不同质因子数是有限的。

CF839D Winter is here

CF839D Winter is here。

这就是一个套路了，枚举 $\gcd$，然后 $g_i$ 是为 $i$ 的倍数的贡献，$f_i$ 是为 $i$ 的贡献。

首先肯定是枚举 $\gcd$。

设 $g_i$ 表示 $\gcd$ 是 $i$ 的倍数的数的长度和。设 $s_i$ 表示 $i$ 的倍数出现次数，$g_i=s_i*2^{s_i-1}$（每一个数倍 $2^{n-1}$ 个集合选中）。

然后答案容斥一下即可。

CF338D GCD Table

CF338D GCD Table。

首先行是不变的，所以 $x|lcm(a_j,\cdots,a_{j+l-1})$。

然后需要保证的：

然后还需要验证，因为没有充分性，这样只能求出 $a_i|\gcd(x,y+i-1)$，需要保证等于。

CF1146E Hot is Cold

CF1146E Hot is Cold。

和位置关系不大的题目考虑值域。

我们考虑值域线段树，维护每一个值。然后同一个值最后翻转的情况一定相同，所以直接打区间 tag 就行了。

然后比如 > x 这个询问，我们分类讨论正负数的情况。我们发现一些部分可以强制变成正数/负数（因为对应的相反区间不变），所以需要区间翻转和区间赋值操作。

需要注意翻转的 tag 和 赋值的 tag，赋值之后翻转的 tag 清零，但是 pushdown 之后两个都需要操作的。

CF891E Lust

CF891E Lust。

容易发现，答案的增加量就是 $a_i$ 乘积的减少量。所以答案就是最初的乘积减去最后的乘积。

我们设每一个数选中的次数为 $b_i$，则 $\sum_i b_i = k$。

然后排列的数量有 $\dfrac{k!}{\prod_{i=1}^nb_i!}$。

最后的期望：

所以对于一组 $b$：

尝试把后面的东西用指数生成函数计算。

需要求出第 $k$ 项。

右边的显然可以预处理出来，设为 $\sum c_ix_i$。

然后就变成了：

CF449D Jzzhu and Numbers

CF449D Jzzhu and Numbers。

还是很套路的，设 $g_s$ 表示与起来包含 $s$ 的情况数，然后就可以求出 $f$ 来。

CF559C Gerald and Giant Chess

CF559C Gerald and Giant Chess。

我们发现黑格子很少，能不能计算总路径减去包含黑格子的然后容斥什么的。

总路径数是 $C_{h+w-2}^{w-1}$。

我们还需要计算黑色点的贡献，主要问题就是一条路径会有多个黑点。先设 $f_i$ 表示第 $i$ 个点是路径第一个黑点的时候的贡献。

CF1557D Ezzat and Grid

CF1557D Ezzat and Grid。

首先容易想到 dp：

可以用线段树，维护每一个位置上 $f$ 值最大的值就行了。需要离散化。

CF1091H New Year and the Tricolore Recreation

CF1091H New Year and the Tricolore Recreation。

这道题我们发现两个人移动棋子是等价的，都是从两个间隔中选一端进行移动，所以可以想到 SG 函数。

$sg_0=0$，$sg_i=mex\{sg_{i-k}\}$。

最后把所有 sg 异或起来即可。

只是 sg 函数不好求，会 TLE，所以我们尝试优化，可以使用 bitset 进行优化。

$f_v$ 是一个 bitset，它的第 $x$ 位为 $1$，当且仅当 状态 $x$ 能一步到达某个 SG 值为 $v$ 的状态。

我们的优化方法就是对于一个 sg 值维护拥有 TA 的下标。

CF1065E Side Transmutations

CF1065E Side Transmutations。

先转化一下题目的意思，就是 $b$ 限制了连续一段的翻转情况需要相同。

对于中间的那些随便选了，能够对应上的一些段的答案就是（拆分左右两边相同/不同的答案）：

最后的答案就是：

CF1106F Lunar New Year and a Recursive Sequence

CF1106F Lunar New Year and a Recursive Sequence。

神秘的降幂方式：用原根！

我们发现 $998244353$ 的原根是 $3$，原来的递推式就变成了：

这个我们发现可以用矩阵快速幂解决：

然后我们得到关系 $g_n=u*g_v$（$g$ 前 $k-1$ 项都是 $0$），于是：$f_k^u=m \pmod p$ 可以用 BSGS 解决。

CF960G Bandit Blues

CF960G Bandit Blues。

相当于给定前缀最大值的个数和后缀最大值的个数，问序列种数。

需要第一类斯特林数，不会算。

20260702

CF1182E Product Oriented Recurrence

CF1182E Product Oriented Recurrence。

这道题算出这几项是几次幂就行了，拆分开算。

CF1514D Cut and Stick

CF1514D Cut and Stick。

相当于就是找到区间出现次数最多的数。单独的众数单独成一段。

然后莫队可以直接做，就是维护区间众数个数。del 的时候直接判断当前数字有没有别的数，没有就把答案减一。

注意初始的时候有 $n$ 个 $0$ 需要赋值。

CF1548C The Three Little Pigs

CF1548C The Three Little Pigs。

$\sum_{i=1}^n\dbinom{3i}{x}$

$3i<x$ 时 $\binom{3i}{x}=0$。

可以想想杨辉三角的结论，$\binom{3i}{x}$ 是 $(1+x)^{3i}$ 的 $x$ 次项系数，所以：

等比数列求和：

直接进行大除法，就行了。

还有一种方法：

设 $f_{x,j}=\sum_{i=0}^n \binom{3i+j}{x}$，答案就是 $f_{x,0}$

$f_{x,0}+f_{x,1}+f_{x,2}=\sum_{i=0}^{3n+2} \binom{i}{x}=\binom{3n+3}{x+1}$

$\binom{n}{m}=\binom{n}{m-1}+\binom{n-1}{m-1}$，$f_{x,1}=f_{x-1,1}+f_{x-1,0},f_{x,2}=f_{x-1,2}+f_{x-1,1}$

然后就可以求出来了。

CF1780F Three Chairs

CF1780F Three Chairs。

直接莫反，注意里面的式子是 $i$ 还是 $a_i$。

CF603C Lieges of Legendre

CF603C Lieges of Legendre。

公平组合游戏一般先尝试一下 sg 函数。

我们发现有多个堆，只需要把每一个的异或起来就行了。

偶数的情况：

然后我们发现 $k$ 个异或跟奇偶性有关。

奇数的情况：

先列出 sg 值，比如 $k$ 为奇数：

0 1 0 1 2 0 2 0 1 0 1

偶数：

0 1 2 0 1 0 1 0 1 0 1

整理一下：

$x$ 为奇数：$sg_x=mex\{sg_{x-1}\}=0$。$x\ge 3$。

$x$ 为偶数，若 $k$ 为偶数：$sg_x=mex\{sg_{x-1},0\}=1$。

$x$为偶数，$k$ 为奇数，$sg_x=mex\{SG(x-1),SG\left(\frac{x}{2}\right)\}=mex\{0,SG\left(\frac{x}{2}\right)\}$，递归处理。

P4199 万径人踪灭

P4199 万径人踪灭。

容易想到容斥，满足 $1$ 不满足 $2$ 的就是马拉车了，可以求出以一个点为中点的连续的回文子串的个数。

所以我们还需要算出来满足 $1$ 的总方案数。我们发现这个只需要算出来对于每一个位置 $i$ 位置和值都对称的数的个数 $c_i$ 即可，最后答案是 $2^{c_i}-1$。

突破口：只有两种字符。对于每一个字符，将自己和自己做卷积（FFT），$cnt_k$ 表示有多少个 $i+j=k$ 的相同的对子，除以二就行了。

也就是自己和自己卷积可以获取下标的和为一个值的时候的数量，真的很强。

CF755G PolandBall and Many Other Balls

CF755G PolandBall and Many Other Balls。

设选了 $i$ 个双球组，有 $k-i$ 个单球组。

• 先把 $i$ 个双球组放进 $n$ 个位置中，方案数：$\binom{n-i}{i}$。

• 然后从这 $i$ 个双球组和 $k-i$ 个单球组中，选出最终的 $k$ 个组：$\binom{k}{i}$。

所以：

这个公式对吗？不对，因为双球组的位置限制会导致重叠，所以需要容斥。

• $\binom{k}{i}$：从 $k$ 个组中钦定 $i$ 个位置发生“重叠”
• $\binom{n-i}{k-i}$：从剩下 $n-i$ 个位置中选 $k-i$ 个组
• $2^{k-i}$：每个组可以是单球或双球

展开组合数：

引入下降幂：

代入：

尝试卷积，令：

则：

可以用卷积。

20260703

CF1610D Not Quite Lee

CF1610D Not Quite Lee。

首先，我们肯定希望找出好的定义。但是我们发现这个东西没有办法直接找，比如：好像不是，比如 $1 2$：$-1 -2$ 和 $3$ 也可以凑出来。