A2586. 白金元首与莫斯科
编程题
NOI/NOI+/CTSC
知识点
题目描述
> 莫斯科吹的寒风 / 仿佛昨日那场梦 / 啊 你还会记得我吗
1941.12.
寒冷刺骨的天气、疲惫不堪的军队…… 包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了，元首 Adolf 想道。在一个 $n \times m$ 的网格区域中存在一个陆军单位需要补给，区域中的每个格子为空地或障碍物中的一种。航空舰队需要派遣若干运输机前往此区域，每一架运输机可以向两个相邻（有一条公共边）的空地投放物资。为防止不必要的损坏，一个标记为空地的格子至多只能得到一次投放。
由于天气原因，陆军单位所在的确切位置并不能确定。因此元首想知道，对于每个空地格子，当陆军单位在其中（视作障碍物）时，用若干（可以为 $0$）架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同，当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放，或存在两个被投放的格子，在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问，请参考【样例 1 解释】。
你需要编写程序帮助元首计算这些值。
1941.12.
寒冷刺骨的天气、疲惫不堪的军队…… 包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了，元首 Adolf 想道。在一个 $n \times m$ 的网格区域中存在一个陆军单位需要补给，区域中的每个格子为空地或障碍物中的一种。航空舰队需要派遣若干运输机前往此区域，每一架运输机可以向两个相邻（有一条公共边）的空地投放物资。为防止不必要的损坏，一个标记为空地的格子至多只能得到一次投放。
由于天气原因，陆军单位所在的确切位置并不能确定。因此元首想知道，对于每个空地格子，当陆军单位在其中（视作障碍物）时，用若干（可以为 $0$）架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同，当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放，或存在两个被投放的格子，在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问，请参考【样例 1 解释】。
你需要编写程序帮助元首计算这些值。
输入格式
第 $1$ 行：两个空格分隔的正整数 $n, m$ —— 网格区域的行数和列数。
接下来 $n$ 行：其中第 $i$ 行包含 $m$ 个空格分隔的整数 $A_{i1}, A_{i2}, \ldots, A_{im}$ —— 其中 $A_{ij} = 0$ 表示第 $i$ 行第 $j$ 列的格子为空地；$A_{ij} = 1$ 表示该格为障碍物。
接下来 $n$ 行：其中第 $i$ 行包含 $m$ 个空格分隔的整数 $A_{i1}, A_{i2}, \ldots, A_{im}$ —— 其中 $A_{ij} = 0$ 表示第 $i$ 行第 $j$ 列的格子为空地；$A_{ij} = 1$ 表示该格为障碍物。
输出格式
输出 $n$ 行，第 $i$ 行包含 $m$ 个空格分隔的整数 $B_{i1}, B_{i2}, \ldots, B_{im}$ —— 若第 $i$ 行第 $j$ 列的格子为空地，$B_{ij}$ 为该格变为障碍物后投放的方案数；否则 $B_{ij} = 0$。每个答案对 $10^9+7$ 取模。
输入输出样例
输入 #1
2 4 0 0 0 0 0 0 0 1
输出 #1
14 13 10 22 15 11 17 0
输入 #2
4 5 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0
输出 #2
1882 827 1523 0 0 0 1189 791 1529 0 0 1106 979 823 1315 1810 899 1136 1075 1189
说明/提示
#### 输入输出样例 1 解释
以第 $2$ 行第 $1$ 列的**空地**格为例，其变为**障碍物**后的网格如下图，其中o格子代表**空地**，x格子代表**障碍物**。
```
ｏｏｏｏ
ｘｏｏｘ
```
#### 数据规模与约定
**本题采用捆绑测试，各测试点信息如下**：
| 子任务编号 | 分值 | $n$ | $m$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $\le 2$ | $\le 17$ |
| $2$ | $8$ | $\le 5$ | $\le 5$ |
| $3$ | $6$ | $\le 9$ | $\le 9$ |
| $4$ | $9$ | $\le 12$ | $\le 12$ |
| $5$ | $17$ | $\le 15$ | $\le 15$ |
| $6$ | $17$ | $\le 16$ | $\le 16$ |
| $7$ | $33$ | $\le 17$ | $\le 17$ |
对于所有数据，有 $1 \leq n, m \leq 17$，$A_{ij} \in {0, 1}$。
#### 说明
题面与史实不尽相符。
以第 $2$ 行第 $1$ 列的**空地**格为例，其变为**障碍物**后的网格如下图，其中o格子代表**空地**，x格子代表**障碍物**。
```
ｏｏｏｏ
ｘｏｏｘ
```
#### 数据规模与约定
**本题采用捆绑测试，各测试点信息如下**：
| 子任务编号 | 分值 | $n$ | $m$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $\le 2$ | $\le 17$ |
| $2$ | $8$ | $\le 5$ | $\le 5$ |
| $3$ | $6$ | $\le 9$ | $\le 9$ |
| $4$ | $9$ | $\le 12$ | $\le 12$ |
| $5$ | $17$ | $\le 15$ | $\le 15$ |
| $6$ | $17$ | $\le 16$ | $\le 16$ |
| $7$ | $33$ | $\le 17$ | $\le 17$ |
对于所有数据，有 $1 \leq n, m \leq 17$，$A_{ij} \in {0, 1}$。
#### 说明
题面与史实不尽相符。