ATCF杂题选做
看见好多人都在写这个啊。每天挑点题写一写吧。
不过可能不止 ATCF。打星号的是没做出来的。
*ARC096E Everything on It
2023.01.04
推了半天一个东西，才发现那个叫第二类斯特林数。
条件不好处理。考虑容斥。
令我们钦定选 $i$ 个不超过 $1$ 的方案数为 $g_i$，恰好选 $i$ 个不超过 $1$ 的方案数。根据二项式反演，有 $f_0=\sum (-1)^j g_j\dbinom{j}{0}=\sum (-1)^j g_j$。
考虑计算 $g_i$。首先其他集合的方案数为 $2^{2^{n-i}}$。选 $t$ 个恰好为 $1$，分成 $j$ 个互不相交的集合的方案数为 $\sum \begin{Bmatrix}t\ j\end{Bmatrix}\dbinom{i}{t}=\begin{Bmatrix}i+1\ j+1\end{Bmatrix}$。等式可以理解为添加一个数 $0$，和 $0$ 在一起的当作不选的。最后因为已经保证集合不同，所以直接乘上 $(2^{n-i})^j$ 来算这 $j$ 个集合。
复杂度 $O(n^2)$。
CF526E Transmitting Levels (2400)
2023.01.04
很有趣的题目啊。没想到什么高妙的做法，想到一个乱搞分析一下发现是正确的。
预处理出每个点跳 $k$ 最远到 $nex_i$。$nex_i$ 一定是不降的。考虑一个块 $[i,nex_i]$，如果有前面的点跳进来，不可能有 $j<i\le nex_i<nex_j$ 的情况。所以我们找任意一个块的每个点作为起点即可考虑到所有情况。
然后我们想找块长最小的那个感觉跑的快一点，假设块长为 $k$，因为它是最小的，所以每次至少跳 $k$，跳的次数是 $O(\dfrac{n}{k})$，而我们枚举 $k$ 次，复杂度就是 $O(n)$ 的了。
*CF319E Ping-Pong（3000）
2024.01.07
观察到只有两种边，有交但不包含则无向边，包含则有向边。然后继续发现如果 $a\to b$ 可达，则最多只会经过一条有向边 $a\to x$。
无向边的连通性考虑用并查集。并查集的维护用线段树，每个线段树上维护一个栈。每次最多只会加入两个点所以复杂度是对的。因为区间长度是递增的，所以从一个端点找过去不会有包含的情况。
判断的时候，两个点在一个联通块肯定有解，否则看 $y$ 的联通块的最远左端点 $L$ 和 $R$ 是否包含 $x$，包含也存在解。否则无解。
复杂度 $O(n\log n)$，还有乘上并查集的复杂度。
CF1916D Mathematical Problem (1700)
2024.01.08
本来以为是高妙题。发现只有 1700。
打标发现增量构造 $169,196,961$，即可。具体就是后面加两个 $0$，然后再加两个 $100\dots 600\dots9$，$900\dots 600\dots1$。
CF1919E Counting Prefixes（2600）
2024.01.10
狗哥推荐题。
把合法序列画成折线图，把前缀和从小到大看，前缀和 $\le i$ 的分成很多段，而 $i+1$ 要么新建一个段，要么扩展一个段，要么合并两个段。这三种情况，考虑维护段的个数的插入 dp。然后还要记录一下末尾是否确定，判一下开头是否为 $0$ 的情况。
复杂度 $O(n^2)$。看题解还能 BEST 定理？感觉很牛啊。
CF1483F Exam（3400）
2024.01.11
没想到还能自己做出来 3400。
下面默认 $n$ 和 $\sum|S|$ 同阶。
首先对于一个串 $i$，对于串的每个右端点匹配的最长的串是可能的合法二元组。所以答案个数是 $O(\sum|S|)$ 级别的。每个右端点匹配最长的可以用 AC自动机 $O(n)$ 求出来。
再用单调栈去掉包含关系的区间。但现在的条件是充分不必要的，考虑一种情况：abcab cab ab，这样子可能会输出 $2$。原因在于一个串可能出现多次。换句话说如果在 fail 树上一个节点子树内有节点被选那么它就不可能选。而子树内存在不可选的它更不可能选。用树状数组维护子树内是否存在被标记过即可。可能还要对 dfs 序从大到小排个序。
复杂度 $O(n\log n)$。
这题的关键在于必要不充分条件一步步限制到充要条件。
*CF468C Hack it!（2500）
2024.01.11
构造题真不是人做的。
观察到当 $x\le 10^{18}$ 时，$f(x+10^{18})=f(x)+1$。
我们想每次增加 $1$，于是构造 $p=\sum\limits _{i=0}^{r=10^{18}-1} f(i)$。这样每次左右端点同时右移就加 $1$。把 $p$ 算出来 $p=81\times 10^{18}$ 即可。
构造题，找不到方法总结了。
CF1149C Tree Generator™（2700）
2024.01.11
经典套路把左括号看成 $1$，右括号看成 $-1$。这样每个点的深度就是前缀和。
这个括号序列还相当于欧拉序，欧拉序中 $a,b$ 的 $lca$ 是 $[a,b]$ 区间中深度最小的那个点。这样直径的 $d_{max}=\max dep_a+dep_b-2\min_{i=a}^b dep_i $。线段树维护最大值，最小值，$\max dep_a-2\min_{i\ge a} dep_i$，以及对应的 $b$，和答案。由于我们要求的是最大值，转移的时候很多不合法的状态都不会统计到答案中。
修改相当于区间加减，再维护个懒标记即可。时间复杂度 $O(m\log n)$。
AT 2016 Final Road of the King
2024.01.11
先讲讲我的比较愚蠢的做法。
钦定每次遍历到没走过的点的顺序 $1\to 2\to 3\to \dots\to n$，最后乘上 $(n-1)!$ 即可。
记 $f_{i,j}$ 表示当前扩展到前 $i$ 个点，连了 $j$ 条额外边，且前 $i$ 个点都和 $1$ 在一个强联通分量的方案数。枚举跳到 $1$ 的强联通分量中的终点 $l$ 和边数 $t$，然后 $[l+1,i-1]$ 之间随便连 $t-k$ 条边，有转移：
$$
f_{i,j}=\sum {l=1}^{i-1}\sum {t=1}^{j}\sum {k=1}^{t} f{l,j-t}\times h{i-l-1,t-k}
\times (i^k-(i-l)^k)
$$
其中 $h{i,j}$ 表示 $i$ 个点连 $j$ 条额外边的方案数。
发现后面那里都和 $j$ 没关系，于是可以对于每个 $i,l,k$ 预处理出来后面的东西。
复杂度 $O(n^4)$，但是带 $1/32$ 的常数所以可以过。其实可以卷积做到更低的复杂度，但没什么意思。
其他题解的做法就是基于分成三类，包含 $1$ 的强联通分量，走过但不在 $1$ 的强联通分量之中，没走过的个数。然后如果当前的点走到 $1$ 的强联通分量中就所有点都在 $1$ 的强联通分量之中。复杂度就是 $O(n^3)$ 的了。
标签：计数
*CF1768F Wonderful Jump（2900）
2024.01.11
知道结论了还不会，好菜。还是没有想到根号分治。
首先考虑放到笛卡尔树上，观察到如果 $j\to i$ 转移但是中间 $\exists k\in (i,j),a_k\le \min(a_i,a_j)$，则 $j\to i$ 一定不如 $j\to k\to i$ 优。所以一个点只会从左子树和祖先转移过来，向右子树和祖先转移过去。
再观察到值域 $a_i\le n$，记 $[j,i]$ 的最小值为 $x$，如果转移点 $x(j-i)^2\ge n(j-i)$ 那么一定不会转移。有 $j-i\le \dfrac{n}{x}$。
然后考虑根号分治并结合第一个性质。对于 $x\ge B$ 的直接暴力转移。而对于 $x<B$ 的，因为第一个性质，所以每个相同的 $x$ 的转移区间不交，分析一下是均摊 $O(n\sqrt n)$ 的。
实现上不需要写单调栈，直接往前转移和往后刷表即可。复杂度 $O(n\sqrt n)$。常数很小。
标签：优化转移，根号分治
CF1870E Another MEX Problem（2300）
记 $f_{i,j}$ 表示前 $i$ 个数 $j$ 是否能被异或出来。
题解有 mex 相同且不被包含的个数只有 $O(n)$ 个的结论。这样可以直接暴力转移了。
但是我不会，怎么办呢？观察到对于 $f_{i,j}=1$，则对于 $\forall k\ge i,f_{k,j}=1$，所以设 $g_j$ 表示异或出来 $j$ 的最小右端点。
然后预处理出 $h_{i,j}$ 表示 $i$ 为左端点 mex 为 $j$ 的最小右端点。然后做个 $O(n^2)$ 的 dj 最短路转移即可。
标签：优化转移，最短路