خستگان


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

دوره ۲۸ ایا بعضی وقت‌ها خسته می‌شدند. دوره ۱۰۲۸ ایا بعد از فهمیدن این موضوع می‌خواهند آن برای تخریب وجهه دوره ۲۸ ایا استفاده کنند. دوره ۲۸ ایا در زمان خستگی همه دور هم جمع می‌شدند و فعالیت روزانه استاد بزرگ را تماشا می‌کردند.

استاد بزرگ هر روز یک تکه چوب دارای nn مربع به هم چسبیده تهیه می‌کرد و در خانه ii ام آن عدد aia_i را می‌نوشت. پس از تهیه چوب استاد عملیات زیر را روی تمام مرز‌‌های مربع‌های متوالی انجام می‌داد (n1n-1 مرز داریم).

استاد با ذکر غوودا ضربه‌‌ای محکم به مرز می‌زد که این ضربه به احتمال 12\frac{1}{2} چوب را می‌شکاند و به احتمال 12\frac{1}{2} نمی‌شکاند (‌استاد در دوران پیری به سر می‌برد به همین دلیل بعضی وقت‌ها چوب نمی‌شکست).

آنگاه دوره ۲۸ ایا مات و مبهوت از مهارت استاد و به نشانه احترام جمع اعداد روی هر تکه چوب باقی‌مانده را بر سردر شاز نصب می‌کردند (برای مثال اگر n=3n = 3 و اعداد روی تکه‌ها به ترتیب 17 ,2 ,3 17\ , 2\ , 3\ بودند و ضربه‌ی استاد مرز بین اولین تکه و دومین تکه را نمی‌شکاند ولی مرز بین دومین تکه و سومین را می‌شکاند، دوره ۲۸ ایا اعداد 5 ,17 5\ ,17\ را بر سر در شاز نصب می‌کردند).

دوره ۱۰۲۸ ایا برای اثبات خفونت خود می‌خواهند امیدریاضی تعداد اعداد متفاوتی که سر در شاز نصب می‌شود را بیابند (برای مثال تعداد اعضای متفاوت مجموعه‌ی {7,1,2,7,3,5,1,1}\{7, 1, 2, 7, 3, 5, 1, 1\} برابر 55 است).

ثابت می‌شود که جواب مورد نظر را می توان به صورت کسر PQ\frac{P}{Q} نشان داد (که قابل ساده کردن نیست). از شما خواسته شده که P.Q1P.Q^{-1} را در پیمانه‌ 109+710^9+7 خروجی دهید.

ورودی🔗

در خط اول ورودی عدد nn داده می‌شود. سپس در خط بعدی nn عدد طبیعی می‌آیند که ii امین آنها aia_i می‌باشد. 1n5001 \le n \le 500 1015ai1015-10^{15} \le a_i \le 10^{15}

خروجی🔗

امیدریاضی تعداد اعداد متفاوت نصب شده در سردر را به فرم P.Q1P.Q^{-1} در پیمانه 109+710^9+7 خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

2
-77 14   
Plain text

خروجی نمونه ۱🔗

500000005
Plain text

به احتمال 12\frac{1}{2} مجموعه ، {63}\{-63\}

به احتمال 12\frac{1}{2} مجموعه ، {77,14}\{-77,14\}

بر سردر شاز نوشته می‌شوند پس جواب مسئله 1+22\frac{1+2}{2} می‌باشد.

ورودی نمونه ۲🔗

3
1 2 3
Plain text

خروجی نمونه ۲🔗

750000007
Plain text

به احتمال 14\frac{1}{4} مجموعه ، {6}\{6\}

به احتمال 14\frac{1}{4} مجموعه ، {1,5}\{1,5\}

به احتمال 14\frac{1}{4} مجموعه ، {3,3}\{3,3\}

به احتمال 14\frac{1}{4} مجموعه ، {1,2,3}\{1,2,3\}

بر سر در شاز نوشته می‌شوند پس جواب مسئله 1+2+1+34\frac{1+2+1+3}{4} می‌باشد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.