做题记录 25.10.15

· · 个人记录

\textcolor{black}\odot CF1608F MEX counting

令 f_{i,j,k} 表示 a_{1\sim i} 中，\le k 的值确定且其 \text{mex} 为 k，>k 的有 j 种值的方案数

初始 f_{0,0,0}=1，显然 f_{i,j,k}=0\;(k<b_i-k\lor k>b_i+k)，答案为 \sum_j \sum_k f_{n,j,k} P_{n-k}^j

考虑 f_{i,j,k} 的转移

若 \text{mex} 不变，新填的数 <k 的贡献为 f_{i+1,j,k}\gets k\cdot f_{i,j,k}，>k 且不新增值的贡献为 f_{i+1,j,k}\gets j\cdot f_{i,j,k}，新增值的贡献为 f_{i+1,j+1,k}\gets f_{i,j,k}

若改变，设变为 t\;\;(t>k)，则 f_{i+1,j-(t-k-1),t}\gets f_{i,j,k}P_j^{t-k-1}

暴力实现时间复杂度为 O(n^4)

显然 k 的取值只有 O(k)（题目给定的 k）种，因此容易做到 O(n^2k^2)，滚动数组做到空间 O(nk)

令 f_{i,j+k,k}\gets f_{i,j,k} 并整理转移方程，发现可以前缀和优化

时间复杂度 O(n^2k)，空间复杂度 O(nk)

代码

参考

\textcolor{black}\odot AT_arc117_e [ARC117E] Zero-Sum Ranges 2

以下用 m 表示题目给定的 k

对于确定的 a_{1\sim 2n}，令 s 为其前缀和，令 c_x=\sum_{i=0}^{2n}[s_i=x]，则合法 (l,r) 数量为 \sum_x \binom{c_x}2

考虑按 s\ge 0 和 s<0 分为两部分，令 f_{i,j,k} 表示选择了一些值（从大到小加入），总数为 i，其中 \sum \binom{c_x}2 为 j，中间有 k 个断点，且 k+1 段之间的顺序没有确定的方案数

初始 f_{i,\binom i2,i-1}=1，答案为 \sum_i\sum_j\sum_k f_{i,j,k}f_{2n+1-i,m-j,k-1}

考虑转移，枚举下一层放置数量 l，显然 l\ge k+2，则新的 i 为 i+l，新的 j 为 j+\binom l2，新的 k 为 l-2-k，将这 l 个分为 k+2 部分，分别放置到空隙中，且每个空隙至少放一个，方案数为 \binom{l-1}{k+1}

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

代码

参考