Основной факт заключается в том, что модуль по которому нужно брать ответ для задачи - простое число (10^9 + 7). Думаю без этого факта задачу невозможно было бы решить за полиномиальное время. Зная применение малой теоремы Ферма можно спокойно решить задачу обычной динамикой.
А именно: чтобы вычислить значение (A/B)%C, воспользуемся фактом что B^(C - 1)%C = 1, (по малой теореме Ферма, C - простой модуль). (A/B)%C == ( (A * B^(C - 2)) / (B^(C - 1)) )%C . B^(C - 1) мы можем убрать из знаменателя, так как он сравним с единицей по модулю С. Отсюда (A/B)%C = (A * B^(C - 2))%C.
Идея динамики заключается в следующем: d[i, j] = кол-во палиндромов длины i, используя первые j символов алфавита из заданной строки.
Теперь о том как считать динамику.
Перебираем j
Для некоторого j перебираем длину строки (i) которую мы будем апдейтить.
Перебираем кол-во символов j которые мы добавим в строку (k). k от 0 до кол-во j в изначальной строке.
d[i + k, j] = d[i, j] * (k!)^(C - 2) * (i+k)! * (i!)^(C - 2);
Если i%2 == 0 и кол-во символов j в изначальной строке > 0 (значит можно добавить текущий символ в центр строки)
d[i + 1, j] = d[i, j];
Ответом на задачу будет d[n, 26]
На заметку: все вычисления нужно делать по модулю C.
Пуст f[i] хранит кол-во k-based чисел длины i. В таком случае можно сделать реккурентную формулу f[i] = (k - 1)f[i - 1] + (k - 1)f[i - 2] = (k - 1)*(f[i - 1] + f[i - 2]). Т.е. мы можем просто любую цифру от 1 до к - 1 к k-based числам длины i-1, а также можем дописать 0 и любую цифру от 1 до к - 1 к k-based числам длины i-2. Так что ответом будет f[n].
Воспользуемся стандартным алгоритмом Куна. Описание его работы и реализацию можно найти на emaxx например. http://e-maxx.ru/algo/kuhn_matching
Найдем кратчайшие расстояния от каждой до каждой вершины алгоритмом Флойда. Теперь просто суммируем кратчайшие расстояния всех пар вершин и поделим на кол-во пар вершин (учитывая что пути может и вовсе не быть).
Найдем все возможные кол-ва палочек которые образуют проигрышный для игрока стол. Можно делать так: один параметр - кол-во текущих палочек, далее пробуем взять какое-то кол-во палочек после этого мы попадаем в какое-то состояние если оно проигрышное значит текущее выигрышное, результат запоминаем. Далее сделаем простой рюкзак по этим кол-вам (проигрышным от 1 до n - 1). Если достигли n, и при этом кол-во использованных столов > 1. Тогда восстанавливаем ответ.
Матрица симметрична относительно главной диагонали, только в случае когда для любых i и j a[i][j] = a[j][i]. Осталось это проверить.
Нам надо знать какое минимальное кол-во символов может принимать длина новой строки и её саму. Для этого для каждого подотрезка будем вычеслять эти данные. При этом сначала для каждого подотрезка проверяем можем ли мы его разбить на одинаковые подподотрезки (КМП например). После чего используем ленивую динамику. А именно пытаемся разбить текущий отрезок в какой-то точке на два и посмотрим длины для обеих частей, и из всех таких разбиений выберем наименьшее по длине. Как восстановить ответ додумайте сами.
Нужно понять что d(xy) = d(x)d(y). Тогда понятно что начиная с какого-то p, последующие d(i!) = 9 (i > p). Потому что d(9*x) всегда = 9. Этот p = 5.
Ну, задача не сложная, нужно проверить лежит ли точка в выпуклом многоугольнике. Строить оболочку не надо, она и так построена, осталось лишь суметь за "быстро" проверять. Можно сделать бинарный поиск. Будем брать l, r и сравнивать векторным произведением вектор из первой точки в (l + r)/2 с вектором из первой точки в точку запроса, если оборот по часовой стрелке, сдвигаем r в (l + r)/2 иначе наоборот. В конечном счете у нас будут два соседних вектора(точки) l и r. Осталось проверить лежит ли сторого точка запроса в треугольнике lrb, где b это первая точка.
Чтобы решить данную задачу, нужно уметь быстро пересекать числовые отрезки. Можно использовать декартово дерево. При получении какого-то отрезка l, r будем находить концы которые входят в данный отрезок (и начала, и концы) и удалять. После чего найдем первый конец левее l и проверим его другой конец находится после l или нет. Если да, то значит есть пересечение и можно удалить эту точку. Далее повторим это и для перого конца правее r. В итоге мы будем поддерживать нужные отрезки.
Доказательство:
Когда мы удаляем все точки на отрезке l, r, может быть максимум две точки которые со своими парами пересекают l и r. Потому что до этого момента наши отрезки были непересекаемыми. Далее когда мы удаляем слева от l и справа от r мы избавляемся от случая когда есть эти пересечения. Еще один случай, это когда наш l и r лежит внутри какого-то отрезка. Тогда кол-во точек от l до r = 0. Потому что нет пересечений существующих отрезков. Т.е. последними проверками мы обходим и этот случай. ч.т.д.
Из условия понятно, что задача сводится к проверке пересечения выпуклого многоугольника построенного из станций метро и самих шоссе, которые являются прямыми. Теперь, что нам нужно сделать так это построить эту оболочку, далее научиться проверять за быстро). Это можно сделать тернарным поиском: разобьем многоугольник на две полудуги. Для каждой полудуги будем пускать тернарный на расстояние от точки до прямой учитывая знак расстояния (мин. и макс.). Понятно, что функция расстояния будет монотонна в двух местах. Теперь сравним знаки минимумов и максимумов которые мы нашли. Если есть различные знаки или же нуль, тогда есть пересечение, в противном случае нет.