باکتری درختی

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

شکل۲: نمونه‌ی یک درخت دودویی کامل به ارتفاع ۳. در این درخت سه راس خاکستری، راس‌های تقسیم هستند. یال‌های پر‌رنگ یک طریقه‌ی ممکن برای حرکت باکتری از ریشه به برگ‌ها را نشان می‌دهند. برگ‌های پررنگ نیز نشان‌دهنده‌ی برگ‌هایی هستند که در انتها درون آنها یک باکتری وجود دارد.

بینگو و پدر بینگو یک بازی روی این درخت انجام می‌دهند. ابتدا پدر بینگو زیرمجموعه‌ی دلخواه $t$ راسی $S$ از برگ‌های درخت را علامت می‌زند. سپس بینگو باید $k$ تا از راس‌های درخت را انتخاب کند و آنها را به محل تقسیم تبدیل کند طوری که اگر باکتری از راس ریشه شروع به حرکت کند، احتمال اینکه در انتها در تمامی راس‌های $S$ یک باکتری وجود داشته باشد، بزرگتر از صفر باشد. دقت کنید راس‌های انتخاب شده توسط بینگو نمی‌تواند شامل برگ‌ها باشد.

به ازای زیرمجموعه‌ی $S$ از برگ‌های درخت تعداد راه‌های ممکن برای انتخاب $k$ راس مذکور توسط بینگو را $A_S$ می‌نامیم. اگر $F$ مجموعه‌ی تمام زیرمجموعه‌های $t$ عضوی از برگ‌های درخت باشد، در این سوال بدنبال محاسبه‌ی $A=\sum_{S\in F} A_S$ هستیم. به عبارت دیگر $A$ مجموعِ $A_S$ها به ازای تمام زیرمجموعه‌های $t$ عضویِ $S$ از برگ‌های درخت می‌باشد.

قرار می‌دهیم $B=A \ mod \ (10^9+7)$.

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

$3$- الف ($8$ نمره) : اگر $n=5$، $t=5$ و $k=8$ باشد، باقیمانده‌ی $B$ بر $\Delta$ چند است؟

$3$- ب ($13$ نمره) : اگر $n=22$، $t=44$ و $k=88$ باشد، باقیمانده‌ی $B$ بر $\Delta$ چند است؟

$3$- ج ($15$ نمره) : اگر $n=55$، $t=777$ و $k=2222$ باشد، باقیمانده‌ی $B$ بر $\Delta$ چند است؟

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