المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۴:سوال ۵

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

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

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

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

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


ابزار صفحه