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
115
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
Ensitreffit Jenni laukoo viinilasin ääressä suorat sanat Jyrkin aikeista: "Mä sanoin, että älä"
Voi ei… Mitä luulet: kestääkö Jennin ja Jyrkin avioliitto vai päättyykö eroon? Lue lisää: https://www.suomi24.fi/viihde192460- 1482214
Ymmärrän paremmin kuin koskaan
Roikut kädessäni ja vedät puoleesi. Näen kuitenkin tämän kaiken lävitse ja kaikkien takia minun on tehtävä tämä. Päästän292132Hullu liikenteessä?
Mikä hullu pyörii kylillä jos jahti päällä? Näitä tosin kyllä riittää tällä kylällä.522109Niina Lahtinen uudessa elämäntilanteessa - Kotiolot ovat muuttuneet merkittävästi: "Nyt on...!"
Niina, tanssejasi on riemukasta seurata, iso kiitos! Lue Niinan haastattelu: https://www.suomi24.fi/viihde/niina-lahti201674Kun Venäjä on tasannut tilit Ukrainan kanssa, onko Suomi seuraava?
Mitä mieltä olette, onko Suomi seuraava, jonka kanssa Venäjä tasaa tilit? Ja voisiko sitä mitenkään estää? Esimerkiks3871583Ano Turtiainen saa syytteet kansankiihoituksesta
Syytteitä on kolme ja niissä on kyse kirjoituksista, jotka hän on kansanedustaja-aikanaan julkaissut Twitter-tilillään961506- 2771388
Varokaa! Lunta voi sataa kohta!
Vakava säävaroitus Lumisadevaroitus Satakunta, Uusimaa, Etelä-Karjala, Keski-Suomi, Etelä-Savo, Etelä-Pohjanmaa, Pohjanm131369- 1301346