chaosiwode'erduole
赛场设计
我们对图传递闭包一下，然后取补图得到 \(G'\)。
\(G'\) 必须不存在三元环。且 \(G'\) 中对于每个点对 \((u,v)\)，他们之间的边至少存在一条。
那么 \(G'\) 中如果存在一个点数大于 2 的环，那么一定会存在三元环。
我们发现，传递闭包这个映射不是双射。那我们从这个 \(G'\) 求一下补图。对于原图，相邻的强连通分量后面那个必须往前面一个连边。于是剩下的边可以随便连。容易 dp。
Text Editor
end不需要，home至多做一次。
那么 \(s\) 可以分为三段/两段，做 dp 即可。
Zeros and Ones
Thue-Morse 序列有通项：\(a_i=\operatorname{popcount}(i)\bmod 2\)。
题目即问对于 \(i=0\sim m-1\)，有多少个 \(\operatorname{pop}(i)\) 奇偶性与 \(\operatorname{pop}(i+n)\) 相同。
继续转化：\(\operatorname{pop}(i\oplus (i+n))\bmod 2\)。
考虑数位 dp 即可。从低到高 dp。
Omkar and Last Floor
因为 1 应该集中地放，所以我们对列做区间 dp。
\(f_{l,r}\) 考虑所有被 \(l,r\) 完全包含的段，每次枚举一列 \(k\)，穿过 \(k\) 的段的 1 全部放到这列，然后显然可以递归子问题。复杂度 \(O(n^3)\)。
Mex Tree
好家伙讲过了：详见 CF1830D
Partial Virtual Trees
看的出来大家很喜欢这题。tj
Jellyfish and Hack
考虑一个 dp，\(f_{i,x}\) 表示长度为 \(i\) 的排列，其 \(fun(P)=x\) 的方案数。
转移：\(f_{i,x}=\sum_{a=0}^{i}\sum_{y=0}^{x} f_{a,y}f_{i-a-1,x-y-i}\binom{i-1}{a}\)。
注意到这个东西 \(x\) 最多是 \(O(n^2)\) 的，那么复杂度为 \(O(n^5)\)。
容易发现是个卷积的形式，考虑转点积然后拉差回来，复杂度 \(O(n^4)\)。
[THUPC 2025 决赛] I'm Here
对于所有的 \(i=1\sim n\) 求出好排列的个数，其中好的排列满足：
- 对于 \(u,v\in P\) 且 \(u\) 是 \(v\) 的祖先，满足 \(v\) 在 \(u\) 之前。
- 若 \(u\) 点被选中，则其在排列中的位置必须在 \(n-u+1\) 以前。
第二个限制可以考虑后缀最大值的限制，那么我们从大到小插入数进行 dp，数只有在插在末尾时才可能是后缀最大值。
设 \(f_{i,j,k}\) 表示填了 \(\ge i\) 的数，\(P\) 的长度为 \(j\)，强制当前序列最后一个数填在 \(k\) 位置的方案数。
转移可以分类讨论：
- \(i\) 不选，直接从 \(i+1\) 继承。
- \(i\) 选，且放在最后成为最大值，一定满足限制 1。那么枚举 \(i\) 的位置即可。
- \(i\) 选，且不放在最后，那么枚举一下 \(i\) 子树内和 \(i\) 一共放了多少个数，他们必须放在 \(k\) 之前，从 \(i+siz_i\) 转移过来。