Fişierul intrare/ieşire:expected3.in, expected3.outSursăFMI No Stress 10
AutorAlexandra UdristoiuAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Expected3

După ce ai primit cadou de Crăciun o cutie cu N bile verzi, M bile roşii şi o bilă neagră, te-ai gândit la următorul joc: la fiecare pas extragi cu probabilitate egală una dintre bilele din cutie.

  • dacă bila este verde, vei câştiga A puncte
  • dacă bila este roşie, vei pierde B puncte
  • dacă bila este neagră, jocul se termină

După ce ai extras o bilă, aceasta nu va mai fi pusă înapoi în cutie. Care este valoarea medie (expected value) a numărului de puncte pe care l-ai obţine?

Se poate demonstra că răspunsul se scrie sub forma unei fracţii ireductibile P/Q, unde gcd(Q, 1 000 000 007) = 1. În acest caz, va trebui să afişaţi numărul P * Q-1 modulo 1 000 000 007.

Date de intrare

Fişierul de intrare expected3.in conţine pe o singură linie 4 numere naturale N, M, A, B, cu semnificaţia de mai sus.

Date de ieşire

În fişierul de ieşire expected3.out se va afişa un singur număr de forma P * Q-1 modulo 1 000 000 007, unde Q-1 reprezintă inversul modular al lui Q faţă de 1 000 000 007.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • 1 ≤ A, B ≤ 1 000 000 000
  • Pentru 40 de puncte, 1 ≤ N, M ≤ 1000
  • Pentru alte 20 de puncte, 1 ≤ N, M ≤ 3000

Exemplu

expected3.inexpected3.out
1 1 3 1
1
5 3 3 4
500000005
10000 10000 90000 70000
100000000

Explicaţie

Pentru primul exemplu, se pot extrage bilele astfel:

  • N (0 puncte), cu probabilitate de 1/3
  • VN (3 puncte), cu probabilitate de 1/6
  • RN (-1 puncte), cu probabilitate de 1/6
  • VRN (2 puncte), cu probabilitate de 1/6
  • RVN (2 puncte), cu probabilitate de 1/6

Expected value este  \frac{0}{3} + \frac{3}{6} + \frac{-1}{6} + \frac{2}{6} + \frac{2}{6} = 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?