The number of prime numbers in range [1, 8000] are 1007(10^3 approx). Let C[i] be the number of occurrences of the i-th prime number in the array. Now we have to calculate DP with parameters DP[position][count] - which is the number of good subsequences that we use prime numbers up to position-th and our subsequence contains exactly count prime numbers. If we are on state DP[position][count] we can do two things: do not use position-th prime number (and do DP[position+1][count] += DP[position][count]) or use position-th prime number (and do DP[position+1][count+1] += DP[position][count]*C[position], because you have C[position] of position-th prime number). Sum of the last row of the DP will be our required result. Also take modulo while calculating the DP and also while adding up the last row.
Can anyone help me with this, showing segmentation fault/runtime error. Hereās the code , I have commented it to make it a bit readable. Please help me out guys!
#define mxf 1010
...
int pf[mxf] = {}; //pf array to store frequency of all primes present
...
cin>>a;
pf[a] += 1; //increasing frequnency of prime 'a'
From the Problem Constraints, a can be as high as 8000.
why havenāt we filled default values for dp[0][i] where 1<= i <= max(k, 1007) ?
if we donāt do this how can we access dp[i - 1][j - 1] for i = 1 and j = 2