بهیک مستطیل که در هر خانه آن یکی از اعداد $0$ یا$1$ نوشته شده است میگوییم خوب اگر:
شما باید برنامهای بنویسید که تعداد مستطیلهای خوب $n \times m$ را بهدست آورد.
به ازای هر مستطیل $n \times m$ خوب میتوان اعداد $a_1,\cdots,a_n$ و $b_1,\cdots, b_m$ از $$0 و $$1 را طوری پیدا کرد که عدد درون سطر $i$ام و ستون $j$ام مستطیل برابر باشد با $a_i \oplus b_j$.
در تنها سطر خروجی پاسخ سوال را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 2 0 2 0 | 6 |
| 30 30 0 0 841 | 1 |
پاسخ
از راهنمایی سوال میتوان فهمید که هر مستطیل خوب$n \times m$ را میتوان متناطر کرد با $n+m$ عدد $a_1, \cdots, a_n$ و $b_1,\cdots, b_m$ طوریکه همه اعداد $$0 یا $$1 باشند و $a_1$ برابر باشد با $0$.
اگر $A_i$ برابر باشد با تعداد $x$هایی که $a_i = x$ و $a_{i+1} =x$ و $B_i$ برابر تعداد $x$هایی باشد طوریکه $b_i = x$ و $b_{i+1} =x$:
مستطیل متناظر با اعداد$a_1, \cdots, a_n$ و $b_1,\cdots, b_m$ دارای $A_0 \times B_0 + A_1 \times B_1$ زیر مربع $2 \times 2$ است که تمام خانههای آن $0$ است و دارای $A_0 \times B_1 + A_1 \times B_0$ زیر مستطیل $2 \times 2$ است که تمام خانههای آن $1$ است.
حال کافیست به ازای ($0 \leq i,j,k \leq 30$) تعداد رشتههای دودویی به طول $i$ که دارای $j$ تا $00$ و $k$ تا $11$ هستند را به صورت پویا محاسبه کنیم و با استفاده از آن پاسخ سوال را بهدست بیاوریم.