Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
A. Фибоначчи
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Фибоначчи-ийн дараалал гэдэг нь рекурсив хамаарлаар тодорхойлогдох бүхэл тооны рекурсив дараалал юм.
$F_{n} = s_{n - 1}*F_{n - 1} + s_{n - 2}*F_{n - 2}$ ба $F_{0} = 0, F_{1} = 1$
$s$ дараалал нь хязгааргүй бөгөөд $N$ урттай цикл бүхий бараг цикл-лэг дараалал юм. Хэрэв ($i ≥ N$) байх хязгаартай тооны $s_{i}$-ын утгыг тооцохгүйгээр $i ≥ N$ бүрийн хувьд
байвал $s$ дарааллыг $N$ урттай цикл бүхий бараг цикл-лэг дараалал гэж нэрлэнэ.
Дараах жишээ нь 4 урттай цикл бүхий бараг цикл-лэг дараалал байна:
s = (5,3,8,11,5,3,7,11,5,3,8,11,…)
тэнцэтгэлийг хангахгүй байгаа $s$-ын цорын ганц утга нь $s_{6}$ ($s_{6} = 7$ болон $s_{2} = 8$) болохыг анхаарна уу. Танд $s_{0}, s_{1}, ...s_{N - 1}$ болон
($i ≥ N$) байх бүх $s$ дарааллын утгууд өгөгдөнө.
-г олно уу.
Оролт
Эхний мөрөнд 2 тоо $K$ болон $P$ өгөгдөнө. 2-дахь мөрөнд ганц тоо $N$ өгөгдөнө. 3-дахь мөрөнд зайгаар тусгаарлагдсан $N$ ширхэг тоо өгөгдөнө, эдгээр нь $s$ дарааллын эхний $N$ тоог илэрхийлнэ. 4-дэх мөрөнд ганц тоо $M$ өгөгдөх ба энэ нь $s$ дарааллын байх утгуудын тоог илэрхийлнэ. Дараагийн $M$ мөрийн мөр болгонд 2 тоо $j$ болон $v$ өгөгдөх ба эдгээр нь
болон $s_{j} = v$ болохыг зааж байгаа юм. Бүх j-нууд нь ялгаатай байна.
- $1 ≤ N, M ≤ 50000$
- $0 ≤ K ≤ 10^{18}$
- $1 ≤ P ≤ 10^{9}$
- $1 ≤ s_{i} ≤ 10^{9}$, бүх $i = 0, 1, ...N - 1$ -ын хувьд
- $N ≤ j ≤ 10^{18}$
- $1 ≤ v ≤ 10^{9}$
- Бүх утгууд нь бүхэл тоо байна
Гаралт
-тай тэнцүү байх ганц бүхэл тоог хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
10 8 3 1 2 1 2 7 3 5 4
Гаралт
4