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

یک درخت $n$ راسی به شما داده می شود.

مجموعه $P$ (که می‌تواند تهی باشد) از رئوس درخت را اکبرجوجه مینامیم، اگر برای هر دو عضو متمایز $u$ و $v$ در $P$، هیچ یک از $u$ یا $v$ جد دیگری نباشد.

می گوییم راس $u$ جد راس $v$ است اگر در مسیر $v$ به راس ۱، راس $u$ وجود داشته باشد.

هدف پیدا کردن باقی‌مانده تعداد زیرمجموعه‌های اکبرجوجه از رئوس درخت بر $10^{9} + 7$ می‌باشد، این عدد را در خروجی چاپ کنید.

ورودی🔗

در خط اول ورودی عدد $n$ که به شما داده می‌شود که بیانگر تعداد رئوس گراف است.

سپس در $n-1$ خط ، و در خط $i$ ام، دو عدد $u_{i}$ و $v_{i}$ می‌آید که به معنی یالی بین این دو راس است.

تضمین می‌شود گراف ورودی درخت است.

$1 \le n \le 100\ 000$$1 \le u_{i} , v_{i} \le n$

خروجی🔗

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

مثال🔗

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

4
1 2
2 3
3 4

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

5

شرح ورودی و خروجی نمونه شماره یک : مجموعه موردنظر حداکثر می‌تواند شامل یک راس باشد که خود چهار حالت دارد و یک حالت هم مجموعه تهی است، پس پاسخ برابر پنج است.

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

4
1 2
1 3
1 4

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

9

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

درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم $\frac {a_i} {b_i}$ نوشته شده است. درخت به این شکل ساخته می‌شود:

1. $a_{1}$ = $b_{1}$ = $1$
2. $a_{2i}$ = ($a_{i}$ + $b_{i}$ ) , $b_{2i}$ = $b_{i}$ (بچه سمت چپ)
3. $a_{2i+1}$ = $a_{i}$ , $b_{2i+1}$ = ($a_{i}$ + $b_{i}$ ) (بچه سمت راست)

فاصله دو راس در درخت را تعداد یال‌های تنهای مسیر بینشان تعریف می‌کنیم.

به شما $Q$ درخواست که هر کدام شامل کسری به فرم $\frac {p_i} {q_i}$ داده می‌شود.

برای هر عدد موجود در درخواست‌ها، اگر تنها یک راس در درخت وجود داشت که کسرش برابر کسر ورودی داده شده بود، فاصله راس آن کسر تا راس ۱ را در خروجی چاپ کنید و در غیر این صورت $-1$ خروجی دهید.

ورودی🔗

در خط اول $Q$ و در $Q$ خط بعدی$p_{i}$ و $q_{i}$ به شما داده شده.

$1 \le Q \le 100\ 000$

$1 \le p_{i},q_{i} \le 10^{18}$

خروجی🔗

در خط $i$ام اگر کسری معادل عدد $\frac {p_i} {q_i}$ بود و فقط این کسر معادل این عدد بود فاصله‌ی آن را از راس ۱ خروجی دهید در غیر این صورت $-1$ خروجی دهید.

مثال🔗

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

2
1 2
3 5

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

1
3

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

دنباله ولایی، یک دنباله به طول $n$ از اعداد حسابی به صورت $a_{0},a_{1},....,a_{n-1}$ است که $a_{i}$ برابر تعداد تکرارهای عدد $i$ در دنباله‌ی $a$ است.

برای مثال دنباله $2,0,2,0$ این خاصیت را دارد زیرا تعداد ۰ های دنباله برابر با ۲، تعداد ۱ های دنباله برابر با ۰، تعداد ۲ های دنباله برابر با ۲ و تعداد ۳ های دنباله برابر با ۰ است.

عدد $n$ به شما داده شده، دنباله‌های ولایی به طول $n$ را چاپ کنید.

ورودی🔗

در تنها خط از ورودی عدد $n$ داده شده. $1 \le n \le 1\ 000$

خروجی🔗

در اولین خط از خروجی تعداد دنباله های ولایی به طول $n$ را چاپ کنید. سپس در خطوط بعدی، در هر خط یک دنباله ولایی را چاپ کنید. دنباله ها باید به ترتیب کتابخانه ای خروجی داده شوند.

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

مثال🔗

ورودی نمونه🔗

1

خروجی نمونه🔗

0

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

تابع $f(i , j)$ روی آرایه‌ی $a$ به طول $n$ به این شکل تعریف می‌شود:

1. $f(i , i) = a_{i}$
2. $f(i , j) = max( f(i+1 , j) , f(i , j-1) , min( a_{i} , a_{i+1} , ... , a_{j} ) \times (j-i+1) ) (i<j)$

به شما $Q$ جفت عدد داده می‌شود.

هر جفت دارای دو عدد $l_{i}$ و $r_{i}$ است.

مقدار زیر را خروجی دهید:

$max( f(l_{1} , r_{1}) , f(l_{2} , r_{2}) , ... , f(l_{Q} , r_{Q}) )$

ورودی🔗

در خط اول دو عدد $n$ و $Q$ داده می‌شود.

در خط بعدی $n$ عدد $a_{1}$ تا $a_{n}$ داده می‌شود.

در $Q$ خط بعدی$l_{i}$ و $r_{i}$ به شما داده می‌شود.

$1 \le Q,n \le 1\ 000\ 000$

$1 \le a_{i} \le 1\ 000\ 000\ 000$

$1 \le l_{i} \le r_{i} \le n$

تضمین می‌شود تمام اعداد آرایه $a$ متمایزند.

خروجی🔗

مقدار خواسته شده را خروجی دهید.

مثال🔗

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

5 2
1 4 3 5 2
1 3
3 5

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

6

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

آرایه ای به طول $n$ داریم. هر عضو از این آرایه یک رشته به طول $k$ است که از ۰ و ۱ تشکیل شده است (رشته باینری به طول $k$).

رشته خفن یک بازه از آرایه، یک رشته به طول $k$ است که بیت $i$ام آن برابر با ۱ است اگر حداقل یکی از رشته های بازه، بیت $i$امش برابر با ۱ باشد.

عدد بوگندوی یک رشته برابر با تعداد بیت های ۱ آن است.

به شما $q$ درخواست داده می‌شود و در هر مرحله دو عدد $l,r$ داده می‌شود و شما باید عدد بوگندوی رشته خفن بازه $[l,r]$ را چاپ کنید.

ورودی🔗

به دلیل حجم زیاد ورودی، ورودی به یک روش غیر معمول داده می‌شود:

در سطر اول سه عدد $n$ و $m$ و $k$ آمده است.

در $m$ خط بعدی، در هر خط ابتدا یک رشته $k$ بیتی $s_{i}$ آمده. سپس یک عدد $cnt_{i}$ آمده و $cnt_{i}$ عدد $index_{ij}$ آمده که بیانگر این است که رشته موجود در خانه ی $index_{ij}$ از آرایه برابر با $s_{i}$ است. تضمین می‌شود که هر خانه از آرایه دقیقا یکبار به عنوان $index$ ظاهر می‌شود.

در خط بعدی عدد $q$ آمده است. سپس در $q$ خط بعدی به شما درخواست‌ها به صورت دو عدد $l,r$ داده می‌شود که باید به آنها جواب دهید. $1 \le l \le r \le n \le 100 \ 000$ $1 \le m \le 1\ 000$ $1 \le k \le 3\ 000$ $1 \le q \le 1\ 000\ 000$

خروجی🔗

در $q$ خط جواب هر درخواست را چاپ کنید.

مثال🔗

ورودی نمونه🔗

8 7 5
10001 1 5
10100 1 1
10001 1 3
00100 1 8
00011 1 7
11000 2 2 4
01110 1 6
8
8 8
1 3
3 5
5 6
8 8
6 8
8 8
3 6

خروجی نمونه🔗

1
4
3
5
1
4
1
5

اعضای آرایه به این صورت اند : $10100,11000,10001,11000,10001,01110,00011,00100$ در درخواست اول فقط عضو هشتم رشته آمده که تعداد بیت‌های ۱ اش برابر با یک است.

در درخواست دوم اعضای ۱ تا ۳ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم، سوم و پنجم اش برابر با ۱ اند.

در درخواست سوم اعضای ۳ تا ۵ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم و پنجم اش برابر با ۱ اند.