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
150
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
- 903265
- 883043
- 681872
Tykkään susta
Elämäni loppuun asti. Olet niin suuresti siihen vaikuttanut. Tykkäsit tai et siitä191842- 301767
- 211701
- 241687
Pettymys! Tähdet, tähdet -kisassa tämä erikoisjakso pois - Pistänyt artistit todella lujille!
Tähdet, tähdet -kisa on edennyt genrestä toiseen. Mutta erästä monen toivomaa erikoisjaksoa ei tällä kaudella nähdä. Voi341379- 481327
Onko meillä
Molemmilla nyt hyvät fiilikset😢ei ainakaan mulla mutta eteenpäin on mentävä😏ikävä on, kait se helpottaa ajan myötä. Ko91319