موبدِ معبدِ شائولین جدیداً به درختها علاقهی عجیبی پیدا کرده است و میزان قداست زیادی در خلقت آنها احساس میکند. او به تازگی با امیرِ دربارِ سلطنتی آشنا شده و گاهی اوقات با یکدیگر به عبادت میپردازند. او از طریق شکرالله (سلطان دانشمندان دربار امیر)، با گرافها و مفهوم درخت1) در آنها آشنا شده و بسیار از این تعریف در علم گراف خوشش آمده است.
او برای دستگرمی ابتدا به کمک سرداد (سلطان دانشمندان دربار امیر) یک درخت $n$ راسی ریشهدار $T$ با رئوس $1$ تا $n$ میکشد (راس $1$ ریشه است) و سپس این درخت را به امیر میدهد تا شمارهگذاری رئوس آن را به ترتیب دلخواه خود جابجا کند. از آنجایی که شکرالله به اعداد طبیعی متوالی علاقهی زیادی دارد برای هر راس $v$ در درخت $T$، عددی به نام $f_v$ تعریف میکند که برابر با «طول بلندترین بازهی متوالی از اعداد طبیعی موجود در زیردرخت $v$» است؛ به طور مثال اگر مجموعه اعداد نسبت داده شده به رئوس داخل زیردرخت راس $v=2$ برابر $\langle1,2,7,8,9,11\rangle$ باشد $f_v=3$ خواهد بود. زیرا $7$ و $8$ و $9$ متوالی هستند. دقت کنید که عدد راس $v$ نیز در این مجموعه حساب میشود و همچنین جایگاه این اعداد در زیردرخت اهمیتی ندارد و تنها حضور یا عدم حضورشان در این زیردرخت مهم است.
شکرالله برای به چالش کشیدن موبد و امیر مسئلهی زیر را برای آنها مطرح میکند؛ او به ازای هر $n!$ حالت شمارهدهی امیر به رئوس درخت $T$ یک عدد به درخت حاصل نسبت میدهد که برابر با جمع تمام مقادیر $f$ به ازای $n$ راس درخت حاصل است. سپس این اعداد را باهم جمع میزند و اسم آن را $g(T)$ میگذارد. با گرفتن درخت $T$ به موبد و امیر برای حساب کردن مقدار $g(T)$ کمک کنید!
تمام پاسخهای ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شدهاند.
بخش اول (۳۱ نمره) : اگر در درخت $T$ مقدار $n=5$ و پدر راس $i$ $(2\leq i\leq n)$ برابر با $i-1$ باشد (یک مسیر $5$ راسی)، حاصل $g(T)^{10}$ به پیمانهی $\Delta$ را خروجی دهید.
پاسخ
1837518
بخش دوم (۳۴ نمره) : اگر در درخت $T$ مقدار $n=500$ و پدر راس $i$ $(2\leq i\leq n)$ برابر با $i-1$ باشد (یک مسیر $500$ راسی)، حاصل $g(T)^{10}$ به پیمانهی $\Delta$ را خروجی دهید.
پاسخ
9571735
بخش سوم (۳۵ نمره) : اگر در درخت $T$ مقدار $n=2^{20}-1$ و پدر راس $i$ $(2\leq i\leq n)$ برابر با $\left\lfloor\frac{i}{2}\right\rfloor$ باشد (یک درخت دودویی کامل2) و متوازن3) $2^{20}-1$ راسی)، حاصل $g(T)^{10}$ به پیمانهی $\Delta$ را خروجی دهید.
پاسخ
4100106