ZJU/ZOJ 1569 Partial Sums 解题报告

题目大意是求一段序列中子序列之和除m余0的子序列数量。

用sum[i]表示∑a[i]，题目所求即所有(sum[i]-sum[j]) mod m=0的组合数量（包括sum[0]）。(sum[i]-sum[j]) mod m=0即sum[i]与sum[j]除m的余数相同，所以可以记录sum[i]除m的每种余数的数量。用f[j]表示sum[i]除m余j的数量，则ans=∑f[j]*(f[j]-1)/2。

1653449    2008-10-01 23:23:58     Accepted    1569    FPC    10    120    IwfWcf