Codeforces Round #804 (Div. 2)
22:52:00 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
G. Анхны тоогоор нүүх
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сонья муужгайд $n$ ширхэг эерэг бүхэл тоонуудаас тогтох цуваа байжээ.Уг цуваанд нийт $2^{n}$ ширхэг боломжит дэд дараалал байх юм.Дэд дараалал бүрийн хувьд тэрээр уг дэд дарааллын бүх элементүүдийг тэнцүү болгох хамгийн бага үйлдлийн тоог тоолох юм.
Үйлдэл бүр нь доорх 2-ын нэг нь байна:
- Дэд дарааллын ямар нэг элементийг сонгон ямар нэгэн анхны тоогоор үржүүлнэ.
- Дэд дарааллын ямар нэг элементийг сонгон ямар нэгэн анхны тоонд хуваана.Сонгогдсон элемент нь сонгогдсон анхны тоондоо заавал хуваагдаж байх ёстой.
Бүх боломжит $2^{n}$ дэд дарааллуудын хамгийн бага үйлдлийн тоонуудын нийлбэр хэд вэ? Уг нийлбэрийг олон $10^{9} + 7$ модулаар бодож хэвлэнэ үү.
Оролт
Эхний мөрөнд цувааны хэмжээг илэрхийлэх ганц бүхэл тоо $n$ ($1 ≤ n ≤ 300 000$) өгөгдөнө.
2-дахь мөрөнд цувааны элементүүд болох $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 300 000$)-ууд өгөгдөнө.
Гаралт
Өгөгдсөн цувааны бүх боломжит дэд дарааллуудын хамгийн бага үйлдлийн тоонуудын нийлбэрийг $10^{9} + 7$ модулаар бодож хэвлэнэ.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
3 60 60 40
Гаралт
6
Оролт
4 1 2 3 4
Гаралт
24
Тэмдэглэл
Эхний жишээнд, $8$-н боломжит дэд дараалал байна: $(60, 60, 40)$, $(60, 60)$, $(60, 40)$, $(60, 40)$, $(60)$, $(60)$, $(40)$ болон $()$ (хоосон дэд дараалал).
Дэд дараалал $(60, 60, 40)$-ын хувьд бид бүх элементийг 2 үйлдлээр тэнцүү болгож чадна -- $40$-ыг $2$-т хувааж $20$-ыг гаргана, дараа нь $20$-ын $3$-аар үржүүлж $60$-ыг гаргана.Үүнээс бага үйлдлээр зорилгодоо хүрэх боломжгүй ба иймд бид хариулт дээр $2$-ыг нэмэх юм.
$(60, 40)$-тай адил 2 дэд дараалал байх ба тус бүр нь мөн дор хаяж $2$ үйлдлээр ижил элементүүдтэй болох юм.
Бусад дэд дараалал бүрийн хувьд бүх тоонууд нь аль хэдийн тэнцүү байна, иймд бид тус бүрийнх нь хувьд $0$ үйлдэл хийх хэрэгтэй.Ингэснээр нийлбэр нь $2 + 2 + 2 = 6$-тай тэнцүү байх юм.