المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۲۸:سوال ۶

درخت کشی

علی تصمیم گرفته است یک درخت ریشه‌دار دودویی رسم کند. او در مرحله‌ی اول یک راس روی کاغذ رسم می‌کند و شماره‌ی $1$ را به آن نسبت می‌دهد. سپس در هر یک از مراحل بعدی، به ازای هر راس درخت مرحله‌ی قبل، مانند راس شماره‌ی $x$، که درجه‌ی آن کوچک‌تر یا مساوی یک است، دو راس جدید اضافه می‌کند و آن‌ها را به راس شماره‌ی $x$ متصل می‌کند. سپس به یکی از دو راس جدید، شماره‌ی $2x$، و به دیگری شماره‌ی $2x + 1$ را نسبت می‌دهد.

از نظر علی، سرسبزی یک درخت، برابر با $AND$ بیتی اعداد راس‌های آن است. به عبارت دیگر، سرسبزی یک درخت عددی است که اگر در مبنای دو نوشته شود، تنها در مکان‌هایی رقم یک دارد که نمایش مبنای دوی تمامی عددهای راس‌های درخت، در آن مکان‌ها، رقم یک داشته باشند. برای مثال سرسبزی درخت رسم شده پس از دو مرحله، صفر است. از طرفی سرسبزی زیردرختی از آن که تنها شامل رئوس یک و سه است، برابر با یک است.

علی زیبایی یک درخت را برابر با مجموع سرسبزی تمام زیرگراف‌های همبند آن تعریف می‌کند و زیبایی درخت رسم شده بعد از $n$ مرحله را با $f(n)$ نمایش می‌دهد. برای مثال $f(1) = 1$ و $f(2) = 7$. علی می‌خواهد بداند تا چند مرحله به رسم درخت ادامه دهد و بنابراین از شما می‌خواهد به سوالات زیر پاسخ دهید.

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

$6$- الف ($11$ نمره) : باقی‌مانده‌ی $f(4)^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

پاسخ

70778

$6$- ب ($11$ نمره) : باقی‌مانده‌ی $f(16)$ بر $\Delta$ چند است؟

پاسخ

46925

$6$- ج ($12$ نمره) : باقی‌مانده‌ی $f(64)$ بر $\Delta$ چند است؟

پاسخ

154594


ابزار صفحه