学步园

题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=569

题目的意思很明了，就不翻译了。。哥也是没有过四级的人啊。。。

这道题的数据量是10000，所以直接预处理+暴力的话是O(n^2)的，肯定会超时

所以程序还有待于优化。

注意到，题目只需要我们求出有多少个序列的和是m的倍数，而不需要知道具体这些序列是什么。

于是我们可以预先构造一个sum[i]序列

让sum[i]=a[1]+a[2]+a[3]+......+a[i]

并且让sum[i]=sum[i]%m

因为如果当sum[k1]==sum[k2]的时候，那么必然就有sum[k1]-sum[k2]=y*m

于是乎我们可以预先去计算每一个sum[i]出现的次数

然后根据组合学的公式去依次的加出这些子序列的个数

我的解法：

#include<stdio.h><br /> #include<string.h></p> <p>int sum[10005];<br /> int num[5005];<br /> int a[10005];</p> <p>int main()<br /> {<br /> int i,n,m,ans;<br /> while(scanf("%d%d",&n,&m)!=EOF)<br /> {<br /> sum[0]=0;<br /> ans=0;<br /> memset(num,0,sizeof(num));<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%d",&a[i]);<br /> sum[i]=(sum[i-1]+a[i])%m;<br /> num[sum[i]]++;<br /> }<br /> ans=(1+num[0])*(num[0])/2;<br /> for(i=1;i<=m-1;i++)<br /> {<br /> if(num[i])<br /> ans=ans+num[i]*(num[i]-1)/2;<br /> }<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }