To all the coders, I challenge you to solve this problem !

Revision en1, by Reducto, 2021-08-08 16:24:53

Given a directed graph of N nodes, each node has a value A[i].

There is a directed edge of length 1 from node i to node j if and only if: - | i — j | <= k . The absolute difference between i and j is less than or equal to k. - A[i] > A[j]

For each node X, find B[X] which is the length of the shortest path to a node Y such that A[Y] is a prime number. If there is no way to go to such a node Y then we say that B[X] is 0.

Print the sum of all elements in array B.

Since the answer might be large return it modulo 10^9 + 7.

Constraints

1 <= N <= 10^5 and 1 <= k <= N 1 <= A[i] <= 10^6

Input 1 5 2 2 4 8 16 32

Output 1 6

Input 2 3 1 1 2 4

Output 2 1

Tags #graph, #math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Reducto 2021-08-08 16:33:54 146 Tiny change: 'Given a di' -> 'Hello, Codeforces community.\n\nGiven a di'
en6 English Reducto 2021-08-08 16:31:11 57
en5 English Reducto 2021-08-08 16:30:15 16 Tiny change: 'only if:\n- | i &m' -> 'only if:\n\n- | i &m'
en4 English Reducto 2021-08-08 16:28:33 16
en3 English Reducto 2021-08-08 16:26:45 4
en2 English Reducto 2021-08-08 16:25:56 16
en1 English Reducto 2021-08-08 16:24:53 756 Initial revision (published)