Codeforces Round #716 (Div. 2)
03:48:46 |
Codeforces Round #717 (Div. 2)
2 өдрийн дараа |
Codeforces Round #718 (Div. 1)
4 өдрийн дараа |
Codeforces Round #718 (Div. 2)
4 өдрийн дараа |
Codeforces Global Round 14
13 өдрийн дараа |
E. Дэвү ба цэцэгнүүд
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дэвү өөрийн цэцэрлэгийг цэцэгнүүдээр чимэглэхийг хүсжээ. Тэр $i$-р хайрцаг нь $f_{i}$ цэцэг агуулдаг $n$ хайрцаг худалдаж авсан байна. Нэг хайрцаг дахь бүх цэцэгнүүд ижил өнгөтэй (иймээс тэднийг ялгах боломжгүй). Мөн ямар ч хоёр хайрцаг ижил өнгийн цэцэгнүүдтэй байж болохгүй.
Одоо Дэвү хайрцагнуудаас цэцэрлэгээ чимэглэх яг $s$ цэцэг сонгохыг хүсэж байгаа ба ингэж цэцэг сонгох нийтдээ хэдэн янзын боломж байгааг мэдэхийг хүсэж байна. Түүний чамаас асуусан тоо хэтэрхий том байж болох тул $(10^{9} + 7)$-д хуваасан үлдэгдлийг олоход болно.
Хэрвээ нэг хайрцгаас ялгаатай тооны цэцэгнүүдийг хоёр аргаар сонгодог бол ялгаатай хоёр арга гэж үзнэ.
Оролт
Оролтын эхний мөр нь зайгаар тусгаарлагдсан $n$, $s$ ($1 ≤ n ≤ 20$, $0 ≤ s ≤ 10^{14}$) бүхэл тоонуудыг агуулна.
Хоёр дахь мөр нь $n$ ширхэг зайгаар тусгаарлагдсан $f_{1}, f_{2}, ... f_{n}$ ($0 ≤ f_{i} ≤ 10^{12}$) бүхэл тоонуудаас бүрдэнэ.
Гаралт
Нэг бүхэл тоо гарна. Энэ бол Дэвүгийн цэцэгнүүдийг сонгож чадах боломжит нийт аргыг $(10^{9} + 7)$-д хуваасан үлдэгдэл.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
2 3 1 3
Гаралт
2
Оролт
2 4 2 2
Гаралт
1
Оролт
3 5 1 3 2
Гаралт
3
Тэмдэглэл
Жишээ 1. $3$ цэцэг сонгох хоёр боломж байна: $(1, 2)$ ба $(0, 3)$.
Жишээ 2. $4$ цэцэг сонгох нэг л боломж байна: $(2, 2)$.
Жишээ 3. $5$ цэцэг сонгох гурван боломж байна: $(1, 2, 2)$, $(0, 3, 2)$, ба $(1, 3, 1)$.