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), то получается решение за . У меня без упихивания зашло в дорешку.