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;
}