Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя nick_301

Автор nick_301, история, 3 года назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится