**This is an unofficial editorial and I may have complicated or simplified the problem.**

**PROBLEM LINK:**

**DIFFICULTY:**

Easy

**PREREQUISITES:**

Basic DP

**PROBLEM:**

You are given an array of **N** integers and two integers **K and M**. Find the number of subsequences of the array of length K such that:

`S[i] % M = i % M (for each i from 1 to k)`

You need to print the answer modulo (10 ^ 9) + 7

**QUICK EXPLANATION:**

We will maintain an array from 1 to k which will store the **value of the number of subsequences of length 1 to k** formed **for each i from 1 to n**. Here the time complexity will be O(n * k) which will give us a TLE. To overcome that, we need to optimize our approach **a bit**. This can be done by observations.

**EXPLANATION:**

We see that we donâ€™t need the original array. **All the operations are in the form of mod m.** So our first step will be:

for each i from 1 to n

a[i] = a[i] % m;

Now, as we only need a **single subsequence**, we **store the subsequence** in an array of length k. So the next step will be:

for each i from 1 to k

seq[i] = i % m;

Now, here comes the **observation part which leads to AC instead of TLE.**

We see, that the same number in the subsequence is repeating itself **periodically**. **The distance between two similar numbers is m.** So we donâ€™t take k iterations, we take (k / m) iterations, which leads to AC.

**Now lets define the recursion of dp**

## Recursion of dp

Firstly, lets define dp[i].

dp[i] means *the number of subsequences in the array* till position j (from 1 to n) of the *first i (from 1 to k) integers in the sequence.*

Now for the recursive formula, I am taking an example:

For example a[i] = 3, m = 4, k = 3.

Now our **seq array will be [1, 2, 3]**

Thus,

as (a[i] % m == seq[3] % m)

Now, the **new subsequences of length 3** will be formed will be **all subsequences of length 2 formed before this index, which is stored in dp[2].**

And **not to forget that there are some subsequences already formed before this index**

Thus,

dp[i] = dp[i - 1] + dp[i];

Thus,

for each i = start to 1

step m

dp[i] = dp[i - 1] + dp[i];

dp[i] = dp[i] % ((10 ^ 9) + 7);

Finally we arrive to the **answer, which is dp[k]**.

Just be careful when m = 1.

**TIME COMPLEXITY:**

*O(N * (K / M) ) per each test case*

**SOLUTION:**

Always feel free to ask me any query about this editorial and rate this editorial on 5.

- Awful
- Bad
- Average
- Good
- Excellent

0 voters