به دلیل اینکه این سوالات برای المپیاد کامپیوتر طراحی شده و محدودیت تستها، امکان ارسال فقط با زبان سیپلاسپلاس ممکن است.
آقای میخواهد با دعوت تعدادی از کارمندهای شرکتش یک دوره مهمانی مخفیانه برگزار کند.
اگر این شرکت کارمند داشته باشد، این کارمندها با شمارههای تا مشخص میشوند و فرد شماره با افراد با شمارههای ، و در صورت وجود دوست است.
در دوره مهمانیهای آقای ، هر شب یک مهمانی برگزار میشود. در این دوره مهمانیها، هر کس در هر مهمانی حضور پیدا کند، در تمام مهمانیهای شبهای بعدی نیز حضور پیدا میکند. آقا تصمیم گرفته برای شب اول تعدادی از کارمندها را مستقیما دعوت کند تا در مهمانی حضور داشته باشند، و بعد از آن در هر شب، هر فردی که در مهمانی شب قبلی حضور داشته دوستانش را برای مهمانی بعدی دعوت میکند و آنها نیز در مهمانی شب بعد حضور پیدا میکنند. همچنین هر کس به اندازه تعداد مهمانیهایی که از دست داده، ناراحت میشود. ناراحتی کلی افراد نیز برابر با مجموع ناراحتی کارمندها است.
حال آقای میخواهد تعدادی از کارمندهایش را به مهمانی دعوت کند، او برای انتخاب افراد در شب اول یکی از مجموعههای ناتهی کارمندان را به صورت تصادفی و با احتمال برابر انتخاب و دعوت میکند. (یعنی هر کدام از حالت ممکن به احتمال برابر انتخاب میشوند)
آقای از شما خواسته تا امیدریاضی ناراحتی کلی افراد را برای او محاسبه کنید ولی چون یادش نیست که شرکتش چند کارمند دارد حدس مختلفی که برای دارد را به شما میگوید تا جواب را در همه حالات به دست آورید. همچنین چون او اعداد اعشاری را دوست ندارد، از شما خواسته که اگر امید ریاضی خواسته شده به صورت نوشته شود که و اعداد صحیح نسبت به هم اول هستند، با توجه به این که بر بخشپذیر نیست، مقدار به پیمانه را به عنوان جواب گزارش کنید.
در سطر اول ورودی عدد آمدهاست.
در هر یک از سطر بعدی یک مقدار آمده است که تعداد کارمندان شرکت در این سناریو را نشان میدهد.
در هر یک از خط خروجی, مقدار خواسته شده را برای مربوطه خروجی دهید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۷ | |
۲ | ۲۳ | هر عدد به شکل است. |
۳ | ۳۳ | |
۴ | ۳۷ | بدون محدودیت اضافی |
در حالت امید ریاضی ناراحتی کلی افراد برابر است. برای امید ریاضی برابر است که به پیمانه برابر با است.
امید ریاضی ناراحتی کلی افراد در مثالهای داده شده به صورت زیر است: