cf1228B B. Filling the Grid

澹台俊达
2023-12-01

Suppose there is a ℎ×? grid consisting of empty or full cells. Let’s make some definitions:

?? is the number of consecutive full cells connected to the left side in the ?-th row (1≤?≤ℎ). In particular, ??=0 if the leftmost cell of the ?-th row is empty.
?? is the number of consecutive full cells connected to the top end in the ?-th column (1≤?≤?). In particular, ??=0 if the topmost cell of the ?-th column is empty.
In other words, the ?-th row starts exactly with ?? full cells. Similarly, the ?-th column starts exactly with ?? full cells.

These are the ? and ? values of some 3×4 grid. Black cells are full and white cells are empty.
You have values of ? and ?. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of ? and ?. Since the answer can be very large, find the answer modulo 1000000007(109+7). In other words, find the remainder after division of the answer by 1000000007(109+7).

Input
The first line contains two integers ℎ and ? (1≤ℎ,?≤103) — the height and width of the grid.

The second line contains ℎ integers ?1,?2,…,?ℎ (0≤??≤?) — the values of ?.

The third line contains ? integers ?1,?2,…,?? (0≤??≤ℎ) — the values of ?.

Output
Print the answer modulo 1000000007(109+7).

Examples
inputCopy
3 4
0 3 1
0 2 3 0
outputCopy
2
inputCopy
1 1
0
1
outputCopy
0
inputCopy
19 16
16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12
6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4
outputCopy
797922655
Note
In the first example, this is the other possible case.

In the second example, it’s impossible to make a grid to satisfy such ?, ? values.

In the third example, make sure to print answer modulo (109+7).
被Hack了,一场掉灰。。。
记得考虑不成立的情况

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
typedef long long ll;
const ll maxn = 1e3 + 7;
const ll mod = 1e9 + 7;
ll r[maxn],c[maxn];
ll maze[maxn][maxn];
 
ll p[1000007];
 
void init()
{
	p[0] = 1;
	for(ll i = 1;i <= 1000000;i++)
	{
		p[i] = p[i - 1] * 2 % mod;
	}
}
 
int main()
{
	ll h,w;scanf("%lld%lld",&h,&w);
	for(ll i = 1;i <= h;i++)
	{
		scanf("%lld",&r[i]);
	}
	for(ll i = 1;i <= w;i++)
	{
		scanf("%lld",&c[i]);
	}
	memset(maze,-1,sizeof(maze));
	for(ll i = 1;i <= h;i++)
	{
		if(r[i] == 0)
		{
			maze[i][1] = 0;
		}
		else
		{
			for(ll j = 1;j <= r[i];j++)
			{
				maze[i][j] = 1;
			}
		}
	}
	
	for(ll i = 1;i <= w;i++)
	{
		if(c[i] == 0)
		{
			maze[1][i] = 0;
		}
		else
		{
			for(ll j = 1;j <= c[i];j++)
			{
				maze[j][i] = 1;
			}
		}
	}
	
	for(int i = 1;i <= h;i++)
	{
		if(r[i] == 0)
		{
			if(maze[i][1] != 0)
			{
				printf("0\n");return 0;
			}
		}
		else
		{
			int tmp = 0;
			for(int j = 1;j <= w;j++)
			{
				if(maze[i][j] != 1)
					break;
				tmp++;
				if(tmp > r[i])
				{
					printf("0\n");
					return 0;
				}
			}
			if(tmp < r[i])
			{
				printf("0\n");
				return 0;
			}
		}
	}
	
	for(int i = 1;i <= w;i++)
	{
		if(c[i] == 0)
		{
			if(maze[1][i] != 0)
			{
				printf("0\n");
				return 0;
			}
		}
		else
		{
			int tmp = 0;
			for(int j = 1;j <= h;j++)
			{
				if(maze[j][i] != 1)
					break;
				tmp++;
				if(tmp > c[i])
				{
					printf("0\n");
					return 0;
				}
			}
			if(tmp < c[i])
			{
				printf("0\n");
				return 0;
			}
		}
	}
	ll cnt = 0;
	for(ll i = 1;i <= h;i++)
	{
		for(ll j = 1;j <= w;j++)
		{
			if(maze[i][j] == -1)
			{
				ll flag1 = 0,flag2 = 0;
				for(ll ci = i - 1;ci >= 1;ci--)
				{
					if(maze[ci][j] == -1 || maze[ci][j] == 0)
					{
						flag1 = 1;
						break;
					}
				}
				for(ll cj = j - 1;cj >= 1;cj--)
				{
					if(maze[i][cj] == -1 || maze[i][cj] == 0)
					{
						flag2 = 1;
						break;
					}
				}
				if(flag1 && flag2)
					cnt++;
			}
		}
	}
	
	init();
	printf("%lld\n",p[cnt]);
	return 0;
}
 类似资料:

相关阅读

相关文章

相关问答