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

[抹消思绪]

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

[抹消思绪]

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，由抹消思绪修改

[抹消思绪]

6 分钟前, Muriya Tensei 说道:

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

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

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

[抹消思绪]

14 分钟前, Muriya Tensei 说道:

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

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

[抹消思绪]

44 分钟前, Muriya Tensei 说道:

√

ok，我再想想。

 

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

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

[抹消思绪]

16 分钟前, yhz012 说道:

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

 

考虑第一行

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

 

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

 

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

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

例如