PKU 3844 Divisible Subsequences
http://poj.org/problem?id=3844
n個の数字からなる数列が与えられる。
このn個の数字の連続する部分列でその和がdで割り切れるものは何通りあるかを答えるというような問題。
nが大きいのでO(n^2)だとアウト。
ある連続する部分列(a_i〜a_j)の和がdで割り切れるとき、
(a_0+a_1+a_2+・・・+a_(i-1))%d=(a_0+a_1+a_2+・・・a_j)%dとなる。
これを利用すれば、a_iまでの数字を見たときに、それまでの和をdで割った余りが同じものがそれ以前の数列の和にいくつあったかを数えることで求めることが出来る。
時間制限は相当厳しいもよう。
int in; int app[1000000]; main(){ int test; cin>>test; while(test--){ memset(app,0,sizeof(app)); int n,d; cin>>d>>n; int sum=0,ans=0; app[0]++; rep(i,n){ scanf("%d",&in); sum=(in+sum)%d; ans+=app[sum]; app[sum]++; } cout<<ans<<endl; } }