Number of Paths
All submissions for this problem are available.
Read problems statements in Russian here
The Head Chef is interested in studying interactions between his chefs . There are N chefs with ids 1 to N . Each chef trusts some of the other chefs . The relation of trust is one way . Also , a chef may trust chefs only with ids strictly greater than his/her id .A chef with id = i , trusts the chefs with next ni id's.
The Head Chef wants to know given a chef B and a set of chefs S, how many lines of trust exist between each element of S and B . A line of trust between chefs A and B is a sequence of chefs a1 ... ak starting at A ( a1 = A )and finishing at B (Ak = B) such that Ai trusts A(i+1) for all i ( 1 to k-1) . Two lines of trust are different if they have a different chef at the some position in the line .
Since the answer may be quite large , output it modulo 1000000007 .
- The first line contains a two space seperated integers N and B denoting the number of chefs and the target chef for whom the lines of trust have to be calculated.
- The next N lines contains an integer ni denoting the number of chefs which are trusted by the chef with id = i .
- The next line contains a single integer Q denoting the number of queries
- The next Q lines contain elements of set S .
- Output a single line for each query containing the answer to the query.
- 1 ≤ N ≤ 200000
- 1 ≤ B ≤ N
- 1 ≤ Q ≤ 100000
- 1 ≤ Each element of set S < B
- 1 ≤ i + ni ( for i = 1 to N ) ≤ N
- 0 ≤ ni ( for i = 1 to N ) ≤ N - 1
Input: 3 3 2 1 0 2 1 2 Output: 2 1
Example case 1. The lines of trust between 1 and 3 are
1 , 3
1 , 2 ,3
There is one line of trust between 2 and 3 which is
|Tags||cook40, dynamic-programming, fenwick, medium, vineetpaliwal|
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.