日记

如何呢？

Genetic engineering# Link to

首先我们就想了 dp。设 $dp_{pos,rt}$ 表示已经填了 $pos$ 个数，当前在 AC 自动机的 $rt$ 点上。转移十分的显然。但是我们发现，无论怎么调都过不了样例，就连手模也过不了。显然是这玩意是错的。

看了题解，我们重新来过。我们对于 AC 自动机上的每个节点记录一个新的值 $val_{rt}$ 表示在 $rt$ 结尾的字符串长度是多少。设 $dp_{i,j,k}$ 表示已经填了 $i$ 个，还剩 $j$ 个没有被覆盖，现在在 $k$ 节点。那么转移的时候，我们从 $rt$ 转移到 $\delta(k,dig)$，如果 $val_{\delta(k,dig)} > j$，那么就可以转移到 $dp_{i + 1,0,\delta(k,dig)}$，反之只能转移到 $dp_{i + 1,j + 1,\delta(k,dig)}$。

类似之前做的题，一个点的 $val$ 一定要对于这个点的所有祖先取 $\max$，在 bfs 的时候处理即可。

Legen…# Link to

显然的状态 + 显然的转移 + 不会推的矩阵优化。

Baggage Claim# Link to

考虑对于两个点，如果位于同一行或者同一列，那么就只能在中间有一个点，反之就有两种情况。对于每两个相邻的点之间，他们对于他们俩的两个可能的中继点建边。

这么建边的意义是：每条变都会对应一个点，且每个点不能被两条边对应。考虑对于每个联通分量的三种形态：

• 树
  由于只有 $siz - 1$ 条边，所以一定会有一个点空出来，方案数就是 $n$。
• 基环树
  我们发现，环上面的树的方法有且仅有一种，那么我们就只用考虑环的方案数了。我们经过简单的手模发现，如果环长大于等于 $2$，那么就有 $2$ 种方案。反之只有一种。
• 其他的乱七八糟的环套环
  这是非法的，$ans$ 直接赋值成 $0$。

最后把所有的乘起来就是了。

后日谈 # Link to 后日谈

期待明天的考试。

期待不了 CCPC