我们现在假设从某个第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三角形的存在,可以裁剪掉很多不必要的选择。
|