F: не знаю авторского, но в ТЛ с хорошим запасом заходит квадрат: для каждой длины префикса i перебрать сдвиг второго префикса относительно первого и проверить, равны ли соответствующие подстроки двумя посчитанными z-функциями.

D: пусть фиксировано q (количество максимумов), и массив отсортирован по убыванию. Ответ для q — (считаем вклад каждого элемента, один коэффициент — сколько больших элементов взяли в подпоследовательность, второй — взяли любые из меньших). Если поменять местами порядок суммирования и раскрыть биномиальный коэффициент, то при желании можно увидеть, какие два полинома нужно перемножить фурьешкой, чтобы получить ответ для всех q.

D: Пусть числа a₀ ≥ a₁ ≥ ... ≥ a_n - 1. Тогда вклад a_j в полную i-ценность коллекции есть (где , если x > y). Получается, что i-ценность коллекции равна . Это префиксные суммы для . Давайте запишем (есть тонкость с j < k, с ней разберёмся попозже). Видим, что . При фиксированном k это уже начинает напоминать свёртку. А именно, посмотрим на "почти многочлены" , (если s > n, то B_- s = 0; если s < 0, то B_- s = 0, видно, что этого достаточно, чтобы разобраться со случаем k > j). Тогда при фиксированном k это коэффициент произведения этих "многочленов" при x^k. Для того, чтобы свести это к произведению настоящих многочленов, просто сдвинем коэффициенты B.

F: в зимнем Петрозаводске 2017 (а также в ГП Гомеля в опенкапе) в этом году была задача "найти позиции минимальных циклических сдвигов для всех префиксов строки". Если мы умеем это делать, то можно просто сравнивать эти минимальные циклические сдвиги хэшами (они равны тогда и только тогда, когда префиксы эквивалентны).

C: Подходит многочлен (x - 1)(x - 2)... (x - n) + x. Надо найти произведение. Это можно сделать в стиле divide and conquer: разделим множители на две части, вычислим ответы для каждой и просто перемножим их. f(n) = 2f(n / 2) + O(n²) даёт f(n) = O(n²). А можно и с FFT, наверное.

B: bitset. Будем идти по возрастанию искомого маршрута и поддерживать для каждой строки два битсета: из каких клеток этой строки можно пойти вправо на k и вниз на k. Из этого логическими операциями и сдвигами можно собрать условие на клетку, может ли она быть центром маршрута, и посчитать количество единичных битов в результате.

С: Так как модуль простой и больше n, то подойдёт (x - 1)(x - 2)... (x - n) + x (совпадает с x в точках 1, 2, ..., n и отличается в n + 1). Перемножать можно просто последовательно за квадрат.

B: Отразим картинку относительно диагонали из левого верхнего угла в правый нижний (это неважно, но мне так проще объяснять). Тогда маршрут сперва идёт вниз, потом вправо, потом опять вниз. Для каждой клетки посчитаем, насколько мы можем отойти вверх, не пересекая водоёмов и края поля и насколько можем отойти вниз (массивы u и d). Каждая строка разбивается на максимальные по включению отрезки, на которых нет водоёмов, будем решать для них независимо. Пусть мы находимся на таком отрезке с l по r в i-той строке. Тога мы хотим выбрать целые числа s и q, что l ≤ s < s + 2q ≤ r, при этом u[i][s] >= q и d[i][s + 2q] >= q (соответствует маршруту (i - q, s) -> (i, s) -> (i, s + 2q) -> (i + q, s + 2q)). Давайте переберём s, тогда q может меняться в пределах от 1 до min(u[i][s], (r - s) / 2) и нужно посчитать для скольки q из этого отрезка d[i][s + 2q] >= q. Это запрос вида "на отрезке посчитать число позиций, x фиксированной чётности, для которых d[i][x] - (x / 2) >= -(s / 2)". Если хранить два дерева отрезков для каждой чётности и перебирать s в порядке возрастания (при этом будут появляться новые хорошие значения x), то получается решение за . У меня без упихивания зашло в дорешку.