Решение задачи Заполнение таблицы с Codeforces
Без пояснения   Просмотров: 136
Предположим, что есть прямоугольная таблица h×w, которая состоит из белых и черных ячеек. Определим следующее:
ri — Количество подряд идущих черных ячеек, с которых начинается i-я строка при просмотре слева направо (1≤i≤h). В частности, ri=0, если крайняя левая ячейка i-й строки является белой.
cj — Количество подряд идущих черных ячеек, с которых начинается j-й столбец при просмотре сверху вниз (1≤j≤w). В частности, cj=0, если самая верхняя ячейка j-го столбца является белой.
Иными словами, если i-я строка начинается ровно с ri черных ячеек. Аналогично, j-й столбец начинается ровно с cj черных ячеек.
Даны r и c. Изначально все ячейки белые. Найдите количество способов заполнить ячейки так, чтобы в заданной таблице значения r и c были равны заданным. Поскольку ответ может быть очень большим, найдите по модулю 1000000007(109+7). Другими словами, найдите остаток от деления ответа на число 1000000007(109+7).
ri — Количество подряд идущих черных ячеек, с которых начинается i-я строка при просмотре слева направо (1≤i≤h). В частности, ri=0, если крайняя левая ячейка i-й строки является белой.
cj — Количество подряд идущих черных ячеек, с которых начинается j-й столбец при просмотре сверху вниз (1≤j≤w). В частности, cj=0, если самая верхняя ячейка j-го столбца является белой.
Иными словами, если i-я строка начинается ровно с ri черных ячеек. Аналогично, j-й столбец начинается ровно с cj черных ячеек.
Даны r и c. Изначально все ячейки белые. Найдите количество способов заполнить ячейки так, чтобы в заданной таблице значения r и c были равны заданным. Поскольку ответ может быть очень большим, найдите по модулю 1000000007(109+7). Другими словами, найдите остаток от деления ответа на число 1000000007(109+7).