Algorithm analysis

general
,
1

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;

    }
}
2

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.