Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Урт дараалал
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Хэрэв $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-тэй тэнцүү байна. Хэрэв хэд хэдэн зөв хариу байвал нэгийг хэвлэнэ үү.
Орчуулсан: Энхгэрэл
Жишээ тэстүүд
Оролт
2
Гаралт
1 1 1 0
Оролт
3
Гаралт
0 1 1 1 1 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$-тэй тэнцүү байна.
Давтамжийг өнгөөр будсан байна.