Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 63 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 7 8 9 10 11 12 13 Отображать по:
#113579
Пианистка Перика
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Пианистка Перика ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.

Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.

Входные данные

В первой строке содержатся два целых числа N и K ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 50 ). Во второй строке содержатся N целых чисел a i ( 0 ≤ a i ≤ 10 9 ) - числа на клавишах пианино.

Выходные данные

В единственной строке выведите одно целое число - ответ на вопрос Перики по модулю 1000000007.

Примечание

Решения, работающие при 1 ≤ N ≤ 1000 , будут оцениваться в 40 баллов.

Примеры
Входные данные
5 3
2 4 2 3 4
Выходные данные
39
Входные данные
5 1
1 0 1 1 1
Выходные данные
4
Входные данные
5 2
3 3 4 0 0
Выходные данные
31
#113581
Массивы, числа, три хеша
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Массивы, числа, три хеша ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .

Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s )  =  ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.

Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .

Входные данные

В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).

Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).

Гарантируется, что во всех тестах K ≤ 2 N - 1 .

Выходные данные

Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .

Примечание

Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.

Примеры
Входные данные
2 3 1 5
1 2
Выходные данные
1 1
3 2
2 1
Входные данные
3 4 2 3
1 3 1
Выходные данные
1 1
1 1
0 2
2 2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1 1
25 2
25 2
577 3
274 4
578 3
#113588
Специфический сон
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Специфический сон ]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
512 megabytes

Анике приснился необычный сон. В нем она увидели бесконечную доску. На той доске бесконечно много строк и бесконечно много столбцов, содержащих бесконечно много чисел. Что интересно, каждое число появляется на доске конечное число раз.

Оказывается, доска соответствует вполне понятным рекурсивным правилам. Первая клетка каждой строки содержит номер этой строки (начиная с 1). Значение же в каждой последующей клетке равно сумме значения в предыдущей клетке и перевернутого значения в предыдущей клетке. Перевернутое число можно получить, если записать в обратном порядке цифры десятичного представления числа.

Формально, если A ( i , j ) - значение в i -й строке и j -м столбце доски, то:

1. A ( i , 1) = i

2. A ( i , j ) = A ( i , j - 1) + rev ( A ( i , j - 1)) , если j > 1 .

rev ( x ) - операция разворота числа в его десятичном представлении. Например, rev (345) = 543 , а rev (1040) = 0401 = 401 .

Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа A и B , а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне [ A : B ] ".

Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.

Входные данные

Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) - количество вопросов.

Каждая из последующих Q строк содержит два целых числа A и B ( 1 ≤ A ≤ B ≤ 10 10 ) - вопросы Бозо.

Выходные данные

Выведите Q строк, в каждой одно целое число - ответ на соответствующий вопрос Бозо.

Примечание

Решения, работающие при A , B ≤ 10 6 , будут оцениваться в 50 баллов.

Примеры
Входные данные
2
1 10
5 8
Выходные данные
18
8
Входные данные
3
17 144
121 121
89 98
Выходные данные
265
25
10
Входные данные
1
1 1000000000
Выходные данные
1863025563
Страница: << 7 8 9 10 11 12 13 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест