nick_301's blog

By nick_301, history, 4 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it