Codeforces Round #793 (Div. 2)
21:50:18 |
Educational Codeforces Round 129 (Rated for Div. 2)
21:50:18 |
Codeforces Round #794 (Div. 1)
4 өдрийн дараа |
Codeforces Round #794 (Div. 2)
4 өдрийн дараа |
E. Xor-дарааллууд
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$-ууд өгөгдөв.
Бүхэл тоонуудын дараалал $x_{1}, x_{2}, ..., x_{k}$-ын хувьд хэрэв $1 ≤ i ≤ k - 1$ бүрийн хувьд $x_{i}$ тооны 2-тын бичлэг доторх 1-ийн тоо $x_{i + 1}$ тооны 2-тын бичлэг доторх 1-ийн тоо гэсэн утга нь $3$-т хуваагдах бөгөөд бүх $1 ≤ i ≤ k$ -ын хувьд
байвал уг дарааллыг "xor-дараалал" хэмээн нэрлэх ажээ.
гэсэн тэмдэг нь 2-тын тооллын систем дэх or үйлдлийг илэрхийлнэ.
Тэгвэл $k$ урттай хэчнээн ширхэг "xor-дараалал" оршин байгаа вэ? Бодлогын хариултыг $10^{9} + 7$ модулаар бодож хэвлэнэ үү.
Хэрэв $a = [1, 1]$ ба $k = 1$ байвал бодлогын хариулт нь $2$ байхыг анхаарна уу. Учир нь та $a$ дотор байгаа 1-үүдийг ялгаатай гэж үзэх ёстой юм.
Оролт
Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 100$, $1 ≤ k ≤ 10^{18}$) өгөгдөх ба эдгээр нь танд өгөгдөх бүхэл тоонуудын тоо болон "xor-дараалал"-уудын уртыг илэрхийлнэ.
2-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{i}$ ($0 ≤ a_{i} ≤ 10^{18}$)-ууд өгөгдөнө.
Гаралт
$k$ урттай "xor-дараалал"-уудын тоог $10^{9} + 7$ модулаар бодсон утга болох ганц бүхэл тоо $c$-г хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
5 2 15 1 2 4 8
Гаралт
13
Оролт
5 1 15 1 2 4 8
Гаралт
5