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
218
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
Riikka runnoo: datakeskuksille tulee UUSI yritystuki
"Suomen valtio erikseen tukee esimerkiksi kryptovaluuttaan tai aikuisviihteeseen tai muuhun keskittyviä datakeskuksia."672297Eläkeläiset siirrettävä muuttotappioalueille
Joutoväki pois ruuhkauttamasta elättäjien arkea. Samalla putoaa jokaisen asumiskulut ja rahaa jää enemmän kuluttamiseen.2282210- 1201498
Jopa Espanjassa talous kasvaa, Purra vain irvistelee
Huomaa kuinka Purra on Suomen historian huonoin miniseteri, joka ei ole saanut aikaiseksi kuin tuhoa, Siis jopa vasemmis231308Kauppalehti - Törkeä skandaali paljastui: Espanja käytti EU-rahoja ihan muuhun kuin piti
Espanja on käyttänyt miljardeja euroja EU:n elpymisavustuksia eläkkeisiin ja sosiaalimenoihin – ja pyytää lisää. Espanj211252En kerro nimeäsi nainen
Sillä olet nyt salaisuus jota kannan sydämessäni. Tämä mitä tunnen ja kuinka sinuun vahvasti ihastuin on jo niin erikoin711210- 1241208
Olet kiva ihminen
En kiellä sitä yhtään. Sinussa on hyvin paljon erinomaisia puolia, enemmän varmasti kun meissä muissa. Sitten on puoli73969Uuden upotuskasteen vaiettu ongelma
Alkuseurakunnan kaste oli useamman vuosisadan upotuskaste, joka toimitettiin joko ulkona luonnon vesistöissä tai kasteki102969Auta mua mies
Ota vielä yhteyttä, keksi oikeat sanat että vuosien ajan kasvanut muuri murtuu meidän väliltä vaikka aluksi vain vähän.77922