پیچک

علی به تازگی نحوه‌ی رسم درخت زندگی به ارتفاع دلخواه را یاد گرفته است. علی برای رسم درخت زندگی به ارتفاع ١، یک راس تنها رسم می‌کند و آن را با عدد یک شماره‌گذاری می‌کند. برای رسم درخت زندگی به ارتفاع $n > 1$ او ابتدا درخت زندگی به ارتفاع $n - 1$ را رسم می‌کند. سپس برگ‌ها را به ترتیب شماره‌شان از کوچک به بزرگ گسترش می‌دهد. برای گسترش یک برگ مانند $v$ ،علی دو راس جدید به درخت اضافه می‌کند و آن‌ها را به $v$ وصل می‌کند و درنهایت دو راس جدید را با کوچک‌ترین عددهای طبیعی‌ای شماره‌گذاری می‌کند که هنوز به راسی در درخت اختصاص داده نشده‌اند.

$$درخت \space زندگی \space با \space ارتفاع \space یک، \space دو، \space سه$$

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

$$پیچک \space زندگی \space به \space ارتفاع \space سه$$

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

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

$6$- الف ($11$ نمره) : اگر مجموع ارزش تمام دورهای پیچک $T_4$ را با $C$ نشان دهیم، باقی‌مانده‌ی $C^4$ (به توان چهار توجه کنید) بر $\Delta$ چند است؟

$6$- ب ($11$ نمره) : علی زیرگراف حاصل از سه مسیر یال مجزا بین دو راس دلخواه $u$ و $v$ را، سه‌ور $uv$ می‌نامد. مجموع ارزش تمام سه‌ور‌های $uv$ را قدرت زوج $(u, v)$ می‌نامیم. باقی‌مانده‌ی مجموع قدرت تمام زوج‌های $(u, v)$ که $u < v$ در $T_6$ بر $\Delta$ چند است؟

$6$- ج ($12$ نمره) : باقی‌مانده‌ی تعداد مسیرهای $T_8$ (شامل مسیرهای تک راسی) بر $\Delta$ چند است؟ توجه کنید که اگر $u$ و $v$ دو راس متفاوت باشند، مسیر از $u$ به $v$ با برعکس همان مسیر از $v$ به $u$ یکسان است و نباید جداگانه محاسبه شوند.

• سوال قبل