DP #11 Combinatorics DP

B. Mashmokh and ACM

Problem Statement: here

Solution:

We are asked to find out the number of sequences. The dp which we will use to construct the solution is 2D. Given the constraints, 2D dp will pass it.

Let dp[i][j] denote the number of sequences that are of length i and whose last element is j.

Since all the numbers are between 1 and n, we are having O(n*k) space complexity.

The DP transition will be:

dp[i][j] = ∑ dp[i-1][d] where d | j. 

So, we saw that if d divides  j, then dp[i-1][d] will add to dp[i][j]. In general, all multiples of d, which are at most n, will need dp[i-1][d] to be added to their answer.

So, to fast our solution fro O(n*k*sqrt(n)), we can use the harmonic sum complexity of O(nlogn).

The code

ll dp[2005][2005]; void solve() { ll n,k; cin >> n >> k; clr(dp,0); rep(i,1,n+1) dp[1][i] = 1; rep(len,2,k+1){ rep(i,1,n+1){ for(int j=i;j<=n;j+=i){ dp[len][i] = (dp[len][i] + dp[len-1][j])%M1; } } } ll ans = 0; rep(i,1,n+1) ans = (ans + dp[k][i])%M1; cout << ans; }