#6301. 「CodePlus 2018 3 月赛」白金元首与莫斯科

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sparrow

题目描述

莫斯科吹的寒风 / 仿佛昨日那场梦 / 啊 你还会记得我吗

1941.12.

寒冷刺骨的天气、疲惫不堪的军队……包围首都的作战计划陷入了困境。空军或许是拯救战况的最后希望了,元首 Adolf 想道。

在一个 n×mn \times m 的网格区域中存在一个陆军单位需要补给,区域中的每个格子为空地障碍物中的一种。航空舰队需要派遣若干运输机前往此区域,每一架运输机可以向两个相邻(有一条公共边)的空地投放物资。为防止不必要的损坏,一个标记为空地的格子至多只能得到一次投放。

由于天气原因,陆军单位所在的确切位置并不能确定。因此元首想知道,对于每个空地格子,当陆军单位在其中(视作障碍物)时,用若干(可以为 00)架运输机向其余空地投放任意数量的物资的不同方案数。两个投放方案不同,当且仅当存在一个格子在一个方案中被投放而另一方案中未被投放,存在两个被投放的格子,在一个方案中被同一架运输机投放而在另一方案中非然。若仍有疑问,请参考「样例 1 解释」。

你需要编写程序帮助元首计算这些值对 109+710^9+7 取模的结果。

输入格式

从标准输入读入数据。

  • 11 行:两个空格分隔的正整数 n,mn, m —— 网格区域的行数和列数。
  • 接下来 nn 行:其中第 ii 行包含 mm 个空格分隔的整数 Ai1,Ai2,,AimA_{i1}, A_{i2}, \ldots, A_{im} —— 其中 Aij=0A_{ij} = 0 表示第 ii 行第 jj 列的格子为空地Aij=1A_{ij} = 1 表示该格为障碍物

输出格式

输出到标准输出。

对于每组数据输出 nn 行,第 ii 行包含 mm 个空格分隔的整数 Bi1,Bi2,,BimB_{i1}, B_{i2}, \ldots, B_{im} —— 若第 ii 行第 jj 列的格子为空地BijB_{ij} 为该格变为障碍物后投放的方案数;否则 Bij=0B_{ij} = 0

样例

样例 1 输入

2 4
0 0 0 0
0 0 0 1

样例 1 输出

14 13 10 22
15 11 17 0

样例 1 解释

以第 22 行第 11 列的空地格为例,其变为障碍物后的网格如下图,其中白色格子代表空地,黑色格子代表障碍物

Sample Grid

1515 种方案如下图所示,不同颜色代表不同运输机的投放位置。

Sample Ways

样例 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

数据范围与提示

子任务

对于所有数据,有 1n,m171 \leq n, m \leq 17Aij{0,1}A_{ij} \in \{0, 1\}

子任务编号分值nn mm
1102\leq 2 17\leq 17
285\leq 5 5\leq 5
369\leq 9 9\leq 9
4912\leq 12 12\leq 12
51715\leq 15 15\leq 15
61716\leq 16 16\leq 16
73317\leq 17 17\leq 17

Von allem Anfang an bin ich nur verraten und betrogen worden!

题面与史实不尽相符。


来自 CodePlus 2018 3 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/吕时清 命题/吕时清 验题/吕欣,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。