0

Count of paths

Difficulty: HARD
Contributed By
Anshul Garg
Avg. time to solve
50 min
Success Rate
60%

Problem Statement

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,
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
Sample Input 1:
2
6 60
1 2 3 4 5 6
1 10
5
Sample Output 1:
1 1 1 2 1 3 
1 
Explanation of sample input 1:
For test case 1:
There is exactly one path to reach 2: 1->2
There is exactly one path to reach 3: 1->3
There are two paths to reach 4: 1->4 and 1->2->4
There is exactly one path to reach 5: 1->5
There are three paths to reach 6: 1->6, 1->2->6 and 1->3->6

For test case 2:
There is only one element, therefore output will be 1.
Sample Input 2:
1
7 120
2 3 4 8 5 6 10
Sample Output 2:
1 0 1 2 0 1 1
Reset Code
Full screen
copy-code
Console