فهرست مندرجات
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$ هستند را به صورت پویا محاسبه کنیم و با استفاده از آن پاسخ سوال را به‌دست بیاوریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
