题意很明确,给定一个数列 \(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=0}j a_i, j = 0, 1, 2, ⋯, n}, δ_{ij} = σ_j - σ_k = ∑_{i = k+1}ja_i$,判断 \(\delta\_{ij}\) 能否被 \(m\) 整除。\(O(n^2)\) 复杂度。照此想法编程,确是 TLE:

#include <stdio.h>

#define max_len 10001

int main(int argc, char *argv[]) {
  int n, m;
  int inta[max_len];
  int sum[max_len+1];

  while (scanf("%d%d", &n, &m) != EOF) {
    int i, j;

    for (i = 0; i < n; ++i) {
      scanf("%d", &inta[i]);
    }

    for (i = 0; i <= n; ++i) {
      sum[i] = 0;
      for (j = 0; j < i; ++j) {
        sum[i] += inta[j];
      }
    }

    int num = 0;
    for (i = 0; i < n; ++i) {
      for (j = i + 1; j <= n; ++j) {
        if (((sum[j] - sum[i]) % m) == 0) {
          num++;
        }
      }
    }
    printf ("%d\n",num);
  }

  return 0;
}

不得不另寻出路。依稀记得当初算法课上关于最大子段和的问题,其复杂度也是一点点从 \(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 这个特殊数字的情况。程序参照上面两篇博客整理下,代码如下:

#include <string.h>
#include <stdio.h>

int c_sum[5001];

int main(int argc, char *argv[]) {
  int i, n, m;
  int temp, sum, num;

  while (scanf("%d %d", &n, &m) != EOF) {
    sum = 0, num = 0;
    memset(c_sum, 0, sizeof(int) * (m + 1));
    for (i = 0; i < n; i++) {
      scanf("%d", &temp);
      sum = (sum + temp) % m;
      if (!sum)
        num++;
      c_sum[sum]++;
    }
    for (i = 0; i < m; i++)
      num += c_sum[i] * (c_sum[i] - 1) / 2;
    printf ("%d\n", num);
  }
  return 0;
}

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