Кстати, а у нее есть решение побыстрее, без разбития по вопросам?

Я тоже так делал) ИМХО, это очень просто и мало кода.

BFS пройдет, если работать не со строками, а только с числами. Сразу получается значительное ускорение

Давайте рассмотрим все варианты распределения N на r,g,b — красных, зеленых и синих. Переберем r,g в цикле (b=n-r-g). Для каждого варианта: пусть мы определили r,g,b, тогда количество вариантов такого распределения полоски равно C(r, n) * C(g, n - r) * C(b, n - r - g), но b = n - r - g, т.е. С(b, n - r - g) = 1.

Чтобы не вычислять каждый раз число перестановок через факториалы, используйте треугольник Паскаля. Псевдокод:

#Читаем данные, строим тр. Паскаля
for r in [Rmin, N - Gmin - Bmin]:
 for g in [Gmin, N - r - Bmin]:
  ans = (ans +C[r,N]*C[g,N-r]) % MOD

Итоговая сложность: N^2

Вроде тупо перебор за квадрат заходил

Если просто после каждого запроса поставить крестик проверять по горизонтали, по вертикали, и по двум диагоналям максимальный ряд из крестиков, все тесты не пройдет, на нескольких будет TL. Но, можно поставить пару примочек(условий) на проверку, надо ли дальше проверять, хватит ли вообще клеток на дополнение ряда, и собственно не проверять, когда этот ряд обречен на провал, тогда решение заметно ускорится и пройдет все тесты.

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

Я писал фенвика. У меня было четыре фенвика: 1)для вертикалей 2)для горизонталей 3)для диагоналей двух типов, которые идут вниз и вверх. Когда мы ставим крестик, то нам имеет смысл проверять только лишь ту горизонталь, вертикаль и диагональ, куда мы его поставили, да так, чтобы наш крестик был среди нужной длины последовательности. Итого получаем сложность O(M*K*logN) и небольшая константа. Прошу заметить, если делать без фенвика, то сложность получится O(M*K^2). Однако мое решение получило на двух тестах TLE. :(