题意很明确,给定一个数列 \(a\_i(i = 0, 2, \cdots, n)\) ,对于 \(m\) ,求有多少个 partial sum 能被 \(m\) 整除,所谓 partial sum 是 \(\sum\_{i = j}^{k} a\_i, j, k \in 1, \cdots n}\)

想法也很简单。第一种方法是求出所有的 partial sum,然后分别判断是否能被 \(m\) 整除, \(O(n^3)\) 的复杂度。

第二种想法是设定 $σ\j = ∑\i=0j a\i, j = 0, 1, 2, ⋯, n}, δ\ij = σ\j - σ\k = ∑\i = k+1ja\i$,判断 \(\delta\_{ij}\) 能否被 \(m\) 整除。\(O(n^2)\) 复杂度。照此想法编程,确是 TLE:

不得不另寻出路。依稀记得当初算法课上关于最大子段和的问题,其复杂度也是一点点从 \(O(n^3) -> O(n^2) -> O(n \log(n)) -> O(n)\) ,在此百度如下两篇文章,茅塞顿开:

大体思路是继续第二种想法,设 \(\phi\_j = \sigma\_j \bmod m\) ,如果存在 \(j\_k, k = 1, 2, \cdots, n\) ,那么 \(\phi\_{j\_k} - \phi\_{j\_s}\) 表示一个符合条件的 partial sum,此类 partial sum 可以利用组合数公式 \(c(n, 2) = \frac{n(n-1)}{2}\) 求出。最后注意考虑 0 这个特殊数字的情况。程序参照上面两篇博客整理下,代码如下:

路漫漫其修远兮,加油加油。