- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک جدول \(n \times m\) داریم. در هر خانه از این جدول 0 یا 1 نوشته شده. در هر مرحله میتوانیم یک سطر را با یک سطر دیگر یا یک ستون را با یک ستون دیگر XOR بگیریم.
بعد از XOR گرفتن سطر \(a\) با سطر \(b\) داریم:
\[ a_{j_{new}} = a_{j_{old}} \oplus b_j \quad (1 \le j \le m) \]
بعد از XOR گرفتن ستون \(a\) با ستون \(b\) داریم:
\[ a_{i_{new}} = a_{i_{old}} \oplus b_i \quad (1 \le i \le n) \]
و همچنین \[ 0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0 \]
با انجام دادن تعداد دلخواه از عملیاتهای بالا، حداکثر تعداد 1ی که میتوان در این جدول آورد را محاسبه کنید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(t\) آمده که تعداد سناریوها را نشان میدهد. \[1 \leq t \leq 100 \, 000\]
در سطر اول هر سناریو، دو عدد صحیح و مثبت \(n\) و \(m\) که با یک فاصله از هم جدا شده اند و بهترتیب تعداد سطرها و ستونهای جدول را نشان میدهد. \[1 \leq n.m \leq 100\, 000\]
در \(n\) سطر بعدی هر سناریو، در هر کدام یک رشته از \(m\) کاراکتر 0 یا 1 میآید که وضعیت اولیه جدول را نشان میدهد.
تضمین میشود که \(\sum n.m\) برای همهی سناریوها از \(100\,000\) بیشتر نمیشود.
خروجی
خروجی \(t\) سطر دارد و به ازای هر سناریو باید حداکثر تعداد 1هایی که میتوان با عملیاتهای بالا ساخت را چاپ کنید.
مثال
ورودی نمونه ۱
3
3 4
1010
1010
0000
2 2
01
10
1 5
10101
خروجی نمونه ۱
12
3
5
در مثال اول اگر ابتدا مقدار سطر ۳ را با سطر ۱ XOR بگیریم به جدولی میرسیم که ستونهای آن یکی در میان تماما 1 و تماما 0 است. سپس میتوانیم ستون ۲ و ۴ را با ستون ۱ XOR بگیریم تا به جدولی تماما 1 برسیم.
در مثال دوم اگر سطر ۲ را با سطر ۱ XOR بگیریم به جدولی میرسیم که تنها خانه 0 آن گوشه بالا چپ است و ۳ تا 1 خواهیم داشت. میتوان نشان داد به جدول تمام ۱ هیچگاه نخواهیم رسید.
در مثال سوم اگر ستونهای ۲ و ۴ را با ستون ۵ XOR بگیریم به جدولی تماما 1 میرسیم.
ارسال پاسخ برای این سؤال