−فهرست مندرجات
Rectangle
به یک مستطیل که در هر خانه آن یکی از اعداد 0 یا1 نوشته شده است می گوییم خوب اگر:
- هیچ زیرمربع 2×2 آن دارای تعدادی فرد عدد 1 نباشد.
- تعداد زیرمربع‌های 2×2 آن که دارای دقیقاً چهار 0 است برابر یا a باشد.
- تعداد زیرمربع‌های 2×2 آن که دارای دقیقا دو0 و دو 1 است برابر یا b باشد.
- تعداد زیرمربع‌های 2×2 آن که دارای دقیقاً چهار 1 است برابر یا c باشد.
شما باید برنامه‌ای بنویسید که تعداد مستطیل‌های خوب n×m را به‌دست آورد.
راهنمایی
به ازای هر مستطیل n×m خوب می‌توان اعداد a1,⋯,an و b1,⋯,bm از 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 هستند را به صورت پویا محاسبه کنیم و با استفاده از آن پاسخ سوال را به‌دست بیاوریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
