Chef is standing in the centre of a circle. The perimeter of the circle is divided into h units (numbered 1 through h) and some of those units contain buildings. There are N buildings in total (numbered 1 through N); let's denote the position of building i, i.e. the number of the unit containing this building, by pi. Note that a unit may contain more than one building.
Chef has a vision range equal to x. This means he can look at an arbitrary contiguous range of x units at the same time.
Chef likes to play with his girlfriend Cheftanya. Since he belongs to Wakanda, he decided to play a shooting game. In this game, he is going to look in some direction and shoot all the buildings he sees (without looking in any other direction). Cheftanya chooses the direction in which he looks; since she loves mathematics, she is going to choose this direction randomly using a special probability density function defined below. Before playing the game, though, she is interested in the expected number of buildings Chef will shoot. Chef is going to be busy shooting, so she asks for your help. Can you impress Cheftanya with your skills?
This expected value can be written as a fraction P/Q, where P and Q are coprime. Since we are in the 21st century, nobody is interested in fractions. Therefore, you should compute P⋅Q−1 modulo 163577857, where Q−1 denotes the modular inverse of Q modulo 163577857. (It is guaranteed that this inverse exists and is unique.)
Consider a sequence of integers a1,a2,…,ah; let's denote s=∑hi=1ai. For each i (1≤i≤h), the probability that Cheftanya directs Chef to look at units i,i+1,…,i+x−1 is ai/s; the units are cyclic, so we can consider "unit i" to be equivalent to "unit i−h". Since the sequence a can be very large, you are only given its first K elements. You are also given a sequence c1,c2,…,cK; the remainder of sequence a can be generated using the formula ai=∑j=1Kcj⋅ai−j∀i:K
Constraints 1≤pi≤h for each valid i 1≤x,K≤h 0≤ai≤109 for each valid i 0≤ci≤109 for each valid i Subtasks Subtask #1 (5 points):
1≤N≤1,000 1≤h≤10,000 1≤K≤10 Subtask #2 (10 points):
1≤N≤50,000 1≤h≤106 1≤K≤10 Subtask #3 (30 points):
1≤N≤100 1≤h≤109 1≤K≤100 Subtask #4 (55 points):
1≤N≤2,000 1≤h≤109 1≤K≤100 Example Input 3 5 3 2 1 3 5 1 1 1 1 Example Output 13631490 Explanation The complete sequence a is equal to {1,1,2,3,5} and s=∑ai=1+1+2+3+5=12. Chef looks at the range starting with unit 1 with probability a1/s=1/12, at the range starting with unit 3 with probability a3/s=1/6, and so on. The expected number of buildings he shoots is therefore equal to 112⋅2+112⋅1+212⋅2+312⋅2+512⋅2=2312=23⋅12−1=13631490.
I have got the expectation but by which number i should multiply each probability.
You need to multiply the expectation with the number of buildings that are present in the given range of units.
In the example given, value of p1,p2,p3 are 1,3 and 5 that means their are three buildings with position unit number 1,3 and 5 respectively.
So,when you calculate the expectation of shooting in a particular range you need to multiply that expectation with the number of buildings present in that range of vision which will give the probability of how many buildings will be hit in particular range.
In the first expectation i.e, 1/12 first find the number of buildings in the range of units 1-3 because range (x) is given as 3,which is 2 one at unit 1 and other at 3 so multiply them.Similarly for other expectations,and as given for units greater than h find the number of building after taking modulo h.
Update: For the next expectation 1/12 consider the unit 2-4 in these units there is only 1 building in the unit number 3,hence multiply 1/12 with 1.
For the third expectation 2/12 consider 3-5,in these units there are two building in units 3 & 5.