جدول باکتری

جینگو از یک مغازه‌ی باکتری فروشی، یک جدول $n \times n$ تهیه کرده است. دو خانه‌ی این جدول را مجاور می‌گوییم اگر در یک ضلع مشترک باشند. در ابتدا در هر یک از خانه‌های چهار گوشه‌ی جدول یک باکتری وجود دارد و سایر خانه‌ها خالی هستند.

می‌دانیم اگر در ابتدای یک روز در خانه‌ای از جدول حداقل یک باکتری وجود داشته باشد، در ظهر آن روز به هر یک از چهار خانه‌ی مجاور آن (در صورت وجود) یک باکتری اضافه خواهد شد.

فرض کنید سطر‌ها به ترتیب از بالا به پایین با شماره‌های $1,2,\ldots,n$ و ستون‌ها از چپ به راست با شماره‌های $1,2,\ldots,n$ شماره‌گذاری شده‌اند. خانه‌ی $(i,j)$ (خانه‌ی سطر $i$ام و ستون $j$ام جدول) دارای یک توان باکتریایی است که با $f(i,j)$ مشخص می‌شود. اگر تعداد باکتری‌های خانه‌ی $(i,j)$ از $f(i,j)$ بیشتر یا مساوی شود این خانه اشباع شده و همه‌ی باکتری‌های آن می‌میرند و دیگر هیچگاه باکتری‌ای در این خانه از جدول رشد نمی‌کند. اشباع شدن خانه‌ها در عصر یک روز اتفاق می‌افتد. دقت کنید پس از اشباع شدن یک خانه‌ و صفر شدن تعداد باکتری‌ها در آن، این خانه دیگر تاثیری در رشد باکتری‌ها در خانه‌‌های مجاور آن ندارد.

فرض کنید تکثیر باکتری‌ها از ظهر روز اول شروع شود. $t_{i,j}$ را اولین روزی که خانه‌ی $(i,j)$ اشباع می‌شود تعریف می‌کنیم (در صورتیکه خانه‌ی $(i,j)$ هیچگاه اشباع نشود $t_{i,j}=0$ است) و قرار می‌دهیم $A = \sum_{i=1}^n\sum_{j=1}^n t_{i,j}$.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10607$ محاسبه شده‌اند.

$5$- الف ($9$ نمره) : اگر $n=8$ و $f(i,j)=10+(7^{\: i}\times3^{\: j} \quad mod \: 41)$ باشد، باقی‌مانده‌ی $A^3$ بر $\Delta$ چند است؟

$5$- ب ($9$ نمره) : اگر $n=40$ و $f(i,j)=10^4+(7^{\: i}\times3^{\: j} \quad mod \: 99991)$ باشد، باقی‌مانده‌ی $A^3$ بر $\Delta$ چند است؟

$5$- ج ($13$ نمره) : اگر $n=100$ و $f(i,j)=10^8+(7^{\: i}\times3^{\: j} \quad mod \: (10^9+7))$ باشد، باقی‌مانده‌ی $A^3$ بر $\Delta$ چند است؟

• سوال بعد
• سوال قبل