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

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

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Note: I used $$$n$$$ and $$$k$$$ for $$$a$$$ and $$$b$$$ respectively. I also assumed based on the example that the array starts out with all zeroes.

If $$$A(n,k)$$$ is the answer for the input $$$n,k$$$,

$$$A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$$$

where

$$$E_2(n) = \frac{(n+1)(n+2)}{6} \text{ and } E_1(n) = \frac{n+2}{3}.$$$

In an operation, a subarray of length $l$ is chosen from an array of size $$$n$$$. $$$E_1(n)$$$ denotes the expected value of $$$l$$$ and $$$E_2(n)$$$ denotes the expected value of $$$l^2$$$.

Claim: $$$A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$$$

Proof:

Claim: $$$E_1(n) = \frac{n+2}{3}$$$

Proof:

Claim: $$$E_2(n) = \frac{(n+1)(n+2)}{6}$$$

Proof:
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Thank you so much.

    You have explained it so well here.

    Could you suggest some similiar problems or articles where I could practice?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      Here are two tutorials by Errichto that I found pretty helpful, Part 1 and Part 2. They also have problems to help practice the techniques.

      Some problems that I can remember off the top of my head that use expected value are these:

      GR 10 HThis solution in my opinion is more intuitive and easier to understand than the official one.

      Merge CardsO(n) solution by Errichto

      Edu 57 F

      There are also some nice resources out there like this one that aren't all expected value problems but in my opinion, help to build an intuitiveness that can help solve expected value problems.