Монгол хэлээр
In English
По-Русски
Сайтын тухай
Тэмцээнүүд
Бодлогууд
Чансаа
Орчуулгын саналууд (211)
mn/86-E
com/86-E
Хадгалах
Fullscreen
# Урт дараалал Хэрэв $a\_{i}$ $(i = 0, 1, ...)$ томъёо тус бүр нь 0 юм уу 1-тэй тэнцүү бол, мөн $n ≥ k$ бүрт  болон $a\_{n} = c\_{1}\*a\_{n - 1} + c\_{2}\*a\_{n - 2} + ... + c\_{k}\*a\_{n - k} (mod 2), $ гэсэн коэффициентууд байдаг бол $a_{0}, a\_{1}, ...$ гэсэн дарааллыг хоёртын рекурент дараалал гэнэ. $c\_{i}$ бүр нь бүгд нэгэн зэрэг $0$ биш гэдгийг санаарай. Энэ мэтийн дарааллыг $k$-хослол ${a\_{s}, a\_{s + 1}, ..., a\_{s + k - 1}}$-ээс ховорхон харж болох ба энэ нь үе үе давтамжтай. Түүнчлэн хэрэв $k$-хослол нь зөвхөн 0 агуулж байвал тус дараалал тэр чигээрээ зөвхөн 0-ийг агуулах учир энэ нь тийм ч сонирхолтой бус байна. Үгүй бол дарааллын хамгийн бага давтамж нь $2^{k} - 1$-ээс бага байх ба $2^{k} - 1$ гэсэн тэгээс ялгаатай $k$-хослол байна. Хэрэв хамгийн бага давтамж нь яг $2^{k} - 1$ байвал урт дараалал гэж үзье. Та өгөгдсөн $k$-д урт дараалал байгаа эсэхийн олоорой. ## Оролт Оролт нь $k$ ($2 ≤ k ≤ 50$) гэсэн ганц бүхэл тоо агуулна. ## Гаралт Хэрэв тийм урт дараалал байхгүй бол -1 гэж хэвлэ. Үгүй бол гаралтын эхний мөр нь $c\_{1}, c\_{2}, ..., c\_{k}$ коэффициенттой $k$ бүхэл тоо агуулсан байна. Хоёр дахь мөр нь $a\_{0}, a\_{1}, ..., a\_{k - 1}$ дарааллын $k$ гэсэн анхны элементүүд агуулсан байна. Бүх элементүүд, коэффициентууд нь 0 юм уу 1-тэй тэнцүү мөн дор хаяж нэг $c_{i}$ нь 1-тэй тэнцүү байна. Хэрэв хэд хэдэн зөв хариу байвал нэгийг хэвлэнэ үү. ## Тэмдэглэл 1\. Эхний жишээнд: $c\_{1} = 1$, $c\_{2} = 1$, so $a\_{n} = a\_{n - 1} + a\_{n - 2} (mod 2)$. Иймээс дараалал нь:  Тиймээс үүний давтамж нь $3 = 2^{2} - 1$-тай тэнцүү байна. 2\. Хоёр дахь жишээнд: $c\_{1} = 0$, $c\_{2} = 1$, $c\_{3} = 1$, so $a\_{n} = a\_{n - 2} + a\_{n - 3} (mod 2)$. Тиймээс бидний дараалал:  Үүний давтамж нь $7 = 2^{3} - 1$-тэй тэнцүү байна. Давтамжийг өнгөөр будсан байна. -- Энхгэрэл
Жишээ тэстүүд
Оролт
2
Гаралт
1 1 1 0
Оролт
3
Гаралт
0 1 1 1 1 1
Тэмдэглэл