So, my solution to this problem only passed the first test case. I’m pretty sure that there is some sort of logic error in my code, but I can’t figure out what it is. I tried to replicate the dp table by hand and I also tried to see if there were any missing holes in my logic. I was hoping that you guys could give me a few hints on any issues with my solution.
My solution
#include <bits/stdc++.h>
using namespace std;
const int mxn=1e4+1;
int n,mod,ans,dp[mxn];
vector<int> primes;
bool isprime(int x){
for(int i=2;i<x;i++)
if(x%i==0)
return false;
return true;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
/* freopen("exercise.in", "r", stdin); */
/* freopen("exercise.out", "w", stdout); */
cin >> n >> mod;
for(int i=1;i<=n;i++)
if(isprime(i))
primes.push_back(i);
dp[0]=1;
for(int x=0;x<(int)primes.size();x++){
for(int i=1;i<=n;i++){
if(i>=primes[x])
(dp[i]+=(dp[i-primes[x]]*primes[x]))%=mod;
/* since the sum of the permutation depends on how many permutations
there are without the prime, I multiplied the prime to the dp without that prime.
The solution takes care of the cases with multiple primes factors because of how the
dp table is set up*/
}
}
cout << dp[n];
}