#P5457. [THUPC2018] 生生不息

[THUPC2018] 生生不息

题目描述

生命游戏是一个经典的零玩家游戏。

游戏在一块 n×mn \times m 的方格棋盘上进行,初始时,棋盘上的一些格子中有生命,另一些格子中没有生命。

在新的一天开始时,如果一个格子周围的 88 个(边界上的格子也许不到 88 个)格子中,在前一天有恰好22个或33个格子中有生命,则这个格子上的生命可以继续生存,如果周围的格子中恰好有33个格子在前一天有生命且这个格子中前一天没有生命,则会在这个格子中诞生新的生命。在其他情况下,该格子中原有的生命则会死去且不会产生新的生命。

如果在某一天,棋盘上所有的格子里都没有生命,显然,在接下来的时间里,所有的格子中再也不会有生命了,我们就说这些生命灭绝了。

现在,牛牛希望让菲菲来决定游戏开始时棋盘上的每个格子中是否有生命。

而他想知道,在游戏开始时,菲菲有多少种不同的方法使得棋盘上的生命永远也不会灭绝。

输入格式

输入包含多组数据,第一行一个整数 TT 表示数据组数。(T<=30T <= 30

接下来依次描述每组数据,对于每组数据:

  • 一行 22 个正整数 nnmm。(n,m<=5n,m<=5

输出格式

对于每组数据,输出 11 行:

  • 一行输出 11 个整数,表示问题的答案。
2
2 2
3 3
5
150

提示

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。