YACS 2023年5月月赛 甲组 T1 子集和（六） 题解

题目链接

YACS 老师说这是道分治，但就不告诉我怎么做，我硬是用线段树卡了过去...特别解气的是把 AC 图片发了过去（我就是在 YACS 上的编程课）

好了说点正经的，看到是谁谁谁的倍数就能想到 DP，状态设计也很水啦！设 $f[i]$ 为当前考虑到的区间内，子集和 $\% k = i$ 的数量。

新加入一个元素时，循环 0 ~ k - 1，更新 $f[i] = f[i - value] + f[i]$（value 是当前加的值，i - value 有可能为负，要取个模大家自己去弄）

这里还不能滚动数组，因为最前面的还会用到最后面的。

每次询问把 $f$ 清空，然后对参数 $l$ $r$ 做 DP 就可以做到 $O(qnk)$ 的复杂度，显然爆炸。

接着就开始了漫长的优化之旅。

首先让我想到的，是莫队，但是这个 dp 它不支持删除元素啊，所以还要搞不删除莫队，我懒了直接用在线莫队。

在线莫队我讲过，这里不废话，时间复杂度就是 $O(q\sqrt{n}\cdot k)$，然后循环展开了只能过 7 个点，看来是取模的问题。