NOIP 模拟赛 7

T1

有个字符串 $S$，你可以删除其的任意子串，询问会得到多少本质不同字符串。
要求线性，字符集小。

考虑容斥，转化成会数重复多少次，注意到每加入一个字符，它并不会影响到前面的点造成的贡献，于是我们只需要统计以 $i$ 开头的后缀匹配前缀会算重多少，注意到我们只需要统计前面出现过多少次 $S_i$ 即可。因为我们只需要考虑 $i$ 什么时后不必须，显然就是有一个位置 $p$，满足 $S_p=S_i$，那么删除 $[p,i-1]$ 和 $[p+1,i]$ 效果等同。

T2

给定一个简单无向图（无自环重边），求 $s$ 到 $t$ 的不连续经过同一条边，经过边数为 $k$ 的方案数有多少。
多组询问，询问次数 $q\le 100$，点数 $n\le 200$，边数 $m\le \frac{n(n-1)}{2}$，$k\le 10^9$，最开始给定固定的 $s$ 和 $t$。

首先我们能发现，如果没有不连续经过同一条边的限制就是直接将到达关系转化成邻接矩阵 $E$，然后求 $B\times E^k$，其中 $B$ 为初始矩阵，也就是只有 $s$ 的位置为 $1$。

于是容易想到去容斥，容斥的话要知道具体到了哪一个点，于是我们记 $f(i,j)$ 表示走 $i$ 条边到 $j$ 的方案数（满足题目条件）。

然后我们能发现对于 $i>2$：$$f(i,u)\leftarrow (\sum _{v\to u}f(i-1,v))-({\text{degree}}_u-1)\times f(i-2,u)$$

也就是说我们减去在 $i-2$ 步后走两步走回到 $u$ 的方案，但是 ${\text{degree}}_i$ 要减去 $1$ 的原因是 $i>2$ 时，你 $f(i-1,v)$ 不会考虑 $v\to u\to v$ 的方案。然而 $f(i-2,u)$ 会考虑 $v\to u$ 的方案，也就是说，你多减去了 $v\to u\to v\to u$ 的方案，要加上。

根据上文分析，容易发现 $i=2$ 时不用减掉 $1$ 即可，$i=1$ 不需要容斥。

不难发现这是线性变换，于是你维护一个 $(2n)\times (2n)$ 的矩阵来转移即可。

注意到要多测，你直接暴力是 $O(q\times n^3\log k)$ 的，无法通过，我赛后才了解到有这么一个技巧：我们预处理快速幂需要访问到的矩阵，也就是转移矩阵的 $2^x$，然后就转化成为向量乘矩阵，这个东西得到的也是向量，于是可以 $O(n^2)$ 的乘，总复杂度 $O(n^3\times \log k+q\times n^2\log k)$。

T3

有 $2n$ 个人，你要将他们平分成 $2$ 组，然后给出 $m$ 个二元组 $(a_i,b_i)$，表示若编号为 $a_i$ 和 $b_i$ 的人被分到同一组，会对划分的代价增加 $2^i$ 的贡献。求最小划分代价。
$n\le 5000$，$m\le 10^6$，$a_i<b_i$，$(a_i,b_i)$ 互不相同。

考虑没有平分的限制怎么做，这个东西显然可以贪心，用个并查集维护一下连通性即可。

接着考虑需要平分，首先对于一组有关的人（也就是钦定他们划分到相同或者不同的人），他们可以表示成二元组 $(p_i,q_i)$，表示有 $p_i$ 个人分在同一组，另外 $q_i$ 分到另一组，平分的限制就相当于有若干二元组，你需要满足对于每个二元组都选出来一个数，然后让他们的和为 $n$。

这个东西可以用背包检查。但是直接背包是 $O(n^{2}m)$ 的，有一个显然的优化就是我们只会在 $a_i$ 和 $b_i$ 不在一个集合中才会做背包检查，然后如果我们已经检验过不可以就也不会再检查。我们将已经检查过不会合并的两个集合虚拟连边，就可以做到每次都会减少一个集合。于是我们会做 $O(n)$ 次背包，于是复杂度变为 $O(n^3)$，同样的，由于 dp 的是可行性，于是可以 bitset 优化，复杂度变为 $O(\frac{n^3}{\omega })$。

注意到 dp 可行性会浪费异常多的空间和时间，考虑转化成记方案数，但是方案数会特别多，对一个大质数取模即可，我们最多可以取 $2^{18}$ 级别的数。

考虑分析错误概率：$f\le \left(\genfrac{}{}{0ex}{}{10^4}{5000}\right)\le 2^{10^4}\le 10^{4000}$，注意如果我们使得素数 $p_1,p_2,\dots ,p_n$ 失效，那么 $p_1{p}_2{p}_3\dots p_n|f$，注意到 $(10^7{)}^{600}\ge 10^{4000}$，于是最多失效 $600$ 个素数（事实上远远不到），然而 $10^{18}$ 有大约 $\frac{10^{18}}{\ln 10^{18}}\ge 2\times 10^{16}$ 个素数，失效概率为 $\frac{600}{2^{2\times 10^{16}}}$，几乎可以忽略。

我们发现转化成

未完待续。