做题记录 25.8.30

· · 个人记录

QOJ #7644. Good Splits

令 H 表示卡特兰数

用 () 表示连线在上方，[] 表示连线在下方，则用 f_n 表示长度为 2n 且 (),[] 分别匹配的方案数，显然 f_n=\sum_{i=0}^n \binom{2n}{2i} H_{i} H_{n-i}

令 c_{x,l} 表示将 l 划分为 x 个自然数，一种划分方案的权值为每段的 f 之积，所有划分方案的权值和，其转移是容易的

令 dp_n 表示满足 f_n 的条件的基础上，不存在一个子区间使得区间内和删除该区间后剩余部分都合法（若将匹配的括号作为一个点，若两组匹配相交且不包含则连边，要求得到的图连通），则

dp_n\gets f_n-\sum_{i=1}^{n-1} dp_{n-i} c_{2(n-i),i}

即在 f_n 的基础上减去不合法的数量，其中枚举第一个字符所在连通块大小为 2(n-i)，将剩余 2i 个字符分为 2(n-i) 组，依次填入 2(n-i) 个空隙（不含第一个字符以前的位置）中

令 rs_i 表示 i 的答案，令 g_{x,l} 表示将 l 划分为 x 个自然数，一种划分方案的权值为每段 rs 之积，所有划分方案的权值和

对于同一 l 先计算 rs_l 再计算 g_{\ast,l}

计算 rs_l 时枚举最外侧的连通块大小，剩余部分填到空隙中，可得 rs_l=\sum_{i=1}^l dp_i g_{i+i,l-i}

计算 g 是容易的

总时间复杂度 O(n^3)

代码

参考