CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== Melborp Elcissalc ======

==== 题意 ====

给定 $n, k, t$ ，求长度为 $n$ 且每个数均在 $0 ~ k-1$ 的数列中，和为 $k$ 的倍数的子段有恰好 $t$ 个的数列有多少个。

$n,k\le 64, t\le \frac{n(n+1)}{2}$
==== 题解 ====

注意到前缀和数组确定后能唯一确定出一个序列，所以我们考虑前缀和数组的每位是几就可以不重不漏的算到每种情况。对于一个前缀和数组，我们可以用 $\sum_{i=0}^{k-1}{\binom{cnt_i}{2}}$ 来算出这个数列的和为 $k$ 的倍数的子段个数。

考虑 $dp_{i,j,h}$ 表示已经考虑了前缀和为 $[0,i]$ 中的位置，共有 $j$ 个位置被考虑了，有 $h$ 个子段和为 $k$ 的倍数。然后每次枚举有多少个位置的前缀和为当前数进行转移，复杂度是 $O(n^5)$ 。

这个复杂度有点小高，我一开始那个写法没过。考虑外层先枚举上一步的状态，然后只用非0的状态进行转移，这样就快了不少（10+倍）。推测是有用状态不多，可能直接记录有用状态会更快。

CVBB ACM Team

用户工具

站点工具

页面工具