多彩的圆山

iseemu2009

多彩的圆山染色方案数求解

mathe

去掉最下面一层，圆山会形成一些不同数目的山林，于是就可以递归求没有染色的情况了。
而加上染色情况，那么分类除了最下面一层圆的数目，还需要加上颜色分类了，状态数目不少。

比如一阶圆山只有一个分类，底层一个圆，颜色a.
二阶圆山也只有一类，底层两圆，颜色ab
三阶圆山有三类，一类底层两圆，颜色ab,另外两类底层三圆，颜色分别aba和abc

mathe

染色数目之和最底下两层分布有关系，最底层的数目加上第二层的数目决定了染色方案数。染色方案为3乘上2的幂，而这个2的幂次应该就是两层数目差。
所以动归可以仅使用最底层的数目加第二层的数目进行分类，这样复杂度就相对比较容易控制了

iseemu2009

mathe 发表于 2025-3-9 12:06
染色数目之和最底下两层分布有关系，最底层的数目加上第二层的段数决定了染色方案数。
所以动归可以仅使用 ...

是的，但当n较大时，可以行成3行，4行……多行的情况，有的层中圆可以分开形成几个小山，小山上又有小山。

iseemu2009

这个也是一道国外求算法的难题，应该比砌砖墙那道题更复杂一些，和我前面发的求平衡雕塑那道难度差不多。

iseemu2009

圆山造型方式举例

mathe

定义F(n,k)为总共n个圆盘，底层k个圆盘不考虑染色的方案数目。

F(1,1)=1, T(1)=3 (T(1)比较特殊)
F(2,2)=1, T(2)=6
n=3,   
   i)第一层为3， F(3,3)=1, T(3)+=3*2*2=12
   ii)第一层为2，F(3,2)=1，上面余一个, 上面只能放F(1,1),T(3)+=3*2=6。
   所以T(3)=18
n=4
  i)第一层为4， F(4,4)=1, T(4)+=3*2^3=24
  ii)第一层为3，余下1个，只能在上面放F(1,1),有两种不同选择位置，F(4,3)=2, 染色方案3*2^2=12, 共2*12=24种
  iii)第一层为2，余下2两个，由于两个放的对象最多底为1，底为1的只能F(1,1)所以不合格，淘汰
故T(4)=48
n=5
  i)第一层为5，F(5,5)=1, T(5)+=3*2^4=48
ii)第一层为4，余下1个有三种位置，F(5,4)=3, T(5)+=3*(3*2^3)=72
iii)第一层为3，余下2个圆盘2个位置，只能放F(2,2)一种选择，由于F(2,2)=1,所以F(5,3)=1,T(5)+=3*2*1 (第2层连续k个盘子会导致连乘种k-1个2变1）
   由此T(5)=126

mathe

所以对于本题，关键还是先计算所有的F(n,k), 其中\(k\le n\le \frac{k(k+1)}2\),而且对于给定的k,其中n可以取到的范围是稀疏的。
我们可以再手工计算几层，比如
n=6
第一层为6的情况很类似，F(6,6)=1,F(6,5)=4.
而第一层只有4个圆的情况，余下两个圆三格位子，由于n=2,只有F(2,2)=1, n=1只有F(1,1)=1,可以放一个F(2,2)两种位置选择或两个F(1,1)一种选择（中间留一个空），对应
   。     。
。 。 。 。
所以得出F(6,4)=3, 但是计算染色方案时，它们对T(6)的贡献不同，其中使用F(2,2)的两种方案，由于第二层存在两个连续格子，颜色选择为3*2*2*1=12,而对于使用F(1,1)的一种方案，颜色选择为3*2*2*2=24.
而第一层使用3个圆的情况，余下3个圆两个位置，只有F(3,2)=1可用，所以F(6,3)=1. 颜色选择为3*2*1=6
而第一层使用2两个圆，余下4个圆1个位置，由于1个位置最多消耗一个圆，已经位置不够，淘汰。

n=7,
同样我们先考虑第一层5个圆情况，余下两个圆4个位置，同样可以选择F(2,2)或F(1,1)+F(1,1). 其中F(2,2)有三个位置可以选择，F(1,1)+F(1,1),相当于在4个空位选择两个不相邻的位置，我们想象每个圆后面捆绑了一个空位，也就时每个圆占两个位置，而最右边位置可以捆绑一个不存在的空位，所以是\(C_{4+1-2}^2=3\)种选择。也就是F(7,5)=3+3=6, 而前三种染色方案为3*2^3*1^1=24，后三种染色方案为3*2^4=48.
第一层4个圆情况，留下三个圆3个位置。所以可以选择F(3,3), F(3,2). 而将n拆为2+1或1+1+1都会导致3个位置不够（3个位置拆分只能为1+1,因为中间要留空）。其中F(3,3)只有一种选择，3个连续圆是的颜色数相乘中两个2变为1，所以颜色数是3*2^1*1^2, 而F(3,2)有两种位置选择，颜色数为3*2^2*1.

mathe

所以一般情况我们为了计算
F(n,k) 我们需要将余下n-k个圆放在k-1个位置上，我们需要将n-k个圆划分为最多k/2组，而且其中组数比较多时，每组可用圆的数目也会比较少。
假设d组，这d组各自拥有圆\(x_1,x_2,...,x_d\),底的宽度为\(y_1,y_2,...,y_d\),于是要求
\(y_1+y_2+...+y_d\le k-d\)
\(1\le y_i \le x_i \le \frac{y_i(y_i+1}2\)
\(x_1+x_2+...+x_d=n-k \le \frac{y_1(y_1+1)}2+\frac{y_2(y_2+1)}2+...+\frac{y_d(y_d+1)}2\)
我们可以利用上面条件先搜索合法的有序的\(y_i\),然后再搜索合适的\(x_i\)让它们满足最后一行等式关系，最后再排列组合考虑它们的位置关系。
最后当然还要检查每个对应的\(F(x_i,y_i)\)非零

iseemu2009

感觉求圆山布局的方案数比求它们的着色方案容易些。