اتاق فرار
پیمان و کیوان به همراه دوستانشان به یک اتاق فرار رفته‌اند و در آخرین مرحله باید رمز قفل نهایی را بیابند. پیمان در یکی از مراحل قبلی دو کاغذ پیدا کرده است که دنباله‌های زیر را نمایش می‌دهند.
$$ \begin{cases} b_1 = 123, b_2 = 456 \\ b_i = (2 \times b_{i - 1} + 5 \times b_{i - 2})mod \Delta \space \space \forall i > 2 \end{cases} $$ $$ \begin{cases} a_1 = 987, a_2 = 654 \\ a_i = (a_{i - 1} + 3 \times a_{i - 2}) mod \Delta \space \space \forall i > 2 \end{cases} $$
همچنین روی برگه‌ی کنار قفل نوشته شده است:
«دنباله‌ی $a$ را تا جمله‌ی $n$ و دنباله‌ی $b$ را تا جمله‌ی $m$ حساب کن. پاسخ در جدول $n \times m$ مانند $M$ است که $M_{i,j} = a_i \oplus b_j$ است. اگر به ازای هر زیر مستطیل این جدول حاصل عملگر $or$ بیتی اعداد آن زیر مستطیل را حساب کنی، مجموع این اعداد به ازای همه‌ی زیرمستطیل‌های $M$ رمز را به تو نشان می‌دهد.»
منظور از $M_{i,j}$ خانه‌ی سطر $i$ و ستون $j$ جدول $M$ و $\oplus$ عملگر $xor$ بیتی (یای انحصاری) است. یک زیر مستطیل از $M$ را می‌توان به صورت $(i_1, i_2, j_1, j_2)$ نشان داد که شامل خانه‌هایی مانند $(x, y)$ است که $$ 1 \leq i_1 \leq x \leq i_2 \leq n \space \& \space 1 \leq j_1 \leq y \leq j_2 \leq m$$
باشد. با پاسخ به سوالات زیر به کیوان، پیمان و دوستانشان کمک کنید تا رمز قفل را کشف کنند و از اتاق فرار خارج شوند.
فرض کنید رمز قفل به ازای مقادیر $n$ و $m$ را با $f(n, m)$ نشان می‌دهیم.
تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 229939$ محاسبه شده‌اند.
$4$- الف ($11$ نمره) : باقی‌مانده‌ی $f(1, 10^5)$ بر $\Delta$ چند است؟
پاسخ
87220
$4$- ب ($11$ نمره) : باقی‌مانده‌ی $f(1000, 1000)$ بر $\Delta$ چند است؟
پاسخ
31714
$4$- ج ($11$ نمره) : باقی‌مانده‌ی $f(10^5, 10^5)$ بر $\Delta$ چند است؟
پاسخ
153342
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
