多彩的圆山

northwolves

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

mathe

关键要用动态规划，应该可以做到O(n^3)的空间复杂度。而如果不需要算颜色，应该可以做到O(n^2)的复杂度

mathe

记F(n,d,m)为去掉底层后山林的计数(不染色)，n为总圆数，d为段数，m为底层圆总数(去掉原底后新底，可以不连续)

mathe

首先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}\)

mathe

下面这段pari/gp代码已经可以验证通过，说明算法上应该没有问题了，只是计算速度还是远远不够

1. Tn(n)=
   
2. {
   
3.    local(F,s,mm,mm2);
   
4.    F=vector(n);
   
5.    for(u=1,n, F[u]=matrix(u,u));
   
6.    F[1][1,1]=1;
   
7.    for(u=2,n,
   
8.       F[u][1,u]=1;
   
9.       for(m=1,u-1,
   
10.          s=0;
    
11.          for(d=1, min(u-m,floor(m/2)),
    
12.              for(x=d,min(u-m,m-d),
    
13.                 s+=(m-x)!/d!/(m-x-d)!*F[u-m][d,x]
    
14.              )
    
15.          );
    
16.          F[u][1,m]=s;
    
17.       );
    
18.       for(d=2,u,
    
19.          for(m=d,u,
    
20.             s=0;
    
21.             for(v=d-1,m-1,
    
22.                for(uu=v,u-m+v,
    
23.                    s+=F[uu][d-1,v]*F[u-uu][1,m-v]
    
24.                )
    
25.             );
    
26.             F[u][d,m]=s;
    
27.          )
    
28.       )
    
29.    );
    
30.    s=0;
    
31.    for(m=1,n-1,
    
32.       for(d=1,min(n-m,floor(m/2)),
    
33.           for(x=d,min(n-m,m-d),
    
34.              s+=(m-x)!/d!/(m-x-d)!*F[n-m][d,x]*2^(m-1-x+d)
    
35.           )
    
36.       )
    
37.    );
    
38.    s*3+3*2^(n-1)
    
39. }
    

复制代码

比如我们可以得到

1. 1 3
   
2. 2 6
   
3. 3 18
   
4. 4 48
   
5. 5 126
   
6. 6 342
   
7. 7 918
   
8. 8 2460
   
9. 9 6612
   
10. 10 17760
    
11. 11 47688
    
12. 12 128082
    
13. 13 343998
    
14. 14 923862
    
15. 15 2481234
    
16. 16 6663894
    
17. 17 17897268
    
18. 18 48066906
    
19. 19 129093882
    
20. 20 346708896
    
21. 21 931160118
    
22. 22 2500827642
    
23. 23 6716501868
    
24. 24 18038587308
    
25. 25 48446444256
    
26. 26 130113179790
    
27. 27 349446483114
    
28. 28 938512492080
    
29. 29 2520573936528
    
30. 30 6769534793922
    
31. 31 18181018483236
    
32. 32 48828973207602
    
33. 33 131140542357792
    
34. 34 352205682819960
    
35. 35 945922906678356
    
36. 36 2540476173509184
    
37. 37 6822986463912222
    
38. 38 18324574255864524
    
39. 39 49214522619196662
    
40. 40 132176016905843034
    
41. 41 354986668879705980
    
42. 42 953391833346573828
    
43. 43 2560535556899917890
    
44. 44 6876860183640182676
    
45. 45 18469263532739961498
    
46. 46 49603116296198116062
    
47. 47 133219667472530689410
    
48. 48 357789613368544044912
    
49. 49 960919734023567035020
    
50. 50 2580753327472370043522

复制代码

mathe

T[100]=7323449210126924910579630584897430688447422
T[200]=58973109821225628584151275235291933222902630858059057350792683647099233689677890066066
T[300]=474889301775612834272906473038741705758701896942716482748190414113594430033117569849194551248694578007105685835551469017719962148
T[400]=3824113220832045525627522558241021631202697365153751029404405981168332552694693864227943231158062291422426812079607700557852398504950695064477487905774626747272829965249436
T[500]=30794212190217473004355080693399296825536110663498496419203022689517620891763563133653307490204289589983483583339450139180406907503795190311143938090243444891020906285005341257620489384213522272500565009745550121156

iseemu2009

mathe 发表于 2025-3-10 09:12
T[100]=7323449210126924910579630584897430688447422
T[200]=589731098212256285841512752352919332229026 ...

能编出这个程序十分了不起，首先解决了山林的造型方案数，其次解决了着色的问题，两个都是棘手的问题。着色问题可能更难一些。结果中的两个答案和题干中的是一致的，其它的我也不知道正不正确。

iseemu2009

iseemu2009 发表于 2025-3-10 09:18
能编出这个程序十分了不起，首先解决了山林的造型方案数，其次解决了着色的问题，两个都是棘手的问题。着 ...

iseemu2009

      mathe和 Wayne版主都是十分厉害的人，还有 northwolves 和 hujunhua也很优秀，你们应该是数学系毕业的吧。  感觉代数、几何、数学分析、函数、群论、数论等方面什么都懂。不知有些题目你们是一起合作解出的，还是各自独立贡献出的。

iseemu2009

mathe 发表于 2025-3-10 09:12
T[100]=7323449210126924910579630584897430688447422
T[200]=589731098212256285841512752352919332229026 ...

既然找到了解决方法，就看代码能不能优化一下，以提高运算速度。就像求三圆相切那道题，我解决了方案，但程序臃肿，运行S(1234)要十多秒的，经大师改进后1秒运行S（10^9）。