怪兽分裂
在一个三维坐标网格中，位于格点 (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) 的末尾九位。 可以重新定义“次”而提出另外一个问题。假定每秒发生一次分裂，每次都有最多的怪兽同时发生分裂，规则如下：
1、当两只怪兽有一个公共目标点时，当前最多只能有其中一只发生分裂。
2、发生分裂的怪兽，恢复的空位可以立即被本秒发生的分裂占据。（快速规则）
2'、发生分裂的怪兽，恢复的空位只能被下一秒发生的分裂占据。（慢速规则）
记 a(n)、a'(n)分别为快速规则和慢速规则第 n 秒发生分裂的怪兽数，求这个序列。
问题加上计时规则后会变得更复杂了。到后面怪兽越来越多时，考虑哪些能分裂，哪些不能，很费脑力。 可以先降到二维来研究。试了一下，快速规则似乎唯一性更好，慢速规则歧路多。 为了方便起见，我们可以用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\), 也就是除了根节点，每个点都只有一个或两个父节点。而且如果一个点有两个父节点，那么它必然分裂（有三个孩子节点）。
mathe 发表于 2025-4-4 07:44
为了方便起见，我们可以用X来代表坐标(x,y,z), L(X)=x+y+z代表这个坐标的层数。
对于怪兽分裂n次后获得的一 ...
这就像不限向上分枝的树干，道理是这个道理，计算起来还是颇费脑力的。你这个逆向推导过程是从任意一个第n层的分枝向主干行进的吧，事先要知道第n层有多少个枝干才行吧？但事先知道不是可能的。 我们现在假设从某个第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)结果
00 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)
01 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)
00 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)
11 0 取R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
10 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)
11 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三角形的存在，可以裁剪掉很多不必要的选择。
根据上面分析方案可以得到如下递推式
a1=+a0+a2
a2=+a0+a2+a2+a3+a2+a3+a3
a3=+a2+a3+a3+a3+a4+a3+a5+a4
a4=+a3+a4+a5+a4+a6+a7
a5=+a3+a5+a4+a4+a8+a5+a9+a8
a6=+a4+a7+a6+a6+a10+a11
a7=+a5+a8+a9+a7+a12+a13
a8=+a4+a6+a7+a8+a14+a15
a9=+a5+a9+a8+a8+a16+a17+a9+a18+a16
a10=+a7+a13+a12+a10+a19+a20
a11=+a6+a11+a10+a11+a21+a22
a12=+a8+a15+a14+a12+a23+a24
a13=+a9+a16+a18+a13+a25+a26
a14=+a6+a10+a11+a14+a27+a28
a15=+a7+a12+a13+a15+a29+a30
a16=+a8+a14+a15+a17+a31+a32+a16+a33+a34
a17=
a18=+a9+a18+a16+a16+a35+a36+a18+a37+a35
其中已知a0是特殊标记，也就是a0=1,而对于所有其它n,a0=0, 而对于其它ai,在x<0时必然为0. 而我们目标是计算a1.
比如根据第一行就可以得出
a1=a0=1
a1=a2=a0=1
a1=a2=a2+a2+a2=3
a1=a2=3a2+3a3=3*3+3*(a2)=12 a1=31022863355197733835084656754275104117019058780166455
a1=4480030736794902002376087592907372109112923882248759630967814762646144183583161840359612734499382545262907
上面a1弄错了，是3a2+3a3=9
附件中是1-299的数据，其中[]里面的是需要的集合数目
做出了前999个层内状态图，其中每个蓝色点代表容量为1的点，红色点代表容量为2的点。
看上去，每个状态图都是连通的，而且除了a1/a2,所有图中红色点都连通形成一条路径，而蓝色点至少同一个红色点相邻，并且蓝色点数目总是比红色点多3.