nowcoder multi 7J

题目描述

给定 、 、 ，问一个长为 ， ，所有非空连续子序列中和能够被 整除的子序列个数恰好为 的序列一共有多少个。

解题思路

一看到 非空连续子序列 ，我们就考虑 前缀和 。本题从这里切入，我们将连续子序列的和能够被 整除转化为两个前缀和在模 意义下的差值为 。进一步研究可以发现，任何序列与其前缀和序列都是唯一对应的，因此我们可以将这一问题转化为，在一个长度为 的模 前缀和序列中，有多少个数对相等。

设前缀和为 的位置的个数为 。那么有，

我们使用二维背包来解决这一问题，注意特判前缀和取 时，其单点就对答案有贡献。

可以从另一种角度来理解这一特判，当我们构造一个前缀和序列的时候，其实我们构造了一个 的长度为 的序列，我们隐含构造的 对答案的影响不能忽略。