F(n)可以计算，但考虑到二层以上可以不连续就麻烦了，直觉与数字的拆分相关。
F(n)={1,1,2,3,5,9,14,26,34,78...}
类似的链接：
A291896
Number of 1-dimensional sandpiles with n grains piling up against the wall.
1, 1, 1, 2, 3, 5, 9, 14, 24, 40, 67, 112, 186, 312, 520, 868, 1449, 2417, 4034, 6730, 11229, 18735, 31254, 52143, 86989, 145119, 242096, 403871, 673751, 1123964, 1875014, 3127926, 5218034, 8704769, 14521354, 24224601, 40411595, 67414781, 112461579, 187608762
关键要用动态规划，应该可以做到O(n^3)的空间复杂度。而如果不需要算颜色，应该可以做到O(n^2)的复杂度
记F(n,d,m)为去掉底层后山林的计数(不染色)，n为总圆数，d为段数，m为底层圆总数(去掉原底后新底，可以不连续)
首先F(n,1,n)=1, 也就是只有一段连续的n个圆。
而当m<n, 那么
\(F(n,1,m)=\sum_{d=1}^{\min\{n-m,\lfloor\frac{m}2\rfloor\}}\sum_{x=d}^{\min\{n-m,m-d\}}{m-x\choose d}F(n-m,d, x)\)
\(F(n,d,m)=\sum_{v=d-1}^{m-1}\sum_{u=v}^{n-m+v}F(u,d-1,v)F(n-u,1,m-v), d\ge 2\)
\(T(n)=3*2^{n-1}+3\sum_{m=1}^{n-1} \sum_{d=1}^{\min\{n-m,\lfloor\frac{m}2\rfloor\}}\sum_{x=d}^{\min\{n-m,m-d\}}{m-x\choose d}F(n-m,d, x)2^{m-1-x+d}\)
下面这段pari/gp代码已经可以验证通过，说明算法上应该没有问题了，只是计算速度还是远远不够
Tn(n)=
{
local(F,s,mm,mm2);
F=vector(n);
for(u=1,n, F=matrix(u,u));
F=1;
for(u=2,n,
F=1;
for(m=1,u-1,
s=0;
for(d=1, min(u-m,floor(m/2)),
for(x=d,min(u-m,m-d),
s+=(m-x)!/d!/(m-x-d)!*F
)
);
F=s;
);
for(d=2,u,
for(m=d,u,
s=0;
for(v=d-1,m-1,
for(uu=v,u-m+v,
s+=F*F
)
);
F=s;
)
)
);
s=0;
for(m=1,n-1,
for(d=1,min(n-m,floor(m/2)),
for(x=d,min(n-m,m-d),
s+=(m-x)!/d!/(m-x-d)!*F*2^(m-1-x+d)
)
)
);
s*3+3*2^(n-1)
}
比如我们可以得到
1 3
2 6
3 18
4 48
5 126
6 342
7 918
8 2460
9 6612
10 17760
11 47688
12 128082
13 343998
14 923862
15 2481234
16 6663894
17 17897268
18 48066906
19 129093882
20 346708896
21 931160118
22 2500827642
23 6716501868
24 18038587308
25 48446444256
26 130113179790
27 349446483114
28 938512492080
29 2520573936528
30 6769534793922
31 18181018483236
32 48828973207602
33 131140542357792
34 352205682819960
35 945922906678356
36 2540476173509184
37 6822986463912222
38 18324574255864524
39 49214522619196662
40 132176016905843034
41 354986668879705980
42 953391833346573828
43 2560535556899917890
44 6876860183640182676
45 18469263532739961498
46 49603116296198116062
47 133219667472530689410
48 357789613368544044912
49 960919734023567035020
50 2580753327472370043522
T=7323449210126924910579630584897430688447422
T=58973109821225628584151275235291933222902630858059057350792683647099233689677890066066
T=474889301775612834272906473038741705758701896942716482748190414113594430033117569849194551248694578007105685835551469017719962148
T=3824113220832045525627522558241021631202697365153751029404405981168332552694693864227943231158062291422426812079607700557852398504950695064477487905774626747272829965249436
T=30794212190217473004355080693399296825536110663498496419203022689517620891763563133653307490204289589983483583339450139180406907503795190311143938090243444891020906285005341257620489384213522272500565009745550121156
mathe 发表于 2025-3-10 09:12
T=7323449210126924910579630584897430688447422
T=589731098212256285841512752352919332229026 ...
能编出这个程序十分了不起，首先解决了山林的造型方案数，其次解决了着色的问题，两个都是棘手的问题。着色问题可能更难一些。结果中的两个答案和题干中的是一致的，其它的我也不知道正不正确。
iseemu2009 发表于 2025-3-10 09:18
能编出这个程序十分了不起，首先解决了山林的造型方案数，其次解决了着色的问题，两个都是棘手的问题。着 ...
mathe和 Wayne版主都是十分厉害的人，还有 northwolves 和 hujunhua也很优秀，你们应该是数学系毕业的吧。:)感觉代数、几何、数学分析、函数、群论、数论等方面什么都懂。不知有些题目你们是一起合作解出的，还是各自独立贡献出的。
mathe 发表于 2025-3-10 09:12
T=7323449210126924910579630584897430688447422
T=589731098212256285841512752352919332229026 ...
既然找到了解决方法，就看代码能不能优化一下，以提高运算速度。就像求三圆相切那道题，我解决了方案，但程序臃肿，运行S(1234)要十多秒的，经大师改进后1秒运行S（10^9）。