ببعی فولاد زره!

ببعی دنباله‌ي اعداد ۰ تا$۲^n-1$ را به ترتیب بر روی تخته یادداشت کرده است. گاوی بعد از دیدن تخته، همه‌ي اعداد را پاک کرده و به جای هر عدد، تعداد بیت های ۱ آن عدد در مبنای ۲ را یادداشت کرد. به عنوان مثال اگر $n$ برابر با ۳ باشد، آنگاه دنباله‌ي اولیه‌ برابر با ۰،۱،۲،۳،۴،۵،۶،۷ و دنباله‌ي جدید برابر با ۰،۱،۱،۲،۱،۲،۲،۳ خواهد بود. سپس ببعی با دیدن دنباله ی جدید، تصمیم گرفت تعداد نابجایی های دنباله را بشمارد. فرض کنید عدد $i$-ام دنباله را $a_i$ بنامیم. در این صورت به زوج مرتب $(i, j)$ یک نابجایی گفته می شود، اگر و تنها اگر، $i\lt j$ و $a_i \lt a_j$ باشد. به عنوان مثال تعداد نابجایی ها در مثال بالا برابر با ۱ است.

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

$5$- الف (۱۱ نمره) : اگر $n$ برابر با ۷ و $M$ برابر با تعداد نابجایی های دنباله باشد، باقیمانده‌‌ي تقسیم $M^n$ بر $\Delta$ چقدر است؟

$5$- ب (۱۱ نمره) : اگر $n$ برابر با ۱۴ و $M$ برابر با تعداد نابجایی های دنباله باشد، باقیمانده‌‌ي تقسیم $M^n$ بر $\Delta$ چقدر است؟

$5$- ج (۱۱ نمره) : اگر $n$ برابر با ۲۰۱۴ و $M$ برابر با تعداد نابجایی های دنباله باشد، باقیمانده‌‌ي تقسیم $M^n$ بر $\Delta$ چقدر است؟

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