Codeforces Round #804 (Div. 2)
23:31:20 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
B. Алимхүү ба Мод
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Алимхүүд $n$ оройтой мод байв. Зарим орой нь (ядаж нэг) хар ѳнгѳтэй ба үлдсэн нь цагаан ѳнгѳтэй байлаа.
Алимхүүгийн модноос $k$ $(0 ≤ k < n)$ ирмэгийг агуулсан олонлогийг авч үзье. Хэрвээ Алимхүү эдгээр ирмэгийг устгавал мод $(k + 1)$ хэсэгт хуваагдна. Хэсэг бүр нь ѳнгѳт мод байхыг тэмдэглэе.
Одоо Алимхүү хэсэг бүр нь яг нэг хар орой агуулсан байхаар хуваадаг олонлогуудын тоог олохыг хүсч байна. Энэ тоог $1000000007$ ($10^{9} + 7$) тоонд хуваахад гарах үлдэгдлийг олно уу.
Оролт
Эхний мѳр модны оройн тоо $n$-г ($2 ≤ n ≤ 10^{5}$) агуулна.
Хоёрдугаар мѳр модыг илэрхийлнэ: $n - 1$ ширхэг бүхэл тоо $p_{0}, p_{1}, ..., p_{n - 2}$ ($0 ≤ p_{i} ≤ i$) агуулна. Энд $p_{i}$ нь $(i + 1)$ орой $p_{i}$ оройтой холбогдсоныг илтгэнэ. Модны оройнуудыг $0$-ээс $n - 1$ хүртэл дугаарлагдсан гэж үзье.
Гуравдугаар мѳр оройнуудын ѳнгийг илэрхийлнэ: $n$ ширхэг бүхэл тоо $x_{0}, x_{1}, ..., x_{n - 1}$ ($x_{i}$ нь $0$ юмуу $1$) агуулна. Хэрвээ $x_{i}$ $1$-тэй тэнцүү бол $i$ орой хар ѳнгѳтэй. Эсрэг тохиолдолд цагаан ѳнгѳтэй байна.
Гаралт
Боломжийн тоог $1000000007$-д ($10^{9} + 7$) хуваахад гарах үлдэгдлийг хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
3 0 0 0 1 1
Гаралт
2
Оролт
6 0 1 1 0 4 1 1 0 0 1 0
Гаралт
1
Оролт
10 0 1 2 1 4 4 4 0 8 0 0 0 1 0 1 1 0 0 1
Гаралт
27