2022-2023:teams:eager_to_embrace_the_seniors_thigh:7j
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:eager_to_embrace_the_seniors_thigh:7j [2022/08/09 20:30] 11231123 [题意] |
2022-2023:teams:eager_to_embrace_the_seniors_thigh:7j [2022/08/09 20:40] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| $n,k\le 64, t\le \frac{n(n+1)}{2}$ | $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+倍）。推测是有用状态不多，可能直接记录有用状态会更快。 | ||
2022-2023/teams/eager_to_embrace_the_seniors_thigh/7j.1660048211.txt.gz · 最后更改: 2022/08/09 20:30 由 11231123
