Codeforces Round #803 (Div. 2)
06:59:03 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
C. Содон үржвэр
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Бяцхан Крис шугаман алгебрын маш том фен. Энэ удаад түүнд квадрат матрицийн содон үржвэрийн тухай гэрийн даалгавар өгсөн.
$n$ хэмжээтэй $x$ ба $y$ векторуудын цэгийн үржвэр нь векторуудын харгалзах бүрэлдэхүүн хэсгүүдийн үржвэрүүдийн нийлбэр байна. $n × n$ хэмжээтэй $A$ матрицийн содон үржвэр нь $n$ цэгийн үржвэрүүдийн нийлбэр байна. Эдгээрийн $i$-р нь $A$ матриц дахь $i$-р мөрийн вектор болон $i$-р баганын векторуудын цэгийн үржвэр байна.
Аз болж крис зөвхөн $GF(2)$-тай ажиллана! Энэ нь бүх үйлдлүүд (нэмэх болон үржүүлэх) 2-т дээр явагдана гэсэн үг. Үнэн хэрэгтээ $A$ матриц нь хоёртынх ба $A$ матрицийн элемент бүр 0 эсвэл 1 байна. Жишээлбэл доорх $A$ матрицийг авч үзье:
$A$ матрицийн содон үржвэр нь $(1*1 + 1*0 + 1*1) + (0*1 + 1*1 + 1*0) + (1*1 + 0*1 + 0*0) = 0 + 1 + 1 = 0$ байна.
Гэсэн ч гэрийн даалгаварт илүү их зүйлс байна. Крис $q$ асуулгыг боловсруулах ёстой; асуулга бүр дараах зүйлсийн нэг байна:
- өгөгдсөн мөрийн дугаар $i$-н хувьд $A$ дахь $i$-р мөрийн бүх утгыг эсрэгээр нь солих;
- өгөгдсөн баганын дугаар $i$-н хувьд $A$ дахь $i$-р баганын бүх утгыг эсрэгээр нь солих;
- $A$-н содон үржвэрийг олох.
Бит утга $w$-н утгыг солих гэдэг нь $1 - w$ болгож солино гэсэн үг буюу өөрөөр 1-г 0, 0-г 1 болгож солино гэсэн үг.
Анхны $A$ матриц өгөгдсөн бол гуравдугаар төрлийн асуулга бүрийн хувьд хариултуудыг хэвлэ. Та Крист гэрийн даалгавраа шийдэхэд нь туслах уу?
Оролт
Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 1000$) байх буюу $A$ матрицийн мөр болон баганын тоо юм. Дараагийн $n$ мөрөнд матрицийг тодорхойлно: $i$-р мөрөнд зайгаар тусгаарлагдсан $n$ бит байх ба $A$ матрицийн $i$-р мөрийг агуулна. $i$-р мөрний $j$-р элемент $a_{ij}$ ($0 ≤ a_{ij} ≤ 1$) нь $A$ матрицийн $i$-р мөр болон $j$-р баганын огтлолцол дээр байрлах элемент юм.
Оролтын дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 10^{6}$) байх буюу асуулгуудын тоо юм. Дараагийн $q$ мөр бүрт нэг асуулгыг тодорхойлох ба дараах хэлбэрүүдийн аль нэг нь байна:
- 1 $i$ -- $i$-р мөрийн бүх утгыг эсрэгээр нь солих;
- 2 $i$ -- $i$-р баганын бүх утгыг эсрэгээр нь солих;
- 3 -- $A$ матрицийн содон үржвэрийг хэвлэх.
Тэмдэглэл: оролт болон гаралтын хэмжээ маш их байж болох учраас програмчлалын хэлүүдийн гаралтын удаан аргуудыг бүү ашиглаарай. Жишээлбэл С++ хэлэнд (cin, cout) оролт гаралтын урсгалыг битгий ашиглаарай.
Гаралт
Оролт дахь 3-р төрлийн асуулгуудын тоог $m$ гэе. Гаралтанд $m$ урттай $s$ тэмдэгт мөр хэвлэх ба энд $s$ тэмдэгт мөрийн $i$-р тэмдэгт нь оролтонд байгаа $i$-р гуравдугаар төрлийн асуулгын хариу болох содон үржвэрийн утга юм.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 1 1 1 0 1 1 1 0 0 12 3 2 3 3 2 2 2 2 1 3 3 3 1 2 2 1 1 1 3
Гаралт
01001