# Algorithm analysis

I need to find the number of subsequence in an array which are divisible by an integer P.
The solution is tricky dynamic programming… how is this code working …??

``````#include<iostream>
#define SIZE 10002
#define LL long long
using namespace std;

LL ans=0;
LL cnt[SIZE],nums;
int main()
{
int T;
cin>>T;
for(int t=1;t<=T;t++){
int N,P;
ans=0;
cin>>N>>P;
for(int i=0;i<P;i++)
cnt[i] = 0;
cnt[0]=1;
int d=0;
LL sum = 0;
for(int i=0;i<N;i++)
{
cin>>nums;
sum += nums;
d = sum%P;
cnt[d]++;
}

for(int i=0;i<P;i++)
{
LL val = cnt[i]*(cnt[i]-1);
ans += val/2;
}

cout<<"Case #"<<t<<"\n"<<ans<<endl;

}
}``````

The sum of the subsequence [l; r) (0-based, from l-th element (inclusive) to r-th element (exclusive)) is clearly sum of first r elements minus sum of first l elements.
So it is divisible by P iff the remainders of these two prefix sums are equal.

Thus, if the number of prefixes which sums give the remainder, say, A, is equal to C, they give C * (C - 1) / 2 correct subsequences.

//