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

خشایارشاه (Xerxes) پادشاه پادشاهان، پادشاه ایران بود و بر بیش از ۴۰ درصد مردم جهان در زمان خود حکومت می‌کرد.

خشایارشاه برای انتخاب تیم محافظتی خویش، $n$ جنگجو را با شماره‌های $0$ تا $n-1$ در دربار خود آموزش داد. پس از آموزش مشخص‌شد که نتیجه مبارزه‌ی هر دو جنگجویی چیست و کدام دیگری را شکست می‌دهد. (قطعا در یک نبرد، یکی دیگری را شکست می‌دهد). اگر جنگجوی $i$ جنگجوی $j$ را شکست دهد $a_{i,j} = 1$ و $a_{j,i} = 0$ خواهد بود.

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

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است.

در $i$ امین سطر (با شروع از صفر) از $n$ سطر بعدی رشته‌ای به طول $n$ آمده‌است که $j$ امین حرف آن (با شروع از صفر) برابر با $a_{i,j}$ است. $1 \le n \le 75$ $0 \le a_{i,j} \le 1$ $a_{i,j} \ne a_{j,i}$ $a_{i,i} = 0$

خروجی🔗

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

زیرمسئله‌ها🔗

مثال🔗

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

2
01
00

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

1
0

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

3
010
001
100

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

2
0 1

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

5
00111
10001
01010
01001
00100

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

2
0 1

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

«تو مرد این کارا نیستی»، این واکنش امین بود وقتی علی داستان پروژه‌ی یک ملیاردی را برایش تعریف کرد.

امین به او گفت برای انجام این پروژه می‌بایست نظریه‌ اعدادش خیلی قوی باشد، برای سنجش سطح نظریه‌ی اعداد او، امین دنباله‌ی $a_0, a_1, \dots, a_{n-1}$ به طول $n$ را به او داد و از او خواست تعداد سه‌تایی‌های مرتب $(i,j,k)$ که $0 \le i < j < k < n$ و $gcd(a_i, a_k) = a_j$ را بیابد.

علی به آن پول خیلی احتیاج دارید، کمکش کنید تا این مسئله را حل کند تا کمک امین را برای پروژه داشته باشد.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است.

در سطر بعد $n$ عدد $a_0, a_1, \dots, a_{n-1}$ آمده‌است. $3 \le n \le 100\ 000$ $1 \le a_i \le 100\ 000$

خروجی🔗

در تنها سطر خروجی تعداد سه‌تایی‌های خواسته‌شده را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

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

5
6 2 3 4 3

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

2

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

5
1 1 1 1 1

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

10

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

8
1 2 3 4 1 2 3 4

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

8

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

شنل‌قرمزی یک گراف‌کار قوی است. او $n$ بازه به شکل $[ l_i, r_i ]$ دارد. حال او گرافی $n$ راسی ساخته‌است که راس $i$ اُم متناظر با بازه‌ی $i$ اُم است. او بین دو راس $u$ و $v$ یال می‌گذارد، اگر و فقط اگر بازه‌ی $u$ و $v$ اشتراک داشته باشند (یعنی $max( l_u , l_v ) \le min( r_u , r_v )$ ). حال او از شما می‌خواهد تا تعداد مجموعه‌های غالب Dominating Set این گراف را بیابید.

مجموعه‌ی $S$ متشکل از تعدادی از رئوس گراف، مجموعه‌ی غالب است اگر و تنها اگر هر راس $v$ در $G$ یا عضو $S$ باشد یا یکی از همسایه‌هایش عضو $S$ باشد.

ورودی🔗

در خط اول ورودی عدد $n$، تعداد بازه‌ها آمده‌است.

در $n$ خط بعدی $l_i$ و $r_i$، شروع و پایان بازه‌ی $i$ ام آمده‌است. $1 \le n \le 5\ 000$ $0 \le l_i \le r_i \le 10\ 000$

خروجی🔗

در تنها سطر خروجی باقی‌مانده‌ی تعداد مجموعه‌های غالب بر $10^9+7$ را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

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

2
1 5
3 3

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

3

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

3
1 3 
2 5
4 6

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

5