怪兽分裂

iseemu2009

      在一个三维坐标网格中，位于格点 (x, y, z) 的一只怪兽，在目标格点 (x+1, y, z), (x, y+1, z) 和 (x, y, z+1)都是空位的情况下，可以将自身分裂成三只怪兽占据它们，并且使 (x, y, z) 恢复空位。若三个目标点中任何一个被占位时它不能分裂。
      开始时只有一只怪兽位于原点 (0, 0, 0), 经过 n 次分裂之后（任何 1 只发生分裂就记为 1 次)，格阵中将会分布有 2n+1 只怪兽, 对应一个 2n+1 点的占位点集。记 `S_n` 为经过 n 次分裂后所有可能的占位点集之集，记D(n)=|`S_n`|。
      例1、`S_1`={{(1,0,0), (0,1,0), (0,0,1)}},   D(1)=1.
      例2、`S_2`={{(0,1,0), (0,0,1), (2,0,0), (1,1,0), (1,0,1)},
                      {(1,0,0), (0,0,1), (1,1,0), (0,2,0), (0,1,1)},
                      {(1,0,0), (0,1,0), (1,0,1), (0,1,1), (0,0,2)}}
                D(2)=3.
       已知 D(10) =44499，D(20) =9204559704，而D (100) 的末尾九位是780166455，求D(1000) 的末尾九位。  

hujunhua

可以重新定义“次”而提出另外一个问题。假定每秒发生一次分裂，每次都有最多的怪兽同时发生分裂，规则如下：
1、当两只怪兽有一个公共目标点时，当前最多只能有其中一只发生分裂。
2、发生分裂的怪兽，恢复的空位可以立即被本秒发生的分裂占据。（快速规则）
2'、发生分裂的怪兽，恢复的空位只能被下一秒发生的分裂占据。（慢速规则）
记 a(n)、a'(n)分别为快速规则和慢速规则第 n 秒发生分裂的怪兽数，求这个序列。

iseemu2009

问题加上计时规则后会变得更复杂了。到后面怪兽越来越多时，考虑哪些能分裂，哪些不能，很费脑力。

hujunhua

可以先降到二维来研究。试了一下，快速规则似乎唯一性更好，慢速规则歧路多。

mathe

为了方便起见，我们可以用X来代表坐标(x,y,z), L(X)=x+y+z代表这个坐标的层数。
对于怪兽分裂n次后获得的一个集合，我们可以将集合里面所有位置按层数从大到小排列，然后逆向分裂过程，对它们在进行反向合并.
由于层数l里面所有坐标位置构成一个正三角形，对于同一个层数中所有点，我总可以从正三角一个角的位置开始向另外一条边合并，这样，合并的方案是唯一。
对于一个合法的分裂结果，总是可以将最大层的所有坐标合并到次大层，唯一的问题是合并后，次大层中某些位置可能会存在多只怪兽。
然后我们继续按同样方式合并次大层，直到最后全部合并到(0,0,0)这一个点。
开始合并之前，每个坐标可以有怪兽也可以没有，构成一个函数S(X), 其中如果位置X有怪兽，S(X)=1,不然S(X)=0.
合并过程中，每个位置怪兽可以达到的最大数目为容量C(X).
而对于每次将(x+1,y,z),(x,y+1,z),(x,y,z+1)合并为(x,y,z)的操作，我们称为对X=(x,y,z)的一次合并操作, 整个过程中对X的合并次数记为分裂数F(X)。
于是很显然C(X)=F(X)+S(X)。
此外很显然我们可以得到\(C((x,y,z))=F((x-1,y,z))+F((x,y-1,z))+F((x,y,z-1))\). (其中如果某个参数小于0，对应F(.)为0）

我们首先需要说明的是，如果给定一个结束状态S(X),存在一个对应合并过程使得最终可以合并到一个点(0,0,0),那么必然存在一个合法的分裂过程，从(0,0,0)分裂到最终S(X)的状态。这个是因为合并过程就唯一确定C(X)和F(X)，然后我们总是从(0,0,0)开始分裂，对于每次分裂出来的任意一个点X,如果已经使用过的X的分裂次数小于F(X),那么就深度优先先分裂X,这个深度优先规则总可以保证不会出现怪兽冲突问题，从而最终必然能够到达结束状态。

由此我们不需要去考虑分裂的顺序问题，而只需要考虑哪些最终状态S(X)或哪些C(X)和F(X)可以被达到。

首先如果对于三个格子(x+1,y,z),(x,y+1,z),(x,y,z+1)有\(C(x+1,y,z)\ge2,C(x,y+1,z)\ge 2, C(x,y,z+1)\ge 2\)那么必然有\(F(x+1,y,z)\ge 1, F(x,y+1,z)\ge 1, F(x,y,z+1)\ge 1\)， 于是我们可以得到\(C(x+1,y+1,z)\ge F(x+1,y,z)+F(x,y+1,z)\ge 2, C(x+1,y,z+1)\ge 2, C(x,y+1,z+1)\ge 2\), 这样，我们就可以从x+y+z+1层中三个两两相邻各自的容量不小于2位置得出x+y+z+2层中三个两两相邻的各自容量不小于2的位置。由此这个递推过程必然能够无限进行下去，得出怪兽的分裂过程无法终止，所以不是一个合法过程，所以我们得出
引理1： 同一层三个两两相邻格子(x+1,y,z),(x,y+1,z),(x,y,z+1)，必然有一格容量小于2.
类似可以有
引理1.1：同一层三个两两相邻格子(x+1,y,z),(x,y+1,z),(x,y,z+1)，必然有一格分裂数为0.
同样如果某个各个格子(x,y,z)的分裂数不小于2，我们可以得出(x+1,y,z),(x,y+1,z),(x,y,z+1)的容量都不小于2，所以得出
引理2：任意一个格子X的分裂数F(X)只能是0或1.
于是所有格子的分裂过程构成一个有向无环图，每条边的权重都只能是1. （因为每个位置最多分裂一次），而对于分裂n次的情况，这个对应有向无环图正好n个点，我们需要计算这样的图的数目。而且还需要满足引理1，引理2以及上面的约束即\(F((x-1,y,z))+F((x,y-1,z))+F((x,y,z-1))-F((x,y,z))=0或1\), 也就是除了根节点，每个点都只有一个或两个父节点。而且如果一个点有两个父节点，那么它必然分裂（有三个孩子节点）。

iseemu2009

mathe 发表于 2025-4-4 07:44
为了方便起见，我们可以用X来代表坐标(x,y,z), L(X)=x+y+z代表这个坐标的层数。
对于怪兽分裂n次后获得的一 ...

这就像不限向上分枝的树干，道理是这个道理，计算起来还是颇费脑力的。你这个逆向推导过程是从任意一个第n层的分枝向主干行进的吧，事先要知道第n层有多少个枝干才行吧？但事先知道不是可能的。

mathe

我们现在假设从某个第k层所有状态容量构成的集合C出发，再分裂n次，可以的方案数目为R(C,n)
于是我们要计算的就是R({(0,0,0)->1},n)
我们直到，这个方案数目实际上是平移翻转都保持不变。也就是如果某个C中，
平移性:如果所有取值非零元素的横坐标都大于某个a,我们可以将所有元素的x坐标减a,那么结果不会发生变换，类似对于y,z坐标也相同。
翻转性：如果每个取值非零元素的xy坐标都交换，那么结果也不会发生变化，类似可以交换其它的坐标。
显然R(ANY,0)=1,R({(0,0,0)->1},1)=1.
而且R({(0,0,0)->1},n)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
为了计算R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n)， 我们需要穷举三个位置(1,0,0),(0,1,0),(0,0,1)的F函数，可以有

(1,0,0)	(0,1,0)	(0,0,1)	结果
0	0	0	当n=0时取1,不然取0
1	0	0	取R({(2,0,0)->1,(1,1,0)->1,(1,0,1)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
0	1	0	取R({(1,1,0)->1,(0,2,0)->1,(0,1,1)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
0	0	1	取R({(1,0,1)->1,(0,1,1)->1,(0,0,2)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
1	1	0	取R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
1	0	1	取R({(2,0,0)->1,(1,1,0)->1,(1,0,1)->2,(0,1,1)->1,(0,0,2)->1},n-1)=R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
0	1	1	取R({(1,1,0)->1,(0,2,0)->1,(0,1,1)->2,(1,0,1)->1,(0,0,2)->1},n-1)=R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
1	1	1	三角形全1非法，取0

由此得出R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n)=(n==0?1:0)+3R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)+3R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1).
我们我们需要使用计算机构建各集合的递推式
R({(0,0,0)->1},n)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n)=(n==0)+3R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)+3R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
等等

而比如计算R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n)
由于C(1,1,0)=2, 我们只能选择F(1,1,0)=1，于是在穷举过程中，同样由于全1三角形的存在，可以裁剪掉很多不必要的选择。

mathe

monster2.zip (395.02 KB, 下载次数: 1)

2025-4-9 17:16 上传

点击文件名下载附件

根据上面分析方案可以得到如下递推式

a1[n]=+a0[n-0]+a2[n-1]
a2[n]=+a0[n-0]+a2[n-1]+a2[n-1]+a3[n-2]+a2[n-1]+a3[n-2]+a3[n-2]
a3[n]=+a2[n-1]+a3[n-2]+a3[n-2]+a3[n-2]+a4[n-3]+a3[n-2]+a5[n-3]+a4[n-3]
a4[n]=+a3[n-2]+a4[n-3]+a5[n-3]+a4[n-3]+a6[n-4]+a7[n-4]
a5[n]=+a3[n-2]+a5[n-3]+a4[n-3]+a4[n-3]+a8[n-4]+a5[n-3]+a9[n-4]+a8[n-4]
a6[n]=+a4[n-3]+a7[n-4]+a6[n-4]+a6[n-4]+a10[n-5]+a11[n-5]
a7[n]=+a5[n-3]+a8[n-4]+a9[n-4]+a7[n-4]+a12[n-5]+a13[n-5]
a8[n]=+a4[n-3]+a6[n-4]+a7[n-4]+a8[n-4]+a14[n-5]+a15[n-5]
a9[n]=+a5[n-3]+a9[n-4]+a8[n-4]+a8[n-4]+a16[n-5]+a17[n-5]+a9[n-4]+a18[n-5]+a16[n-5]
a10[n]=+a7[n-4]+a13[n-5]+a12[n-5]+a10[n-5]+a19[n-6]+a20[n-6]
a11[n]=+a6[n-4]+a11[n-5]+a10[n-5]+a11[n-5]+a21[n-6]+a22[n-6]
a12[n]=+a8[n-4]+a15[n-5]+a14[n-5]+a12[n-5]+a23[n-6]+a24[n-6]
a13[n]=+a9[n-4]+a16[n-5]+a18[n-5]+a13[n-5]+a25[n-6]+a26[n-6]
a14[n]=+a6[n-4]+a10[n-5]+a11[n-5]+a14[n-5]+a27[n-6]+a28[n-6]
a15[n]=+a7[n-4]+a12[n-5]+a13[n-5]+a15[n-5]+a29[n-6]+a30[n-6]
a16[n]=+a8[n-4]+a14[n-5]+a15[n-5]+a17[n-5]+a31[n-6]+a32[n-6]+a16[n-5]+a33[n-6]+a34[n-6]
a17[n]=
a18[n]=+a9[n-4]+a18[n-5]+a16[n-5]+a16[n-5]+a35[n-6]+a36[n-6]+a18[n-5]+a37[n-6]+a35[n-6]

其中已知a0是特殊标记，也就是a0[0]=1,而对于所有其它n,a0[n]=0, 而对于其它ai[x],在x<0时必然为0. 而我们目标是计算a1[n].
比如根据第一行就可以得出
a1[0]=a0[0]=1
a1[1]=a2[0]=a0[0]=1
a1[2]=a2[1]=a2[0]+a2[0]+a2[0]=3
a1[3]=a2[2]=3a2[1]+3a3[1]=3*3+3*(a2[0])=12

mathe

a1[100]=31022863355197733835084656754275104117019058780166455
a1[200]=4480030736794902002376087592907372109112923882248759630967814762646144183583161840359612734499382545262907
上面a1[3]弄错了，是3a2[1]+3a3[0]=9
monster3.zip (13.02 KB, 下载次数: 6)

2025-4-10 10:14 上传

点击文件名下载附件

附件中是1-299的数据，其中[]里面的是需要的集合数目

mathe

gend.tgz (163.01 KB, 下载次数: 6)

2025-4-11 09:56 上传

点击文件名下载附件

做出了前999个层内状态图，其中每个蓝色点代表容量为1的点，红色点代表容量为2的点。
看上去，每个状态图都是连通的，而且除了a1/a2,所有图中红色点都连通形成一条路径，而蓝色点至少同一个红色点相邻，并且蓝色点数目总是比红色点多3.