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

[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修改

[抹消思绪]

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

[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

这种有算吗（）

[抹消思绪]

40 分钟前, Muriya Tensei 说道:

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

0 0 1 1

0 1 1 1 

0 0 1 0

0 0 0 0

这种有算吗（）

菜了，确实是没看懂。

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

一月 9, 2021，由抹消思绪修改

[Muriya Tensei]

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

菜了，确实是没看懂。

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

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

[抹消思绪]

6 分钟前, Muriya Tensei 说道:

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

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

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

[Muriya Tensei]

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

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

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

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

[抹消思绪]

14 分钟前, Muriya Tensei 说道:

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

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

[Muriya Tensei]

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

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

√

[抹消思绪]

44 分钟前, Muriya Tensei 说道:

√

ok，我再想想。

 

放弃了，蹲一个大佬讲解，诶嘿。

一月 9, 2021，由抹消思绪修改

[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

是连续的

一月 9, 2021，由yhz012修改

[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修改

[yhz012]

7 小时前, Muriya Tensei 说道:

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

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

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

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 （否则无法连通）

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

 

  

7 小时前, Muriya Tensei 说道:

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

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

一月 10, 2021，由yhz012修改

[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不连通

[yhz012]

11 小时前, Muriya Tensei 说道:

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

想了一下，好像可以沿着这个思路搞

 

考虑第一行

引理1：第一行的01必然只会翻转一次。即存在0 <= x <= n，使得M[1, :x] = 0, M[1, x:] = 1。否则会出现0被1包住的不连通情况。（备注：行列对称所以第一列同理）

 

想了下，可以直接把第一行第一列展平，展平后的依然只能有且仅有一次翻转

 

然后似乎就可以丢掉第一行第一列开始递推一下了

一月 11, 2021，由yhz012修改

[抹消思绪]

16 分钟前, yhz012 说道:

想了一下，好像可以沿着这个思路搞

 

考虑第一行

引理1：第一行的01必然只会翻转一次。即存在0 <= x <= n，使得M[1, :x] = 0, M[1, x:] = 1。否则会出现0被1包住的不连通情况。（备注：行列对称所以第一列同理）

 

想了下，可以直接把第一行第一列展平，展平后的依然只能有且仅有一次翻转

 

然后似乎就可以丢掉第一行第一列开始递推一下了

第一行第一列虽然只能翻转一次，但第二行第二列开始就不是了。

例如

[skaldskaldskald]

我们。。。。。逛的是同一个论坛么。。。。。膜拜大佬

[Mr.K 018]

  对矩阵的可能形状做了一些观察，又参考了yhz的回复，以下是目前为止观察得出的结果。如果一个仅由0和1为元素的n阶方阵合题意，那么它必须：

1）是沿副对角线对称的，前面不少人都发现了；

2）左上三角形要么只有一个连通分量，要么只有两个连通分量。若有两个：

2.1）这两个连通分量必须各自占据一些处在边线（左或上）和反对角线上的元素，否则整个矩阵就会出现多于2个的连通分量。进而得知，

2.2）右上方元素和左下方元素分属不同的连通分量；

2.3）参考yhz的回复，边线上0和1只能翻转一次；

2.4）反对角线上0和1也只能翻转一次。如果翻转了多于1次（例如3次。参考2.2，不可能翻转偶数次），就会破坏原有两个连通分量的连通性，形如

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

上述几个要求只是必要条件，并非充分条件，例如，将上例（4，3）处的1换为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

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

[xyDnz]

稍微想了一下，这道题的本质是要讲一个阶梯形的图形分割成两部分，并且这两部分在远正方形的分割上也是两块联通的分割子集，将原图形中的交点作为坐标，右上角为（0,0），左下角为（n，n），分为三种情况，分割线连右边和下边，分割线连接右边和斜边，分割线连接斜边和下边，第二种情况可以看做是分割线从（0,0）出发到垂直向下后再到斜边上，第二种情况本质上会将中间分成3分所以排除，第三种情况和第一种情况实际上是对称所以最后只要答案乘以2再去掉对称相等的特例，这样这题就变成从（0,0）出发不能经过底边的到（x，x）(1<=x<=n)的合法路线合计有多的爆搜题

大体思路应该是这样，实际上可能还有一些细节需要优化，不过最近一年备战考研算法荒废了半年，就不丢人了，摸了

一月 15, 2021，由xyDnz修改

[伽莫夫博士]

在SS你甚至可以刷题？

[无明]

本来到这个论坛是来ghs的，没想到我居然开始思考数学题.... (｡í _ ì｡)先插个眼，回头想好了再回来装逼 ⊙ω⊙