خلمپیاد

به یک درخت ریشه‌دار دودویی، کامل می‌گوییم اگر و فقط اگر هر راس یا فرزندی نداشته باشید یا دقیقا دو فرزند داشته باشد. همچنین در این گونه از درخت‌ها، ترتیب فرزندان مشخص است و بنابراین بچه‌ی چپ از بچه‌ی راست قابل تشخیص است.

فاطمه، مدیر کارخانه‌ی خاک پای المپیاد (به اختصار «خلمپیاد») است. به جز فاطمه، هر یک از کارمندان دقیقا یک رییس دارند. اگر به ازای هر یک از کارمندان یک راس گذاشته و بین راس متناظر هر کارمند با راس متناظر رییس او، یک یال بگذاریم، گراف حاصل یک درخت دودویی کامل است.

در خلمپیاد، به کارمندانی که رییس هیچ فردی نیستند، «دانش‌پژوه» و به سایر کارمندان، «مسئول» گفته می‌شود. همچنین هر یک از کارمندان سطح مشخصی دارد. سطح فاطمه صفر است. سطح هر یک از کارمندان یکی بیشتر از رییسشان است. در خلمپیاد سطح تمامی دانش‌پژوهان با هم برابر است. همچنین دانش‌پژوهان از چپ به راست و با شروع از صفر شماره گذاری شده‌اند. بنابراین اگر سطح دانش پژوهان $n$ باشد، شماره‌ی هر دانش‌پژوه عددی حسابی بین $٠$ تا $2^n - 1$ است.

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

در نهایت فاطمه نیز مانند سایر مسئولین تا زمانی که تعداد نامه‌ها به کمتر از $k$ برسد، آن‌ها را در دسته‌های $k$تایی دور می‌اندازد. درنهایت نامه‌های باقی‌مانده را می‌خواند.

فرض کنید $A$ مجموعه‌ی شماره‌ی دانش‌پژوهانی باشد که برای فاطمه نامه می‌نویسند. مجموعه‌ی طلایی $A$، زیرمجموعه‌ای از $A$ شامل شماره‌ی دانش‌پژوهانی است که فاطمه حتما نامه‌ی آن‌ها را می‌خواند. به عبارت دیگر نامه‌ی آن‌ها مستقل از نحوه‌ی دور ریختن نامه‌های اضافی توسط کارمندان به دست فاطمه می‌رسد و فاطمه نیز آن‌ها را دور نمی‌ریزد. توجه کنید که این مجموعه می‌تواند تهی باشد. مجموعه‌ی طلایی $A$ را با $f(A)$ نشان می‌دهیم.

فرض کنید $ C = \{0, 1,\dots, 2^n - 1\}$ مجموعه‌ی شامل شماره‌ی تمامی دانش‌پژوهان باشد. $g(B)$ را تعداد مجموعه‌های $A \subseteq C$ تعریف می‌کنیم که $B \subseteq f(A)$.

فاطمه برای سنجش کارایی برنامه‌اش، از شما کمک خواسته است تا مقدار $g(B)$ را حساب کنید. با توجه به بزرگ بودن این مقدار، او پذیرفته است که شما در عوض، مقدار $h(B)$ را محاسبه کنید که باقی‌مانده‌ی $g(B)$ بر $10^9+7$ است. به فاطمه کمک کنید و به سوالات زیر پاسخ دهید.

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

$2$- الف ($11$ نمره) : اگر $n = 20$ و $k = 10$، باقی‌مانده‌ی $h(\{0\})^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

$2$- ب ($11$ نمره) : اگر $n = 10^6$ و $k = 11$، باقی‌مانده‌ی $h(\{0, 10^5\})^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

$2$- ج ($11$ نمره) : اگر $n = 1000$ و $k = 11$، باقی‌مانده‌ی $(\sum_{B\subseteq C}h(B))^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

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