ZOJ 1569

题意很明确，给定一个数列 $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;
}

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