Lasketaan n-pituisesta H,T-jonosta kuinka monta kertaa siinä esiintyy HH, HT, TH ja TT. Siis katsotaan kaikkia kahden peräkkäisen merkin palasia (näitä on n-1). Esim jonossa
HTTHHHTHT
määrät ovat:
HH: 2, HT: 3, TH: 2, TT: 1
Merkitään f(a,b,c,d):llä niiden H,T-jonojen lukumäärää joissa määrät ovat HH: a, HT:b, TH: c, TT: d. Laske
f(8, 5, 4, 2)
f(29, 24, 25, 21)
f(276, 249, 250, 224) (Ilmoita vastaus modulo M = 10^9 + 7)
Määritellään sitten g(n, a) niiden n:n pituisten H,T-jonojen lukumäärää, joissa esiintyy a kappaletta HH:ta. Laske mod M
g(24, 12)
g(100, 34)
g(10^100, 13)
Binäärijonon kahden peräkkäisen lukumäärät
Anonyymi-ap
3
234
Vastaukset 3
- Anonyymi
Kysy TVH:lta! Ne tietää. Tuskinpa muita kiinnostaa.
- Anonyymi
Vastaus:
f(a,b,c,d) =
[b=c➕1]( (a➕b-1) C a * (c➕d)Cd ➕ [b=c] (a➕b) C a * (c➕d-1)Cd ➕ (a➕b-1) C a * (c➕d-1)Cd )) ➕ [b=c-1] ((a➕b-1) C a * (c➕d-1)Cd ))
Eli riippuen siitä onko b=c tai c -1, niin otetaan pienillä muutoksilla kahden binomikertoimen tulon summa. Kaipa tuon voisi kirjoittaa lyhyemminkin muodostamalla binomikertoimen sisäosat Iversonin sulkeella [b=?].
Toinen kohta:
g(n, a) = [z^a] sum (([[1,z], [z,z]])^n)[0]
(tässä hakasulje tarkoittaa kertoimen ottoa)
Laskenta kannattaa tehdä modulo z^(a 1) ja tietenkin jo lähtöjään polynomi Z/ZM -kertoiminen kun tuossa modulossa lasketaan.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 641032
- 621024
- 93817
- 57803
- 42668
Jasmin vauhdissa
Kyllä pitää Jassulla kiirettä, kun yhtenään menoa mun äidin, isäpuolen ja Markon kanssa Ossianin ollessa tietysti sulois222630- 50588
- 40570
- 66565
Nainen joka haluaa miehen
Näyttää sen selvästi. Hommaa minihameet, pitkät hiukset, laihduttaa ja on iloinen sekä aktiivinen.79553