Codeforces Round #716 (Div. 2)
03:19:13 |
Codeforces Round #717 (Div. 2)
2 өдрийн дараа |
Codeforces Round #718 (Div. 1)
4 өдрийн дараа |
Codeforces Round #718 (Div. 2)
4 өдрийн дараа |
Codeforces Global Round 14
13 өдрийн дараа |
H. Фибоначчи-иш II
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Яаш эцэст нь хамгийн урт Фибоначчи-иш дарааллын уртыг тооцохоос залхжээ.Тэрээр одоо илүү төвөгтэй зүйл сонирхож байгаа бөгөөд тухайлбал Фибоначчи-иш чадлын талаар сонирхож байгаа юм.
$a_{i}$ цувааны Фибоначчи-иш чадал гэдэг нь дараах байдлаар бодогдоно:
- Хэрэв $a_{i} = a_{j}$ байх $i < j$-ууд оршин байвал бүх $j$ элементүүдийг цуваанаас хасна.
- Тэгээд үлдсэн элементүүдийг өсөх дарааллаар байрлуулна, өөрөөр хэлбэл $a_{1} < a_{2} < ... < a_{n}$.
- Чадлыг бодохдоо $P(a) = a_{1}*F_{1} + a_{2}*F_{2} + ... + a_{n}*F_{n}$ томьёогоор бодох ба энд $F_{i}$-аар $i$-дахь Фибоначчийн тоог тэмдэглэв(тодруулах үүднээс тэмдэглэлийг үзнэ үү).
Танд $n$ урт бүхий $a_{i}$ цуваа болон $l_{j}$-аас $r_{j}$-ын хооронд байх $q$ ширхэг завсар өгөгдөнө.$j$ завсар бүрийн хувьд та $a_{i}$-ын $l_{j}$-аас $r_{j}$-ын хооронд байх элементүүдийг дээрх зааврын дагуу хассан цуваа болох $b_{i}$-ын Фибоначчи-иш чадлыг олох юм.Тус утгыг $m$ модул-аар бодож олно уу.
Оролт
Эхний мөрөнд харгалзан анхны цувааны урт болон модул-ыг илэрхийлэх бүхэл тоонууд $n$ болон $m$ ($1 ≤ n, m ≤ 30 000$) өгөгдөнө.
Дараагийн мөрөнд цувааны элементүүд болох $n$ ширхэг бүхэл тоонууд $a_{i}$ ($0 ≤ a_{i} ≤ 10^{9}$) өгөгдөнө.
Дараа нь завсрын тоо болох $q$ ($1 ≤ q ≤ 30 000$) өгөгдөнө.
Сүүлийн $q$ ширхэг мөрөнд Фибоначчи-иш чадлыг нь олох ёстой завсруудыг илэрхийлэх хос бүхэл тоо $l_{i}$ болон $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө.
Гаралт
$q$ ширхэг мөрөнд хэвлэх ба $i$-дахь мөрөнд $i$-дахь завсрын Фибоначчи-иш чадлыг $m$ модул-аар бодсон утгыг хэвлэнэ.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
5 10 2 1 2 1 2 2 2 4 4 5
Гаралт
3 3
Тэмдэглэл
Фибоначчийн тоонууд гэдэг нь дараах байдлаар тодорхойлогдоно:
- $F_{1} = F_{2} = 1$.
- Бүх $n > 2$-ын хувьд $F_{n} = F_{n - 1} + F_{n - 2}$ байна.
Эхний даалгавар дээр, дэд цуваа [1,2,1] нь үйлдлийн дагуу {1,2} цуваа болно. Түүнчлэн, энэ дэд цувааны чадал нь 1*1+2*1=3 байна.