娱乐 奇怪的算法挑战【第①期】拼图游戏

[Muriya Tensei]

（开幕雷击，先来个不是很难的数学题（？））

希望不会沉（）

 

天星有一块n*n的拼图，其左右各拼有一块“母块”拼图，如图所示。

天星想把拼图分成AB两部分（与母块需要相连），然后将B旋转，与A拼接出一个直角，拼合时两母块角对角接触。

一种正确的拼图方案：

 

错误实例：

（注：母块没有角对角）

你不能丢弃拼图，或使得拼图重叠。

那么天星有多少种不同的分割方案呢

 

输入

n，拼图的规模

输出

不同的方案数量

 

输入样例

3

输出样例

8

 

 

题目中

对于30%的用例：1≤n≤10

对于70%的用例：1≤n≤100

（我降一下量级吧）

输出的n可能过大，请对1e9+7取模

 

喊大佬们捧个场

  @Mr.K 018 @yhz012

一月 10, 2021，由Muriya Tensei修改

[Muriya Tensei]

1 分钟前, 抹消思绪 说道:

不确定我看懂了题目没有，是求2^n对1e9+7取模吗。

那么2^n是怎么得出来的（）

0 0 1 1

0 1 1 1 

0 0 1 0

0 0 0 0

这种有算吗（）

[Muriya Tensei]

38 分钟前, 抹消思绪 说道:

菜了，确实是没看懂。

n等于3的时候，这些分割方式有哪种违规吗，或者是重复？

重复的话应该没吧，但是很多没法拼成要的结果啊（母图角对角其实就是n*n切开然后拼回n*n）

[Muriya Tensei]

9 分钟前, 抹消思绪 说道:

n*n是只能切割不能移动咯？

那主楼里4*4的正确例子貌似没法通过切割后旋转来实现吧，其中一边还得镜像。

是拼图，所以允许翻转，另外只讨论旋转b的情况（因为旋转a和旋转b可以完全镜像）

[Muriya Tensei]

18 分钟前, 抹消思绪 说道:

好像明白了，那么3*3的情形是这8种吗。

√

[Muriya Tensei]

从一侧分析的话，会导致另一侧的连续性难以判断，所以可以（）

一月 10, 2021，由Muriya Tensei修改

[Muriya Tensei]

6 小时前, yhz012 说道:

想了下，可以理解为是问对于一个n * n的01矩阵，有多少种对称矩阵，使得0和1都是连续的吧？

 

假如说上面的理解是正确的，那大概就可以暴力递归了

首先1*1的只有0和1两个满足，因为实际上始终是对称的，我们不妨让右上角始终是0，然后最终结果乘2一下就好

接下来假设k*k的方案已经全部找到了，那么对于每种方案，接下来就是把这个方案放到右上角，然后左侧和最下面增加一行一列，使得增加的这一行一列对称并与原方案连续

 

要保证这个的话似乎可以用排除法？我大概需要仔细想一下。不过这么做完之后肯定能不重复，因为右上角部分就不重复，所以可以继续往下递归就行了

 

不对我傻了，这样会漏方案比如3*3的

1 0 0
0 0
1

这个是不连续的，但是在4*4的时候

1 1 0 0
1 0 0
1 1
1

是连续的

 

 

大佬来了，大佬分析还是准的，就差一点小细节了

这个题网上没解析，和朋友们一起做的，最后拍板的答案都不是特别确定（我现在确定了，有些问题，所以还是看看能不能有大佬给更好的解答emmm）

 

 

一月 10, 2021，由Muriya Tensei修改

[Muriya Tensei]

2 小时前, yhz012 说道:

因为是对称矩阵，所以如果带着（上）三角矩阵是联通的，那整个矩阵是联通的倒是没问题

不过我刚才想到仅仅要求联通应该是不够的

1 1 1 1 1
1 1 0 1
1 0 0
1 1
1

这个虽然联通，但是实际上不能这么切块，写完整的话如下

1 1 1 1 1
1 1 0 1 1
1 0 0 0 1
1 1 0 1 1
1 1 1 1 1

B块和中间连不上，所以实际上我还得要求第一行和第一列至少要出现01各1次

 

从左到右，从上往下标记行列的话

对于n*n的矩阵M，如果M[1, n] = 0，如果存在其他的0，则必然M[1, n-1]为0（否则无法连通）

如果M[1, n-1] = 0，如果M[1, n-2] != 0，且存在0在前n-3列，则M[2, n-1] = M[2, n-2] = 0 （否则无法连通）

感觉这边似乎也可以考虑递推一下，我再仔细思考一下

 

  

不是大佬，我差的这点小细节实际上很头疼……

如果1代表右侧部分，0代表左侧的话，应该是0如果出现则左下必然是0，不然对称产生的0不连通 或 导致1不连通

[Muriya Tensei]

《没什么用的探讨结果》

对于一个n*n的矩阵，首先排除全1和1个1（0）的四种情况，最外层可以2~n-1块，共n-2种；n块时可以看做由n-1翻转得到

对于这n-2种情况，其内部是一个n-2阶的方块，再分两类：①本身符合条件的双联通，f（n-2）种；②1的单连通，0不可存在于副对角线即其相邻一格上（额外的，这种情况下对外侧的n-2种不能完全对应，不能直接乘算）

 

位置的情况只剩下了②是未知的，可以简单转化为，对于一个n-4阶的上三角区域，1单连通且0的若干连通区域均与左或上边界相邻。

 

0	0	0	0	0	1	1
		1		1	1	1
	1	1	1	1	1
		1	1	1
	1	1	1	1	1
	1	1		1

抽象为②的 3阶上三角 

0 1 0

1 1

0

（然后这个数量怎么求嘛，没想到）