Help in Expected Value Problem

Правка en1, от nick_301, 2021-02-18 14:43:35

There is a array of length A. We have to perform B operations. In each operation, we can select a subarray of any length and increase all its elements by 1. All subarrays are equiprobable. Find the expected value of the square of the sum of elements. (mod 1e9+7)

Constraints:

1<=A,B<=1e9

Sample Input 1:

A=2

B=2

There are 9 different order of operations.

  1. (0,0) + (1,1) = 2

  2. (0,0) + (0,0) = 2

  3. (1,1) + (0,0) = 2

  4. (1,1) + (1,1) = 2

  5. (0,1) + (0,0) = 3

  6. (0,1) + (1,1) = 3

  7. (0,0) + (0,1) = 3

  8. (1,1) + (0,1) = 3

  9. (0,1) + (0,1) = 4

Expected Value= [4*(2^2) + 4*(3^2) + (4^2)]/9 = 68/9 (mod 1e9+7) = 555555567

How do I approach this problem?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский nick_301 2021-02-18 14:43:35 745 Initial revision (published)