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

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

第二种想法是设定[tex]\sigma_j = \sum_{i=0}^{j} a_i, j = 0, 1, 2, \cdots, n}, \delta_{ij} = \sigma_j - \sigma_k = \sum_{i = k+1}^{j}a_i[/tex]，判断[tex]\delta_{ij}[/tex]能否被[tex]m[/tex]整除。[tex]O(n^2)[/tex]复杂度。照此想法编程，确是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;
}

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

• http://hi.baidu.com/hi_chf/blog/item/50017817903f0e11972b43e9.html
• http://bloodybat.blog.hexun.com/2788438_d.html

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

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

int c_sum[5001];

int main ()
{
    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;
}

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

• Relative Posts