Решение задачи Заполнение таблицы с 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).

Код 

//besmellah
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 2, mod = 1e9 + 7;
int a[maxn], b[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	long long ans = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (i < b[j]){
				if (j == a[i])
					ans *= 0;
			}
			else if (i == b[j]){
				if (j < a[i])
					ans *= 0;
			}
			else{
				if (j > a[i]){
					ans *= 2;
					ans %= mod;
				}
			}
		}
	}
	cout << ans;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 mycod   [email protected]  Карта сайта   Правообладателям