# Count of paths

#### Given a sequence of **N** integers: arr_{0}, arr_{1}, arr_{2}, ….. arr_{N-1} and an integer **K**

**K** is divisible by all the array elements, ie: **K % arr**_{i} = 0 for (0 <= i <= N-1).

_{i}= 0

##### A directed graph is built using this sequence. A directed edge from the j^{th} to the i^{th} array element exists if **j < i** and a_{i} is divisible by a_{j}, ie: **a**_{i} % a_{j} = 0.

_{i}% a

_{j}= 0

#### Find the count of different paths from 0^{th} element to i^{th} element for 0 <= i <= N-1. As the answer can be very large, return answer modulo 10^{9}+7.

##### Input Format:

```
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.
The first line contains two integers, 'N' and 'K', where N represents the sequence length.
The next line contains N integers, 'ai' for (0 <= i <= N-1).
```

##### Output Format:

```
Print N integers, where ith element denotes the count of different paths from 1st element to ith element.
Output for each test case will be printed in a separate line,
```

##### Note:

```
You are not required to print anything; it has already been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= 10^9
1 <= ai <= 10^5
Time limit: 1 sec
```

For each position in range 1 to N-1 we will find all j^{th} positions that satisfy the condition for existence of edge from j to i. And we will store all the edges in form of an an adjency list.

^{As the input sequence can have duplicate values, so rather than the value at a position, consider position index itself as vertices while storing the graph in form of an adjency-list.}

Apply dfs from 0^{th }position and simply increase the count for i^{th} node each time it is visited. Return the final answer for each i^{th }position.

The steps are as follows:

- Build an adjency-list to store edges of the graph.
- Declare a array/vector to store the count of paths.
- Initialize all elements in VIS to 0.
- Apply dfs from 0
^{st}position. - Each time i
^{th}position is visited, increment VIS[i]. - Our answer is finally stored in VIS vector.

Edge can only exist from j to i if j < i. We don’t need to worry about elements to the right-side of i^{th} position while finding the count of paths from 0^{th }to i^{th }element.

We can simply declare a dp array/vector of size N and initialize dp[0]=1 and the initialize rest elements as 0, ie: dp[i]=0 for (1 ≤ i ≤ N-1). Here dp[i] will denote the count of paths from 0^{th }to i^{th }element.

To calculate the value of dp[i], we need to simply iterate for all positions to the left of ‘i’ and if the element of the sequence is divisible by i^{th }element, we will add its count of paths to dp[i].

Finally return elements of dp[i] as they store the count of different paths for i^{th }element.

The steps are as follows:

- Declare a dp array/vector of size = ‘N’, and initialize all elements equal to 0.
^{dp[i] denotes the count of paths from 0th to ith element.} - Assign dp[1] = 1 (base condition)
- Iterate through elements of the dp array, ie: run a for loop from 1 to N-1.
- Calculate dp[i] using another loop that iterates from 0 to i-1. If the element of the sequence is divisible by i
^{th}element of the sequence, then simply add its count to dp[i].

Finally, return the elements of dp[i]

Edge can** only exist** from **j** to **i** if **j** < **i**. We don’t need to worry about elements to the right-side of **i ^{th}** position while finding the count of paths from

**0**

^{th}^{ }to

**i**

^{th}^{ }element.

We can simply declare a **dp** array of size **N** and initialize **dp[0] **=** 1** and the rest elements equal to 0. Here **dp[i]** will denote the count of paths from **0 ^{th}**

^{ }to

**i**

^{th}^{ }element.

We can only reach **i ^{th}**

^{ }element from factors of

**a[i]**on the left of the element.

So there is no point in iterating from 0 to **i**-1 to calculate **dp[i]**, we can simply search for factors of **a[i]** lying on the left of **i ^{th }**position and add their count to

**dp[i]**.

We can simply store the given sequence of elements as an unordered_map, where the key of the map denotes the element, and the value of the map stores the positions of that element. Hence we can use an unordered_map of int and vector if int.

We can now simply iterate through the **dp** array, to calculate **dp[i]** we will first find factors of a[i], this can easily be done in sqrt(**a[i]**). We will then search each factor of **a[i]** in the unordered_map in O(1), if the elements exist, we will add the count to **dp[i]** corresponding to all the positions less than i.

The steps are as follows:

- Create unordered_map<int, vector<int> > MP
- Iterate all the elements of sequence and fill up the unorder map using MP[ a[i] ].push_back(i).
- Declare a dp array of size=N, and initialize all elements equal to 0.
^{dp[i] denotes the count of paths from 1st to ith element.} - Assign dp[1]=1 (base condition).
- Iterate through elements of the dp array, ie: run a for loop from 0 to N-1, for each iteration calculate all the factors of a[i].
- Search the factors of a[i] in the unordered_map and add the count to dp[i] for all the factors that are on the left of i
^{th}position.

Finally, print all the elements of dp[i]