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
175
Vastaukset
- 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
Sannan kirja USA:n bestseller!
"Congratulations to Sanna Marin's HOPE IN ACTION, officially a USA TODAY bestseller!" Kertoo Scribner. Mitäs persut tä15111406- 288102
Metsäalan rikolliset
Jokohan alkaa vähitellen kaatua kulissit näillä ihmiskauppaa harjoittavilla firmoilla.565874Ruotsalaistoimittaja: "Sanna Marinin saunominen saa minut häpeämään"
Sanna Marinin kirja saa täyslaidallisen ruotsalaislehti Expressenissä perjantaina julkaistussa kolumnissa.....voi itku..1624749- 154671
Suomen kaksikielisyys - täyttä huuhaata
Eivätkö muuten yksilöt pysty arvioimaan mitä kieliä he tarvitsevat? Ulkomaalaiselle osaajalle riittää Suomessa kielitai324331Työeläkeloisinta 27,5 mrd. per vuosi
Tuo kaikki on pois palkansaajien ostovoimasta. Ja sitten puupäät ihmettelee miksei Suomen talous kasva. No eihän se kas844193- 843487
- 803240
- 481741