2024 CCPC 网络赛 F 题题解

包子鸡蛋Ⅲ

https://codeforces.com/gym/105336/problem/F

首先将这 26 种字符的概率合并为三种 \(p_e,p_g,p_o\) ，分别为 e ，g 和其它字符出现的概率。

当长度相同时，该长度子串为“好串”的概率是相同的。设 \(f(l)\) 为长度为 \(l\) 的子串是好串的概率，则答案为

\[\sum_{i=1}^n (n-l+1)f(l) \]

考虑如何计算 \(f(x)\) ，我们可以将一个子串分为 eg 部分和其它字符的部分。设 \(g(l)\) 为长度为 \(l\) 的 eg 字符串为好串的概率，将这个 eg 串作为原串的子序列放入原串中，我们就能得到

\[f(x)=\sum_{i=0}^xp_o^{x-i}g(i)\binom n i=x!~\sum_{i=0}^x\frac {p_o^{x-i}g(i)}{(x-i)!i!} \]

这是一个卷积形式，可以用 NTT 加速。

接下来考虑如何计算 \(g(x)\) 。现在问题变成了已知 01 出现的概率，求出 1 到 \(n\) 每个长度的 01 串，正好有 \(m\) 个子序列为 100 的概率。不难想到设 \(h(i,j,k)\) 为长度为 \(i\) ，已有 \(j\) 个 100 子序列，末尾有 \(k\) 个 0 时的概率，通过不断在字符串开头添加 01 来转移能求出所有 \(g(x)\) 。但是这样的 复杂度是 \(O(n^2m)\) 的，不能通过。

思考这类 01 串的性质，将这 01 串分为三部分，

\[\dots|1\dots|0\dots0\dots \]

第一部分，在串的最末尾，结构为 \(0\dots 0 \dots\) ，省略部分填入任意的 \(1\) ，这部分不存在子序列 100 ；第二部分，结构为 \(1\dots\) ，省略部分填入任意 \(0\) 或 \(1\) ，要求与第一部分合并起来后 100 正好为 \(m\) 个，显然这部分长度要小于 \(m\) ，\(0\) 的个数 \(t\) 也要满足 \(t(t-1)\le2m\) （否则 100 子序列个数一定超过 m）；第三部分，在串开头，填入任意个 \(0\) ，对 100 无贡献。

第二部分的计算，设 \(h(i,j,k,0/1)\) ，长度为 \(i\) ，已有 \(j\) 个 100 子序列，末尾有 \(k\) 个 0 ，开头为 \(0/1\) 时的概率，转移如下

\[\begin{align} h(i,j,k,0)&=p_g[h(i-1,j,k-1,0)+h(i-1,j,k-1,1)]\\ h(i,j,k,1)&=p_g[h(i-1,j-\binom k 2,k,0)+h(i-1,j-\binom k 2,k,1)] \end{align} \]

计算这部分的复杂度为 \(O(m^2\sqrt m)\) 。

设 \(H(i)=\sum_{j\ge1}h(i,m,j,1)\) ，\(I(x)\) 为包含第一第二部分长度为 \(x\) 的好 01 串的概率，那么可以得到

\[I(x)=\sum_{i=0}^x(i-1)p_g^2p_e^{i-2}H(x-i) \]

包含一二三部分的好 01 串也能通过类似方法得到

\[g(x)=\sum_{i=0}^x p_g^{i}I(x-i) \]

这两部分计算都能用 NTT 加速。到这里我们就解决了整个问题，时间复杂度为 \(O(m^{2.5}+n\log n)\) 。