Codeforces Round #804 (Div. 2)
00:34:07 |
Educational Codeforces Round 131 (Rated for Div. 2)
5 өдрийн дараа |
Codeforces Round #805 (Div. 3)
7 өдрийн дараа |
Codeforces Round #806 (Div. 4)
9 өдрийн дараа |
D. Алимхүү ба тѳвѳгтэй даалгавар
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Талххүү маш хэцүү даалгавартай иржээ. Тэрээр түүнийгээ Алимхүүд ѳгч, гэтэл Алимхүү хэрхэн шийдэхийг мэдэхгүй байв. Түүнд туслах боломж байна уу?
$n × n$ шатрын хѳлѳг ѳгѳгдсѳн. Хѳлгийн нүд бүрт эсвэл 'x' үсэг, эсвэл 'o' үсэг, эсвэл хоосон байна. Нүд бүрийн хувьд хѳрш 'o' үсэгтэй нүдний тоо тэгш байхаар хоосон нүднүүдийг 'x' юмуу 'o' (тѳгсгѳлд нь нүд бүрт яг нэг үсэг байх ёстой) үсгээр дүүргэх боломжийн тоо хэд байх вэ? Боломжийн тоог $1000000007$ $(10^{9} + 7)$ тоонд хуваахад гарах үлдэгдлийг ол. Хѳрш нүд гэж ерѳнхий талтай нүднүүдийг хэлнэ.
Оролт
Эхний мѳрѳнд хѳлгийн хэмжээ, анх үсэгтэй байсан нүдний тоог илэрхийлэх $n$, $k$ ($1 ≤ n, k ≤ 10^{5}$) бүхэл тоо ѳгѳгднѳ.
Дараа нь $k$ мѳр байрлана. $i$-р мѳр хоёр тоо нэг үсэг агуулна: $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $c_{i}$ нь 'o' юмуу 'x'). Энэ нь $c_{i}$ үсэг $a_{i}$-р мѳр $b_{i}$-р баганын огтлол нүдэнд оршино гэсэн утгыг илтгэнэ. Ѳгсѳн нүднүүд ялгаатай.
Мѳрүүд дээрээс доош, баганууд зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаартай гэж үзнэ.
Гаралт
Бодлогын хариу болох ганц тоог хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
3 2 1 1 x 2 2 o
Гаралт
2
Оролт
4 3 2 4 x 3 4 x 3 2 x
Гаралт
2
Тэмдэглэл
Эхний жишээ тэстийн хувьд хоёр янзын боломжтой:
xxo xoo
xox ooo
oxx oox