Codeforces 577B. Modulo Sum

div2Bのレベルなの・・・？

問題

n個の要素からなる数列aと整数mが与えられる。
空でない部分列の和がmで割り切れるような部分列があるかチェックし、あるならYES、ないならNOを返す。

1<=n<=10^6
2<=m<=10^3
0<=a_i<=10^9

考え方

各a_iはmod mを取っておいても問題ない。なので、問題は「0〜(m-1)のn個の整数の和のmod mが0となるものがあるか？」になる。

計算量を無視して考えると、
dp[i][j]:=i番目までを使って、和 mod m = jとなるような和が作れるか？(YES/NO)
というdpで、dp[i][j]が作れる(YES)なら、dp[i+1][(j+a_{i+1})%m]とdp[i+1][j]も作れる(YES)。
各iのうち、dp[i][0]が2以上(1つは何も足さない場合)になっているものがあれば、0となるものを作れるのでYES。
ただし、これだと、O(n*m)になってTLEになってしまっている。

もし、「部分列」ではなく、「連続する部分列」である場合は、先頭からi番目までの和を計算しておくと、同じ和が2回以上でてくれば、その和が出てきたインデクスをl, rとすると、(l+1)〜rまでの和は0になっている、とチェックできる。
実は、n>mであるならば、先頭からi番目までの和はn個でてきて(鳩)、m種類の値(鳩の巣)のどれかになるので、鳩の巣原理より必ず同じ和となる2つ以上の場所が存在する。

なので、n>mなら必ずYESになり、n<=mならば、上のdpで計算してもO(m^2)なので、計算量的に間に合う。