electicode
АсосӣКурсҳоМанбаъҳоМасъалаҳо
Ҳамаи масъалаҳо
Khimio
Khayyam Finals 2025

Маҳдуди Сурх/Синӣ

1 сМаҳдудияти вақт
256 МБМаҳдудияти ҳофиза
Ҳамаи ҳалҳо

Тавсифи масъала

Фирдавс ният дорад деворе аз NNN тахта бунёд кунад. Ӯ мехоҳад ҳар як тахтаро ба ранги кабуд ё сурх ранг кунад. Барои ранг кардани як тахта ба Фирдавс дақиқан як банка ранги мувофиқ лозим аст.

Дар ихтиёри Фирдавс MMM дӯстон ҳастанд, ки ҳар кадоми онҳо ба ягон префикси тахтаҳо менигаранд. Дақиқтар, дӯсти iii ба pip_ipi​ тахтаи аввал менигарад, яъне ба тахтаҳои 1,2,…,pi1, 2, \ldots, p_i. Эҳтимол дорад, ки чанд дӯст ба префиксҳои якхела нигаранд.

Ҳал кардан мехоҳӣ?

Ворид шав, кодро ҳамин ҷо навис ва натиҷаро дарҳол бин.

Ворид шудан

electicode© 2026. Ҳамаи ҳуқуқҳо ҳифз шудаанд.

Намуд
1,2,…,pi​

Ҳар як дӯст талабе дорад. Дӯсти iii мехоҳад дақиқан cic_ici​ тахтаи сурх бинад. Мо дӯсти iii-умро хушҳол меномем, агар Фирдавс талабашро қонеъ кунад.

Хушбахтии Фирдавс бевосита аз дӯстонаш вобаста аст. Аз ҳар дӯсти хушҳол ӯ миқдори муайяни хушбахтӣ мегирад. Ба таври расмӣ, хушбахтии Фирдавс суммаи eie_iei​ аз рӯйи ҳамаи дӯстони хушҳоли iii мебошад. Худи Фирдавс кӯшиш мекунад деворашро чунин ранг кунад, ки хушбахтии худро ҳадди аксар намояд.

Фирдавс ҳоло дар бораи сенарияҳои гуногун меандешад. Ӯ намедонад, чанд банка аз ҳар ранг дар ихтиёраш аст. Бигзор F(R,B)F(R, B)F(R,B) ҷавоби савол бошад: Агар дар ихтиёри Фирдавс RRR банка ранги сурх ва BBB банка ранги кабуд мебуд, ҳадди аксар чанд хушбахтӣ мегирифт?

Пас аз андаке андеша, ӯ қарор дод муайян кунад, ки ҷамъбасти хушбахтии ӯ дар ҳамаи сенарияҳои мумкин чӣ қадр мешавад? Яъне, барои ҳамаи ҷуфтҳои R,BR, BR,B ба шартҳои 0≤R,B≤N, N≤R+B0 \leq R, B \leq N, \ N \leq R + B0≤R,B≤N, N≤R+B. Азбаски ҷавоб метавонад хеле бузург шавад, ӯ танҳо бақияи тақсим ба 998244353998244353998244353-ро мехоҳад. Ба таври расмӣ, суммаи зеринро ёбед:

∑R=0N∑B=N−RNF(R,B)mod  998244353\sum_{R = 0}^{N} \sum_{B=N-R}^{N} F(R, B)\mod 998244353∑R=0N​∑B=N−RN​F(R,B)mod998244353

Формати Вуруд

  • Сатри якум як адади бутуни TTT-ро, шумораи тестҳоро, дар бар мегирад.

  • Сипас, барои ҳар як тест:

    • Сатри якум ду адади бутун бо фосила ҷудо кардашуда N,MN, MN,M-ро дар бар мегирад.
    • Сатри дуюм MMM адади бутун p1,p2,…,pM (1≤pi≤N)p_1, p_2, \ldots, p_M \ (1 \leq p_i \leq N)p1​,p2​,…,pM​ (1≤pi​≤N)-ро дар бар мегирад.
    • Сатри сеюм MMM адади бутун c1,c2,…,cM (0≤ci≤pi)c_1, c_2, \ldots, c_M \ (0 \leq c_i \leq p_i)c1​,c2​,…,cM-ро дар бар мегирад.
    • Сатри чорум MMM адади бутун e1,e2,…,eM (0≤ei≤109)e_1, e_2, \ldots, e_M \ (0 \leq e_i \leq 10^9)e1​,e2​,…,eM-ро дар бар мегирад.

Маҳдудиятҳо

Бигзор SN,SMS_N, S_MSN​,SM​ — суммаи умумии NNN ва MMM дар ҳамаи тестҳо мутаносибан бошанд.

  • 1≤T≤1031 \leq T \leq 10^31≤T≤103
  • 1≤N≤1091 \leq N \leq 10^91≤N≤109
  • 1≤SM≤2⋅1051 \leq S_M \leq 2 \cdot 10^51≤SM​≤2⋅105

Формати Баромад

Барои ҳар як тест як сатр чоп намоед, ки як адади бутун — ҷавобро дар бар мегирад.

Системаи баҳодиҳӣ

ЗервазифаҳоМаҳдудиятҳои иловагӣХолҳоЗервазифаҳои зарурӣ
000Намуна000-
111SN≤20S_N \le 20SN​≤20777000
222SN≤2⋅103, M=1S_N \le 2 \cdot 10^3, \ M = 1SN​≤2⋅103, M=1
333SN≤2⋅105, M=1S_N \le 2 \cdot 10^5, \ M = 1SN​≤2⋅105, M=1
444M=1M = 1M=17772,32, 32,3
555SN≤2⋅103S_N \le 2 \cdot 10^3SN​≤2⋅103111111
666SN≤2⋅105, SM≤2⋅103S_N \le 2 \cdot 10^5, \ S_M \le 2 \cdot 10^3SN​≤2⋅105, S
777SM≤2⋅103S_M \le 2 \cdot 10^3SM​≤2⋅103111111
888SN≤2⋅105S_N \le 2 \cdot 10^5SN​≤2⋅105888
999-3232320,1,2,3,4,5,6,7,80, 1, 2, 3, 4, 5, 6, 7, 80,1,2,3,4,5,6,7,8

Мисолҳо

Мисол 1
Вуруд
2 5 5 3 2 5 5 2 2 2 1 0 1 8 10 5 6 6 5 5 5 4 5 4 1 4 3 1 0 0 4 9 8 9 7
Баромад
344 415
​
 
(
0
≤
ci​≤
pi​)
​
 
(
0
≤
ei​≤
109)
55
5
-
66
6
222
0,20, 2
0,2
M
​
≤
2⋅
103
131313
0,2,30, 2, 30,2,3
2,3,4,62, 3, 4, 6
2,3,4,6
0,1,2,3,5,60, 1, 2, 3, 5, 6
0,1,2,3,5,6