اثر بستنی

کمیته‌ی ملی المپیاد کامپیوتر می‌خواهد برای دانش‌پژوهان خود یک بستنی فروشی ویژه بسازد. اعضای کمیته تصمیم گرفته‌اند بستنی فروشی را به شکل $n$ سکوی کنار هم بسازند. همچنین از نظر آن‌ها ضروری است که دنباله‌ی ارتفاع سکو‌ها جایگشتی از اعداد $١$ تا $n$ باشد.

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

حال کمیته از شما خواسته است تعداد دنباله‌های ممکن برای ارتفاع سکوها را محاسبه کنید که تمام شرایط گفته شده را دارند. این مقدار با $f(n, k)$ نمایش داده می‌شود. شما باید به سوالات زیر پاسخ دهید.

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

$3$- الف ($11$ نمره) : باقی‌مانده‌ی $f(50, 10)$ بر $\Delta$ چند است؟

پاسخ

91293

$3$- ب ($11$ نمره) : باقی‌مانده‌ی $f(1000, 150)$ بر $\Delta$ چند است؟

پاسخ

27156

$3$- ج ($12$ نمره) : باقی‌مانده‌ی $f(10^4, 1500)$ بر $\Delta$ چند است؟

پاسخ

152427