CF1845E-Boxes and Balls-计数DP,巧妙状态设计

· · 题解

CF1845E - Boxes and Balls

题意

给出一个长度为 n(1\leq n\leq 1500) 的 01 串，需要执行以下操作恰好 m(\leq m\leq 1500) 次：

求：总共能产生多少种本质不同的 01 串，答案对 10^9+7 取模。

思路

注意到，移动前后，所有 1 的顺序不变。

令 f(i,j,k) 表示：当前是 01 串的第 i 位，目前已经移动了第 j 个 1，目前已经进行了 k 次操作，产生的本质不同的 01 串数量。

转移：

f_{i,j,k} = f_{i-1,j,k}+f_{i-1,j-1,|pos_{j}-i|}

其中 pos_j 指的是第原串第 j 个 1 的位置。

注意到实际被移动的 1 的数量不超过 \sqrt m 个，可以由此减少枚举 j 的数量，枚举根号规模即可。