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. All rights reserved.

​
≤
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.