Есеп D. Көрінбейтін Жанәділдің ағашы

Көрінбейтін Жанәділ осы есепті шығарғысы келеді: $N$ шыңы бар, байланған ағаш беріледі. Берілген ағаштан шыңдар жиынтығын таңдайтын алгоритм бар және осы таңдалған шыңдарды, соның ішінде онымен байланысты қабырғаларды ағаштан кетіретіп тастайды делік. Нәтижесінде $X$ компоненттері бар орман шығады. Сол орманның $i$-ші компоненті $sz_i$ ($1 <= i <= X$) шыңдардан тұратын болады. Сонда бұл алгоритм $$F = \sum_{i=1}^{X} 2^{sz[i]}$$ мәнін қайтарады. Сіздің міндетіңіз барлық ықтимал жиынтықтар бойынша $F$-тің барлық мүмкін мәндерін есептеп қосындысын шығару. Жауапты $10^9 + 7$ санына модульдеп шығарыңыз. Бірінші жолда бір бүтін сан $N$ $(1 <= N <= 2 * 10^5)$ — ағаштағы шыңдар саны берілген. Келесі $N - 1$ жолда екі саннан $u_i$ и $v_i$ ($1 <= u_i <= N$, $1 <= v_i <= N$ и $u_i \neq v_i$) — $u_i$ мен $v_i$ арасындағы қабырға сипаттамасы беріледі. Барлық ықтимал жиынтықтар бойынша $F$-тің соммасын $10^9 + 7$ санына модульдеп шығару. Есеп бес бөлімнен тұрады, әр бөлімде есептің толық шектеулері орындалады:

1. $1 <= N <= 20$. 8 ұпайға есептеледі.
2. $1 <= N <= 200$. 13 ұпайға есептеледі.
3. $1 <= N <= 2000$. 18 ұпайға есептеледі.
4. $1 <= N <= 2 * 10^5$, әр шыңның байланысқан көршілес шыңдар саны екіден аспайды. 14 ұпайға есептеледі.
5. Есептің толық шектеулері. 47 ұпайға есептеледі.

Вход

3
1 2
2 3

Ответ

26

Вход

5
1 2
1 3
5 1
5 4

Ответ

216

Бірінші мысалда $8$ жағдай бар: $F$ мәні $0$, $2$, $2$, $2$, $4$, $4$, $4$, $8$, сондықтан сандар қосындысы = $0 + 2 * 3 + 4 * 3 + 8 = 26$ тең.

Есеп E. НурлашКО

АланашКО мен НурлашКО графом ойнап жатыр, сол себепті сіздің көмегіңіз қажет. Ойын бағытталған, циклдік емес $G$ графынан басталады. Алғашында граф $n$ шыңнан тұрады және граф қабырғасыз болып келеді. Ойын барысында ойнаушылар $q$ операциялар орындайды. Операциялар түрлері осындай:

1. $u_i$ шыңынан $v_i$ шыңына бағытталған қабырға жасау.
2. 1-ші шыңнан $x_i$ шыңына дейін бағытталған қабырғалар арқылы жол табылса, $x_i$ шығарыңыз, табылмаса $0$ шығарыңыз.

Әр операциядан кейін граф циклсыз болатынына кеппілдік беріледі. Бірінші жолда үш бүтін сан $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — шыңдар саны, операциялар саны мен константалық сан енгізіледі. Келесі $q$ жол әр операцияның сипаттамасын береді.

1. Бірінші түрлі операция осылай сипатталады: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
2. Екінші түрлі операция осылай сипатталады: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.

Назар аударыңыз, бірінші операцияға арналған $u_i$, $v_i$ шыңдар номерлері мен екінші операцияға арналған $x_i$ шыңының номері кодталған болып келеді, және оларды алу үшін осындай тағы операциялар орындау қажет: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} $lastans$ — соңғы $2$ операциясынан шыққан жауап (алғашында $lastans$ $0$-тең). Мына жерде $\oplus$ аралас немесе операциясын білдіреді. Осы операция заманғы бағдарламалау тілдерінде ба, мысалға, C++ және Java — ^ арқылы белгіленген, Pascal — $xor$ арқылы. $a \mod b$ операциясы $a$-ның $b$-ға бөлгендегі қалдығын береді. Есепте кемінде бір екінші түрлі операция келетініне кепілдік беріледі. Аралас НЕМЕСЕ($xor$) операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $xor$ $Y$ = $68_{10}$ = $1000100_{2}$. Әр екінші түрлі операцияның жауабын бөлек жолға шығарыңыз. Есеп 5 бөлімнен тұрады:

1. Шарттағы мысалдар. $0$ ұпайға бағаланады.
2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. $11$ ұпайға бағаланады.
3. $n, q <= 10^3$. $18$ ұпайға бағаланады.
4. $t = 0$. $39$ ұпайға бағаланады.
5. Есептің толық шарттары. $32$ ұпайға бағаланады.

Вход

5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3

Ответ

1
0
2
0
4

Вход

5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3

Ответ

1
0
2
0
4

Есеп F. Оңдаңыз!

Барлық сандары теріс емес массивты, Тима жақсы деп есептейді. Тиманың ұзындығы $n$ болатын, бүтін сандардан тұратын $a$ массивы бар. Тима оны жақсы еткісі келеді, сол үшін ол осындай операция істей алады:

• $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ және $a_i \ge x$ орындалатын $i,j, x$ сандарын таңдап алып, $a_i$ санынан $x$ санын азайтып, ал $a_j$ санына $x$ қосу. Осы операцияның құны $|i - j| \cdot x$ теңге.

Қалайда аз теңге қолданып, Тиманың массивын жақсы етіңіз. Бірінші жолда екі бүтін сан $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$ енгізіледі. Екінші жолда $n$ бүтін сан $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$ енгізіледі. $a$ массивын жақсы ете алынуына кепілдік беріледі. Бірінші жолда массивты жақсы етуге құртылған тенге санын шығарыңыз. Егер $type = 1$ болса, екінші жолда бір бүтін сан $k (0 <= k <= 2 \cdot n)$ — операциялар санын шығарыңыз. Келесі $k$ жолда үш саннан $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — операциялар сипаттамасын шығарыңыз. Операциялар санын азайтудың қажеті жоқ, бастысы құртылған тенге санын азайтыңыз. Егер $type = 0$ болса, басқа ештеңе шығарудың керегі жоқ. Есеп сегіз бөлімнен тұрады:

1. Мысалдағы тесттер. 0 ұпайға бағаланады.
2. $n <= 10, type = 0, -1 <= a_i <= 1$. 8 ұпайға есептеледі.
3. $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. 16 ұпайға есептеледі.
4. $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. 12 ұпайға есептеледі.
5. $n <= 2000, type = 0, -1 <= a_i <= 1$. 15 ұпайға есептеледі.
6. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. 13 ұпайға есептеледі.
7. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. 15 ұпайға есептеледі.
8. $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. 21 ұпайға есептеледі.

Вход

7 0
1 1 -1 0 -1 1 1

Ответ

2

Вход

4 1
4 -2 -2 1

Ответ

5
3
1 2 2
1 3 1
4 3 1