Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 512 513 514 515 516 517 518 >> Отображать по:
#113707
Симпатичные прямоугольники наносят ответный удар
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc    a

cb и a

Напишите программу, которая по информации о шедевре Васи определит его стоимость.

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

В первой строке содержатся два числа N и M ( 1 ≤ N , M ≤ 300 ). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i -й строке j -м столбце определяет цвет соответствующего квадратика картины.

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

Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.

Система оценки

n, m < 10 -> 20 баллов

n, m < 50 -> 30 баллов

n, m < 100 -> 20 баллов

n, m < 300 -> 30 баллов

Примечание

Этот пример разобран в условии

Симпатичными являются шесть частей 1 × 1 , одна часть 1 × 2 и сама картина.

Примеры
Входные данные
2 3
abc
acb
Выходные данные
8
Входные данные
3 2
ab
cc
ba
Выходные данные
8
#113710
Маша и Маша.
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Маша и Маша - лучшие подруги. Однажды Маша и Маша пошли по магазинам. Оказалось, что Маша не хочет заходить в каждый a -ый магазин, а Маша в каждый b -ый. Но так как Маша любит Машу как подругу, а Маша как подругу любит Машу, Маша и Маша не заходят в магазин, если в него не хочет заходить ни Маша, ни Маша. В сколько магазинов зайдут Маша и Маша, если на их пути было n магазинов.

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

Единственная строка содержит три целых числа — a , b , n ( 1 ≤ a , b , n ≤ 10 9 )

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

Выведите единственное число — количество посещённых магазинов

Система оценки

Программы, работающие корректно для n ≤ 1000 получат 40 баллов.

Программы, работающие корректно для n ≤ 10000 получат 70 баллов.

Примеры
Входные данные
1 1 10
Выходные данные
0
Входные данные
1 2 5
Выходные данные
3
Входные данные
2 3 9
Выходные данные
8
#113774
Фурье?
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
512 megabytes

Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.

Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .

Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 3 + 2 3 + 1 3 = 27 + 8 + 1 = 36 .

Поскольку задача должна быть интересной, вам нужно посчитать интересность всех чисел от 1 до n по модулю MOD .

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

В единственной строке входных данных задаются два числа n и MOD ( 1 ≤ n ≤ 10 5 , 1 ≤ MOD ≤ 10 9 + 7 ) — максимальное число, для которого надо посчитать интересность, и модуль.

Модуль не обязательно простой.

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

Выведите n строк, в i -й строке должна содержаться интересность числа i по модулю MOD .

Система оценки

Данная задача содержит 8 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.

  1. 1 ≤ n ≤ 5 , 5 баллов.
  2. 1 ≤ n ≤ 10 , 5 баллов.
  3. 1 ≤ n ≤ 20 , 10 баллов.
  4. 1 ≤ n ≤ 100 , 10 баллов.
  5. 1 ≤ n ≤ 1000 , 10 баллов.
  6. 1 ≤ n ≤ 5000 , 10 баллов.
  7. 1 ≤ n ≤ 50 000 , 25 баллов.
  8. 1 ≤ n ≤ 100 000 , 25 баллов.

Примеры
Входные данные
3 998244353
Выходные данные
1
9
36
Входные данные
10 3
Выходные данные
1
0
0
0
2
2
0
2
2
0
#113775
Все на выборы!
  
Ограничение по времени, сек4
Ограничение по памяти, мегабайт512

Я на выборы никогда не ходил, но в этот раз точно пойду за Зигги голосовать. Кандидат от народа!

Вдохновившись трудами греческих философов, Спортакус решил избрать главу правительства в Лентяево. Поскольку греческие философы убедили Спортакуса, что демократия является лучшим видом государственного устройства, он решил провести выборы. Для этого он открыл n избирательных участков, пронумерованных от 1 до n . Известно, что на участке с номером i проголосовали a i жителей Лентяево.

После окончания выборов Спортакус решил подвести некоторую статистику явки на выборах. Спортакус знает множество разных статитстических величин, но наиболее показательной он считает k -ю порядковую статистику, поэтому для некоторых регионов и некоторых значений k Спортакус хочет узнать значение k -й порядковой статистики явок на участках данного региона.

Опишем действия Спортакуса более формально. Регионом с границами l и r Спортакус называет множество избиртельных участков, чьи номера лежат на промежутке от l до r включительно. k -й порядковой статистикой массива чисел супергерой называет число, которое бы находилось на k -й позиции в этом массиве, если бы он был упорядочен по возрастанию.

Стефани огорчает, что явка на выборах не соотетствует её ожиданиям, поэтому она решила слегка изменить значения явок на некоторых участках так, чтобы выборы казались более успешными. Для этого она выбирает четыре числа l , r , x и y и на всех избирательных участках региона с границами l и r , на которых явка равна x меняет протокол, после чего явка на этих участках становится равной y .

Напишите программу, отвечающую на запросы Спортакуса с учётом изменений, которые делает Стефани.

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

В первой строке содержатся два целых числа n и m ( 1 ≤ n , m ≤ 100 000 ) — количество избирательных участков и количество событий.

Во второй строке содержатся n целых чисел ( 1 ≤ a i ≤ n ) — количество людей, проголосовавших на участке с номером i .

В следующих m строках содержатся описания событий. Каждое событие задано в одном из двух форматов.

1 l r x y ( 1 ≤ l ≤ r ≤ n , 1 ≤ x , y ≤ n ) обозначает, что Стефани на всех участках региона с границами l и r и явкой x установила явку равной y .

2 l r k ( 1 ≤ l ≤ r ≤ n , 1 ≤ k ≤ r - l + 1 ) обозначает, что Спортакуса интересует значение k -й порядковой статистики явок на участках в регионе с границами l и r .

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

Для каждого вопроса Спортакуса выведите ответ на него.

Система оценки

Группа 1 (10 баллов) 1 ≤ n , m ≤ 100 . Для прохождения этой подгруппы требуется прохождение тестов из условия.

Группа 2 (10 баллов) 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение тестов из условия.

Группа 3 (10 баллов) 1 ≤ n , m ≤ 100 000 , нет запросов первого типа. Для прохождения этой подгруппы требуется прохождение группы 2.

Группа 4 (20 баллов) 1 ≤ n , m ≤ 100 000 , в запросах первого типа l = r . Для прохождения этой подгруппы требуется прохождение группы 3.

Группа 5 (50 баллов) Без дополнительных ограничений. Для прохождения этой подгруппы требуется прохождение всех предыдущих групп.

Примеры
Входные данные
3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2
Выходные данные
2
1
#113776
Лес
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .

Игра задаётся перестановкой вершин и происходит следующим образом:

  1. Если граф опустел, то игра заканчивается.
  2. Иначе выбирается первая ещё не удалённая вершина в перестановке, после чего
  3. Количество очков увеличивается на размер дерева из которого была выбрана вершина, а затем выбранная вершина и все связанные с ней рёбра удаляются, и тот же процесс продолжается на оставшемся графе.

Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 9 + 7 .

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

В первой строке входного файла дано число N ( 2 ≤ n ≤ 10 5 ) — количество вершин в исходном дереве.

Каждая из последующих N - 1 строк содержит два числа — x i , y i задающих концы соответствующего ребра дерева ( 1 ≤ x i , y i ≤ n ).

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

Выведите одно число — суммарное количество очков по модулю 10 9 + 7 .

Система оценки

Тесты к данной задаче состоят из 3 групп:

  1. (20 баллов) n ≤ 10 .
  2. (40 баллов) n ≤ 5000
  3. (40 баллов) n ≤ 10 5

Примеры
Входные данные
2
1 2
Выходные данные
6
Входные данные
3
1 2
2 3
Выходные данные
34
Страница: << 512 513 514 515 516 517 518 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест