zoj 1569 - 行者无疆 始于足下 - 行走,思考,在路上

zoj 1569

xiaohanyu posted @ Mon, 24 May 2010 23:01:59 +0800 in Algorithm with tags ZOJ Algorithm , 2085 readers

题意很明确,给定一个数列[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],在此百度如下两篇文章,茅塞顿开:

 大体思路是继续第二种想法,设[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;
}

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


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee