The 3rd Universal Cup. Stage 2: Zielona Góra

维护 $f_{i,j}$ 表示从 $S_{i}$ 的开头，从给定串的第 $j$ 个位置往右贪心匹配最长匹配多少，$g_{i,j}$ 是从 $S_{i}$ 的结尾，从给定串的第 $j$ 个位置往左贪心匹配最长匹配多少。这两个量容易类似倍增维护。

若答案串第一次出现在 $S_{i}$ 里，那么这个子串一定跨过 $S_{i-1}$ 和 $S_{i-2}$，不然 $i$ 可以更小。枚举这个 $i$（显然是 $\log$ 级别的）利用 $f,g$ 取最小值即可（可能需要额外记录 $f,g$ 尽量匹配以后的位置，这个预处理也是平凡的）。

这类题就是枚举每一位是什么，计算剩下的位置满足情况的排列数即可。

剩下的情况计算，对“坑”和“值”的配对情况设计一个贡献提前计算 dp 即可。如：$dp_{i,j,k,l}$ 表示前 $i$ 个物品，当前总贡献是 $j$，还有 $k$ 个没有配对的坑，$l$ 个没有配对的值得方案数。转移 trivial，最终要求 $dp_{*,*,0,0}$。其中 $k,l$ 可以互相表示，状态数可以降低一维。dp 复杂度 $O(n\times n^2\times n)=O(n^4)$。外层枚举复杂度 $O(n^2)$，总复杂度 $O(n^6)$。

我们将设计一种做法证明合法区间数量是 $O(n\log n)$ 并能够直接求出。求出后就简单了，直接 dp 即可。

考虑分治，每次仅考察跨过中点的区间。计算 $mid$ 往前的后缀二进制表达（把每个值视为二进制后后缀和的二进制）的 hash（可以取 sum hash） $l$ 和 $mid+1$ 往后的前缀二进制表达的 hash $r$。

关键观察：对于一个二进制表达，最高位不高于他自己的二进制表达中，和他加起来能凑成合法区间（只有一个位是 1）的表达只有 1 个。且这个数是容易计算的。

那就好了，枚举每个表达，钦定他是高位更高的一个，去另一个区间里找能凑起来的就好了。显然这一轮找出的合法区间数量是 $O(len)$ 的，根据这种分治的结论，$\sum len=O(n\log n)$。

构造，yk 教我的。

神经题。断环成链，合法即为没有选择的区间相交。

朴素 $dp$ 是 $dp_{l,r}$ 表示只考虑区间 $[l,r]$ 的答案，转移很简单。

考虑随机的意义。它保证了答案不大。同时 $dp_{l,r}$ 关于 $l$ 是有单调性的，所以只需要记录变化的位置即可。可以用 vector 存。

实现其实不困难。

十分高明。

首先给出判定条件：不可行当且仅当有一条边超过了总长度的一半。这个边一定是唯一的，因此可以枚举这条边是什么。记为 $i$，我们想要计算 $P(X_i\ge \sum_{j\neq i}X_j)$。

注意到 $X_i\sim U(0,2^{a_i})$，$2^{a_i}-X_i$ 同样服从 $U(0,2^{a_i})$，因此可以说 $P(X_i\ge \sum_{j\neq i}X_j)=P(2^{a_i}-X_i\ge \sum_{j\neq i}X_j)=P(2^{a_i}\ge \sum_i X_i)$。现在问题转化为求 $\sum_i X_i\le 2^k$ 的概率。

设离散随机变量 $A_i$，其仅有两种取值 0 和 $2^i$，概率各为 0.5。显然有 $X_i=U(0,1)+\sum_{j=0}^{a_i-1}A_j$。

设计 $dp_{i,j}$ 表示已经考虑完前 $i$ 位，此时第 $i$ 位上有 $j$ 个 bit 的概率。转移如下：

其中 $c_i=\sum_{j}[a_j\ge i]$ 表示 $A_i$ 有多少个，并枚举有多少个抽中了 $2^{i}$。下取整是在考察进位。

于是我们有 $P(\sum_i X_i< 2^k)=dp_{k,0}\times \frac{1}{2^{\sum_{i=k+1} c_i}}$。即，在 $k$ 位及以前不能出现 $k$ 上的位，同时 $k$ 位以后的所有随机变量都得抽中 0。

初始状态有：

其中 $f_j$ 是那堆 $U(0,1)$ 的和 $\in [j,j+1)$ 的概率。这个东西的计算也很有讲究。

设 $\text{i.i.d.}\ S_1, S_2, \dots S_n \sim U(0,1)$，则 $g_k=\sum_{i=0}^{k-1} f_i=P(\sum_j S_j\le k)$。求出 $g_k$ 易得 $f_i$。

易得在我们的设定下概率等于高维体积，因此我们转向体积的计算。我们放开取值上界。所有数都没有取值上界时，体积为 $\frac{k^n}{n!}$，可以归纳证明。

假设至少有 $x$ 个数取值 $>1$，则将这 $x$ 个数的取值都减去 1 即可转化为原问题。因此恰有 $x$ 个数取值 $>1$ 的体积是 $\frac{(k-x)^n}{n!}$，当然需要满足 $k-x\ge 0$。

进行二项式反演即可得到 $g_k=\sum_{i=0}^k\binom{n}{i}(-1)^{i}\frac{(k-i)^n}{n!}$