Count of paths

Posted: 7 Jul, 2021
Difficulty: Hard


Try Problem

Given a sequence of N integers: arr0, arr1, arr2, ….. arrN-1 and an integer K

K is divisible by all the array elements, ie: K % arri = 0 for (0 <= i <= N-1).

A directed graph is built using this sequence. A directed edge from the jth to the ith array element exists if j < i and ai is divisible by aj, ie: ai % aj = 0.

Find the count of different paths from 0th element to ith element for 0 <= i <= N-1. As the answer can be very large, return answer modulo 109+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,
You are not required to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= N <= 5 * 10^4    
1 <= K <= 10^9  
1 <= ai <= 10^5

Time limit: 1 sec
Approach 1

For each position in range 1 to N-1 we will find all jth 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 0th position and simply increase the count for ith node each time it is visited. Return the final answer for each ith position.


The steps are as follows:

  1. Build an adjency-list to store edges of the graph.
  2. Declare a array/vector to store the count of paths. ie: vector<int> VIS
  3. Initialize all elements in VIS to 0.
  4. Apply dfs from 0st position.
  5. Each time ith position is visited, increment VIS[i].
  6. Our answer is finally stored in VIS vector.
Try Problem