Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
E. DZY гүүрэнд дуртай
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
DZY гэрийнхээ ойролцоо $2^{m}$ арал эзэмшдэг ба эдгээр нь $1$-с $2^{m}$ хүртэл дугаарлагдсан. Тэр арлуудыг холбосон гүүр барих дуртай. Түүний барьсан гүүр бүрийг алхаж гарахад нэг өдрийн хугацаа шаардана.
DZY гүүр барих хачирхалтай дүрэмтэй. $u, v (u ≠ v)$ хос арал бүрийн хувьд тэр тэдгээрийг холбосон ялгаатай $2^{k}$ гүүр барьсан ба энд ($a|b$ нь $b$ тоо $a$-д хуваагддаг гэсэн үг). Гүүрүүд хос чиглэлтэй.
Мөн DZY өөрийн гэрийг арлуудтай холбосон хэдэн гүүр барьсан. Тухайлбал түүний гэрээс $i$-р арал хүртэл ялгаатай $a_{i}$ гүүр байгаа. Эдгээр нь нэг чиглэлтэй гүүр ба тэр гэрээ орхисоны дараа хэзээ ч эргэж ирэхгүй.
DZY үзэсгэлэнтэй газруудыг тойрч үзэхээр арлуудруугаа явахаар шийдсэн. Эхлээд тэр гэртээ байх ба түүний гэртэй холбогдсон нэг гүүрээр нэг арал дээр очно. Үүний дараа тэр арлууд дээр $t$ өдрийг өнгөрүүлнэ. Өдөр бүр тэр уг арал дээр үлдэж амрах эсвэл өөр аралруу гүүрээр дамжин явахаа сонгож чадна. Арал дээр нэгээс олон өдөр амарч болно. Нэг гүүрээр хэдэн удаа ч давж болно.
Яг $i$-р өдрийн дараа DZY $i$-р арал дээр байна гэж бодьё. $i$-р өдрийн дараа DZY $i$-р арал дээр хүрэх замуудын тоог $ans[i]$ гэе. Таны ажил бол $i$ бүрийн хувьд $ans[i]$ тоог тооцоолоод $1051131$ тоонд хуваагаад үлдэгдлийг авах юм.
Оролт
Маш их хэмжээтэй оролтоос сэргийлж бид $a$ массивыг үүсгэх дараах аргыг хэрэглэнэ. Танд массивын эхний $s$ элемент өгөгдөнө: $a_{1}, a_{2}, ..., a_{s}$. Бусад бүх элементүүд томьёогоор тооцоологдох ёстой: $a_{i} = (101*a_{i - s} + 10007) mod 1051131$ $(s < i ≤ 2^{m})$.
Эхний мөрөнд гурван бүхэл тоон утга $m, t, s$ $(1 ≤ m ≤ 25; 1 ≤ t ≤ 10^{18}; 1 ≤ s ≤ min(2^{m}, 10^{5}))$ байна.
Хоёр дахь мөрөнд $s$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{s} (1 ≤ a_{i} ≤ 10^{6})$ байна.
Гаралт
Маш их хэмжээтэй гаралтаас сэргийлж бүх $i$-н хувьд хариултуудыг $1051131$ тоонд хуваагаад үлдэгдлүүдийн xor-нийлбэрийг хэвлэнэ $(1 ≤ i ≤ 2^{m})$. Өөрөөр $(ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131)$.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
2 1 4 1 1 1 2
Гаралт
1
Оролт
3 5 6 389094 705719 547193 653800 947499 17024
Гаралт
556970
Тэмдэглэл
Эхний жишээн дээр $ans = [6, 7, 6, 6]$.
Хэрвээ тэр нэг өдрийн дараа 1-р арал дээр байхыг үсвэл түүнд ялгаатай зургаан зам байна:
- гэр --> 1 -(үлдэх)-> 1
- гэр --> 2 --> 1
- гэр --> 3 --> 1
- гэр --> 3 --> 1 (1 ба 3-н хооронд хоёр ялгаатай гүүр байгаа)
- гэр --> 4 --> 1
- гэр --> 4 --> 1 (гэр ба 4-н хооронд хоёр ялгаатай гүүр байгаа)
Хоёр дахь жишээн дээр $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849)$, $ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335]$.