====== Rectangle ====== به یک مستطیل که در هر خانه آن یکی از اعداد ‎$0$‎ یا‎$1$‎ نوشته شده است می گوییم خوب‎ اگر: * هیچ زیرمربع ‎$2 \times 2$‎ آن دارای تعدادی فرد عدد ‎$1$‎ نباشد. * تعداد زیرمربع‌های ‎$2 \times 2$‎ آن که دارای دقیقاً چهار ‎$0$‎ است برابر یا ‎$a$‎ باشد. * تعداد زیرمربع‌های ‎$2 \times 2$‎ آن که دارای دقیقا دو‎$0$‎ و دو ‎$1$‎ است برابر یا ‎$b$‎ باشد. * تعداد زیرمربع‌های ‎$2 \times 2$‎ آن که دارای دقیقاً چهار ‎$1$‎ است برابر یا ‎$c$‎ باشد. شما باید برنامه‌ای بنویسید که تعداد مستطیل‌های خوب ‎$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$. ===== ورودی ===== * در تنها سطر ورودی پنج عدد $n$، $m$، $a$، $b$ و $c$ آمده است. * $1 \leq n, m \leq 30$ * ‎$0 \leq a, b, c \leq n \times m$ ===== خروجی ===== در تنها سطر خروجی پاسخ سوال را چاپ نمایید.‎ ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |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$ هستند را به صورت پویا‎‎ محاسبه کنیم و با استفاده از آن پاسخ سوال را به‌دست بیاوریم. * [[سوال ۸۰|سوال بعد]] * [[سوال ۷۸|سوال قبل]]