electicode
АсосӣКурсҳоМанбаъҳоМасъалаҳо
...

Аквилла

Маҳдудияти вақт: 2000msМаҳдудияти ҳофиза: 512MB
Ҳамаи ҳалҳо

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

Ба шумо пайдарпаии NNN ҷуфтҳои ададҳои натуралӣ (di,vi)(d_i, v_i)(di​,vi​) дода шудааст, барои iii аз 111 то NNN.

Зерпаиҳамии индексҳо 1≤i1<i2<⋯<ik≤N1 \leq i_1 < i_2 < \cdots < i_k \leq N1≤i1​<i2​<⋯<ik​ номида мешавад, агар барои ҳар ду индекси пайдарпай ва , ки , фарқияти ба тақсимшаванда бошад.

Вазифаи шумо муайян кардани суммаи ҳосилзарбҳои vi1×vi2×…×vikv_{i_1} \times v_{i_2} \times \ldots \times v_{i_k}vi1​​×vi2​​ аз рӯи ҳамаи зерпайдарпаҳои зираки ғайрихолӣ, боқимонда аз рӯи мебошад.

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

Файли вуруд дар сатри аввал адади натуралии NNN (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^51≤N≤2⋅105)-ро дар бар мегирад.

Сатри дуюм NNN адади натуралӣ d1,d2,…,dNd_1, d_2, \ldots, d_Nd1​,d2​,…,dN​ ()-ро, ки бо фосила ҷудо шудаанд, дар бар мегирад.

Сатри сеюм NNN адади натуралӣ v1,v2,…,vNv_1, v_2, \ldots, v_Nv1​,v2​,…,vN​ ()-ро, ки бо фосила ҷудо шудаанд, дар бар мегирад.

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

Баромад бояд як адади натуралиро дар бар гирад, ки суммаи ҳосилзарбҳои ҳамаи зерпайдарпаҳои зираки ғайрихолӣ, боқимонда аз рӯи 109+710^9 + 7109+7-ро ифода мекунад.

Баҳогузорӣ

ЗервазифаХолҳоМаҳдудиятҳо
111666N≤20N \leq 20N≤20
2221313

Мисолҳо

Мисол 1
Вуруд
3
2 3 2
1 10 100
Баромад
211
Шарҳ

Мо N=3N = 3N=3 ҷуфт дорем: (2,1)(2, 1)(2,1), (3,10)(3, 10)(3,10) ва (2,100)(2, 100).

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

≤
N
зирак
ipi_pip​
ip+1i_{p+1}ip+1​
1≤p<k1 \leq p < k1≤p<k
ip+1−ipi_{p+1} - i_pip+1​−ip​
min⁡(dip,dip+1)\min(d_{i_p}, d_{i_{p+1}})min(dip​​,dip+1​​)
×
…×
vik​​
109+710^9 + 7109+7
1≤di≤1091 \leq d_i \leq 10^9
1≤di​≤109
1≤vi≤1091 \leq v_i \leq 10^9
1≤vi​≤109
13
N≤2⋅103N \leq 2 \cdot 10^3N≤2⋅103
333777N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 ва di=1d_i = 1di​=1 барои ҳар 1≤i≤N1 \leq i \leq N1≤i≤N
444777N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 ва 1≤di≤21 \leq d_i \leq 21≤di​≤2 барои ҳар 1≤i≤N1 \leq i \leq N1≤i≤N
555141414N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 ва 1≤di≤2001 \leq d_i \leq 2001≤di​≤200 барои ҳар 1≤i≤N1 \leq i \leq N1≤i≤N
666121212N≤105N \leq 10^5N≤105 ва пайдарпаии ddd афзоянда аст
777222222N≤105N \leq 10^5N≤105
888191919Ягон маҳдудияти иловагӣ нест
(2,100)

Биёед ҳамаи зерпайдарпаии имконпазири ғайрихолии индексҳоро таҳлил кунем:

  • (1)(1)(1): мувофиқ аз рӯи таъриф, зеро он танҳо як унсур дорад. Ҳосилзарб v1=1v_1 = 1v1​=1 аст.
  • (2)(2)(2): мувофиқ. Ҳосилзарб v2=10v_2 = 10v2​=10 аст.
  • (3)(3)(3): мувофиқ. Ҳосилзарб v3=100v_3 = 100v3​=100 аст.
  • (1,2)(1, 2)(1,2): фарқи индексҳо 2−1=12 - 1 = 12−1=1 аст. Ҳамчунин, min⁡(d1,d2)=min⁡(2,3)=2. \min(d_1, d_2) = \min(2, 3) = 2. min(d1​, Азбаски ба тақсим намешавад, ин зерпайдарпаӣ зирак нест.
  • (2,3)(2, 3)(2,3): фарқи индексҳо 3−2=13 - 2 = 13−2=1 аст. Ҳамчунин, min⁡(d2,d3)=min⁡(3,2)=2. \min(d_2, d_3) = \min(3, 2) = 2. min(d2​, Азбаски ба тақсим намешавад, ин зерпайдарпаӣ зирак нест.
  • (1,3)(1, 3)(1,3): фарқи индексҳо 3−1=23 - 1 = 23−1=2 аст. Ҳамчунин, min⁡(d1,d3)=min⁡(2,2)=2. \min(d_1, d_3) = \min(2, 2) = 2. min(d1​, Азбаски ба тақсим мешавад, ин зерпайдарпаӣ зирак аст. Ҳосилзарб
  • (1,2,3)(1, 2, 3)(1,2,3): азбаски ҷуфтҳои ҳамсояи (1,2)(1, 2)(1,2) ва (2,3)(2, 3)(2,3) шартро қонеъ намекунанд, ин зерпайдарпаӣ зирак нест.

Аз ин рӯ, ҷамъбасти ҳосилзарбҳои ҳамаи зерпайдарпаии зирак баробар аст ба 1+10+100+100=211.1 + 10 + 100 + 100 = 211.1+10+100+100=211. Пас, ҷавоб 211 mod (109+7)=211211 \bmod (10^9 + 7) = 211211mod(109+7)=211 мебошад.

d
2​
)
=
min(2,3)=
2.
111
222
d
3​
)
=
min(3,2)=
2.
111
222
d
3​
)
=
min(2,2)=
2.
222
222
v1⋅v3=1⋅100=100. v_1 \cdot v_3 = 1 \cdot 100 = 100. v1​⋅v3​=1⋅100=100.