پارتی بازی

$n$ دانش پژوه برای ورود به محل آزمون مرحله‌ی سوم المپیاد کامپیوتر به ترتیب جلوی درب دانشگاه شهیدرجایی صفی تشکیل داده‌اند. مسئولان برای نشاندن دانش پژوهان در سایت یک صف جلوی درب سایت تشکیل داده‌اند که ابتدا خالی است. روند ورود دانش پژوهان به سایت این‌گونه است که پس از ورود به دانشگاه در صف جلوی سایت قرار می‌گیرند و پس‌از رسیدن نوبتشان به داخل سایت می‌روند. مسئولان برای هر دانش پژوهی که اسم رمز را بگوید پارتی بازی می‌کنند. مسئولان نمیدانند چه کسانی اسم رمز را می‌دانند، ممکن است همه آن‌را بدانند.

به طور دقیق‌تر در هر دقیقه یکی از سه اتفاق زیر می‌افتد:

1. اولین نفر در صف بیرون دانشگاه در انتهای صف جلوی سایت قرار می‌گیرد.
2. اولین نفر در صف جلوی سایت به داخل سایت می‌رود.
3. اولین نفر در صف بیرون دانشگاه اسم رمز را می‌گوید و مسئولان او را با پارتی بازی به‌طور مستقیم و بدون وارد شدن به صف جلوی سایت به داخل سایت می‌فرستند.

برای اینکه جلوی سایت زیاد شلوغ نشود، طول صف جلوی سایت هیچ‌گاه از $k$ نفر بیشتر نمی‌شود.

صندلی های سایت از $1$ تا $n$ شماره گذاری شده‌اند. هر نفر که وارد سایت می‌شود روی اولین صندلی خالی‌ (با کم‌ترین شماره) می‌نشیند.

مثلاً اگر $n=3$ و $k=1$ باشد، یکی از اتفاقات ممکن این است:

1. نفر اول صف بیرون دانشگاه (دانش پژوه شماره‌ی $1$) در انتهای صف جلوی سایت قرار می‌گیرد.
2. نفر اول صف بیرون دانشگاه (دانش پژوه شماره‌ی $2$) اسم رمز را می‌گوید و مسئولان با پارتی بازی او را وارد سایت می‌کنند و او روی صندلی شماره‌ی $1$ می‌نشیند.
3. نفر اول صف جلوی سایت (دانش پژوه شماره‌ی $1$) وارد سایت می‌شود و روی صندلی شماره‌ی $2$ می‌نشیند.
4. نفر اول صف بیرون دانشگاه (دانش پژوه شماره‌ی $3$) اسم رمز را میگوید و مسئولان با پارتی بازی او را وارد سایت می‌کنند و او روی صندلی شماره‌ی $3$ می‌نشیند.

بدین ترتیب چینش دانش پژوهان در سایت $\langle 2, 1, 3 \rangle$ است (یعنی روی صندلی اول دانش پژوه شماره‌ی $2$ نشسته است و $\cdots$). با توجه به محدودیت های بالا و اینکه صف روبروی دانشگاه هم اکنون تشکیل شده است، چند چینش متفاوت از دانش پژوهان بر روی صندلی‌های سایت ممکن است به طوری که همه ی $n$ دانش پژوه داخل سایت نشسته باشند؟

هوشنگ از مسئولان برگزاری مسابقه است و عدد فوق را $f$ می‌نامد. او از شما خواسته به سوالات زیر پاسخ دهید.

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

$1$- الف ($11$ نمره) : اگر $n=100$ و $k=1$ باشد، باقی‌مانده‌‌ی تقسیم $f$ بر $\Delta$ چند است؟

$1$- ب ($11$ نمره) : اگر $n=11$ و $k=4$ باشد، باقی‌مانده‌‌ی تقسیم $f$ بر $\Delta$ چند است؟

$1$- ج ($11$ نمره) : اگر $n=100$ و $k=17$ باشد، باقی‌مانده‌‌ی تقسیم $f$ بر $\Delta$ چند است؟

• سوال بعد