F. Баавгай ба Жүүс

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нийтдээ $n$ ширхэг баавгай буудалд байрлах бөгөөд тус буудалд $p$ ширхэг унтах газар байв. Баавгай нар нь хамтдаа хэдэн шөнө (мөн өдөр) шоудхаар болжээ.

Баавгайнууд жүүс уух дуртай байв. Тэд дарс уух дургүй боловч дарсыг жүүснээс амт болон үнэрээр нь ялгаж чаддаггүй байжээ.

Хэрэв ямар нэгэн баавгай дарс уугаагүй л бол тэрээр унтахгүй байх ажээ. Баавгай нь дарс ууснаас хойш хэдхэн цагийн дараа заавал явж унтдаг байв. Тэрээр уг шоудалт дууссанаас хойш маш олон өдрийн дараа сэрэх юм.

Рэйдвүүш уг буудлын эзэн бөгөөд тэрээр хэсэг тооны торхнуудыг баавгайнуудын өмнө байрлуулахыг хүсжээ. Нэг торх нь дарс агуулах бөгөөд бусад бүх торхнууд нь жүүс агуулж байв. Рэйдвүүш эдгээр баавгайнуудтай дарс агуулах торхыг олох тоглоом тоглохоор болжээ.

Шөнө болгон дараах зүйлс яг дарааллын дагуу болж өнгөрнө:

  1. Баавгай болгон нь нэг ширхэг торхнуудын олонлог(хоосон олонлог байж болно) сонгоно. Ижил торх нь олон тооны баавгайнуудаар сонгогдож болохыг анхаарна уу.
  2. Баавгай болгон нь өөрийн сонгосон олонлогт байх торх болгоноос нэг хундагыг ууна.
  3. Дарс уусан бүх баавгайнууд нь унтахаар явна. Өөрөөр хэлбэл дарстай торхыг сонгосон бүх баавгайнууд нь унтахаар явах юм. Тэд уг шоудалт дууссанаас хойш маш олон өдрийн дараа сэрэх бөгөөд хэрэв баавгайнуудад унтах хангалттай олон тооны унтах газах байхгүй бол баавгай нар тоглоомд ялагдах юм.

Төгсгөлд нь хэрэв баавгай нар дарс яг хаана байгааг мэдэх бөгөөд ядаж нэг ширхэг баавгай сэрүүн байвал баавгайнууд тоглоомд ялах юм. Үгүй бол тэд нар унтах газрын тооноос болж ялагдахаас өмнө тоглоомд ялагдах ажээ.

Рэйдвүүш баавгай нар тоглоомд ялахыг зөвшөөрчээ. Тэрээр $q$ ширхэг тохиолдол авч үзэх бөгөөд эдгээрийн $i$-дахь тохиолдолд шоудалт нь $i$ шөнө үргэлжилнэ гэж үзэх юм. Дараа нь бид $R_{i}$-аар $i$-дахь тохиолдолд хэрэв баавгайнууд нь ухаалаг байдлаар тогловол тэдний баттай ялах тоглоомын нийт торхны боломжит хамгийн их утгыг тэмдэглэе. Мөн гэж тэмдэглэе. Тэгвэл таны даалгавар -ыг олох бөгөөд энд нь тусгай or үйлдэл буюу XOR үйлдлийг илэрхийлнэ.

Ижил торх нь олон тооны баавгайнуудаар сонгогдсон байж болох бөгөөд эдгээр бүх баавгайнууд нь шуудхан л унтдаг гэж үзнэ үү.

Оролт

Оролтын цорын ганц бөгөөд эхний мөрөнд 3-н бүхэл тоо $n$, $p$ болон $q$ ($1 ≤ n ≤ 10^{9}$, $1 ≤ p ≤ 130$, $1 ≤ q ≤ 2 000 000$) өгөгдөх ба эдгээр нь харгалзан баавгайнуудын тоо, унтах газрын тоо болон нийт тохиолдлын тоог тус тус илэрхийлнэ.

Гаралт

-тай тэнцүү байх ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5 1 3
Гаралт
32
Оролт
1 100 4
Гаралт
4
Оролт
3 2 1
Гаралт
7
Оролт
100 100 100
Гаралт
381863924

Тэмдэглэл

Эхний жишээнд нийт $5$ ширхэг баавгай байх бөгөөд зөвхөн $1$ ширхэг унтах газар байх юм. $R_{1} = 6, R_{2} = 11, R_{3} = 16$ байх бөгөөд ингэснээр хариулт нь болох юм. $2$ өдөр үргэлжлэх тохиолдлын оновчтой стратегийг авч үзье. $R_{2} = 11$ ширхэг торх байх бөгөөд эдгээрийн $10$ ширхэг нь жүүс агуулсан байна.

  • Эхний шөнө $i$-дахь баавгай нь зөвхөн $i$-р торхыг сонгоно.
    • Хэрэв эхний $5$-н торхны аль нэг нь дарс агуулсан байвал ямар нэгэн баавгай унтахаар явах юм. Одоо тэд дарсыг хаана байгааг мэдэж байгаа бөгөөд дор хаяж нэг ширхэг баавгай сэрүүн байх учир баавгай нар тоглоомд ялна.
    • Эхний $5$-н торхны аль нь ч дарс агуулаагүй байна гэж үзье. 2-дахь шөнө $i$-дахь баавгай нь $5 + i$-р торхыг сонгоно.
      • Хэрэв $6 - 10$-р хүртэлх торхнуудын аль нэг нь дарс агуулсан байвал нэг баавгай нь унтахаар явах бөгөөд өмнөх шөнөтэй адилаар баавгай нар тоглоомд ялна.
      • Хэрэв хэн ч унтахаар явахгүй бол дарс нь $11$-р торхонд байна.

2-дахь жишээнд зөвхөн нэг ширхэг баавгай байна. Тэрээр шөнө болгон хоосон олонлог сонгох ёстой бөгөөд эс бөгөөс тэрээр магадгүй дарс уух ба ингэснээр баавгай нар тоглоомд ялагдах юм(учир нь дор хаяж нэг ширхэг баавгай сэрүүн байх ёстой). Иймд шоудалт хэдэн ч өдөр үргэлжилсэн бай $R_{i} = 1$ байна. Ингэснээр хариулт нь болно.

Сэтгэгдлүүдийг ачааллаж байна...