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

· · 个人记录

E.

维护 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 尽量匹配以后的位置，这个预处理也是平凡的）。

M.

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

剩下的情况计算，对“坑”和“值”的配对情况设计一个贡献提前计算 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)。

K.

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

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

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

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

G.

构造，yk 教我的。

L.

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

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

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

实现其实不困难。

J.

十分高明。

首先给出判定条件：不可行当且仅当有一条边超过了总长度的一半。这个边一定是唯一的，因此可以枚举这条边是什么。记为 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 的概率。转移如下：

dp_{i,k+\lfloor\frac{j}{2}\rfloor}\leftarrow dp_{i,k+\lfloor\frac{j}{2}\rfloor}+\frac{1}{2^{c_{i}}}\binom{c_{i}}{k}dp_{i-1,j}

其中 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。

初始状态有：

dp_{0,k+j}\leftarrow dp_{0,k+j}+\frac{1}{2^{c_{0}}}\binom{c_{0}}{k}f_j

其中 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!}

一个推论：当 k 为实数时，g_k=\sum_{i=0}^{\lfloor k\rfloor}\binom{n}{i}(-1)^{i}\frac{(k-i)^n}{n!}。