砌砖墙的趣题

王守恩 · 发表于 2025-2-28 19:22:12

已知W(11,3)=18, W(11,8)=220, W(11,18)=52492, W(11,28)=12754588。

W(11,1)=9,
W(11,2)=12,
W(11,3)=18,
W(11,4)=28,
W(11,5)=46,
W(11,6)=76,
W(11,7)=130,
W(11,8)=220,
W(11,9)=382,
W(11,10)=652,
W(11,11)=1138,
W(11,12)=1948,
W(11,13)=3406,
W(11,14)=5836,
W(11,15)=10210,
W(11,16)=17500,
W(11,17)=30622,
W(11,18)=52492,

{12, 18, 28, 46, 76, 130, 220, 382, 652, 1138, 1948, 3406, 5836, 10210, 17500, 30622, 52492, 91858, 157468, 275566, 472396, 826690, 1417180, 2480062, 4251532, 7440178, 12754588, 22320526, 38263756}

LinearRecurrence[{1, 3, -3}, {12, 18, 28}, 29]

yigo · 发表于 2025-2-28 20:11:50

本帖最后由 yigo 于 2025-2-28 22:15 编辑

发现一个思路，对于给定的方案$A_i$,其中长度为2的砖上面必有砖缝（位于两端头的除外），因为假如没有缝，那么其上面要覆盖这个砖，至少要1块长度为4的砖，矛盾。
所以我们只需要求夹在2个长度2中间有n个连续的长度为3的错缝方案，这个也容易求得为（n+1）种方案，其上1层有且仅有1个长度为2的砖，依次对应下1层的n+1个缝，所以是（n+1）种方案。
对于位于端头的n个连续的长度为3的错缝方案数也类似的容易求得为n种方案。
总的可邻方案，就是所有连续长度为3的方案的乘积。
现在只需要对每一种方案按1，2，3，...序数一一对应的编码，也就是给定一个序数就能翻译出来方案的排列，给定一个排列就能求出序数，那么传递矩阵就求出来了

例如：3332323233322
端头3个3的1个，有3种方案
中间1个3的2个，有$(1+1)^2$=4种
中间3个3的1个，有3+1=4种
所以一共有3*4*4=48种可邻方案。

以上没考虑完全，还要考虑端头为2然后接3的情况，例如23333332，23322232222
对于两端为2，中间都为3的，例如23333332，可邻方案为0，
对于夹在一个端头2和一个中间2的n个连续3，只有1种可邻方案。

还有一种情况，全部都是3的（n个），例如3333333，这种情况等价于2个中间2夹了（n-2）个3，有（n-1）种方案。

好像也挺麻烦，还要考虑一个端头2接全部3的，例如23333333，3333332，这种情只有1种可邻方案。

整理下：
                              （中2，n个3，中2）方案数：n+1
（端2，n个3，中2）或（中2，n个3，端2）方案数：1
                              （端2，n个3，端2）方案数：0
      （中2，端n个3）或（端n个3，中2）方案数：n
      （端2，端n个3）或（端n个3，端2）方案数：1
                                             （n个3）方案数：n-1

猜想：可邻方案相邻两层的的砖数量相差不超过1。

按2，3砖头的组合分类计算墙长为n的单层方案数：$ \displaystyle F_n=\sum_{2a+3b=n}C_{a+b}^a$
是否能求出各a+b情况下的可邻方案数，然后求得$W(n,2)$

mathe · 发表于 2025-2-28 20:33:40

使用大整数比较消耗内存，而且程序本身也很难并行化，不能充分利用CPU.
所以我试了一下，采用不同的模使用64位无符号整数计算。不同的模可以并行计算，对于高度25，计算速度和大整数基本相同，8个模同时计算内存开销大概9G

W(5,25)%(2^64-9)=2
W(5,25)%(2^64-5)=2
W(5,25)%(2^64-0)=2
W(5,25)%(2^64-1)=2
W(5,25)%(2^64-15)=2
W(5,25)%(2^64-3)=2
W(5,25)%(2^64-33)=2
W(5,25)%(2^64-17)=2
W(6,25)%(2^64-9)=2
W(6,25)%(2^64-15)=2
W(6,25)%(2^64-0)=2
W(6,25)%(2^64-1)=2
W(6,25)%(2^64-33)=2
W(6,25)%(2^64-3)=2
W(6,25)%(2^64-17)=2
W(6,25)%(2^64-5)=2
W(7,25)%(2^64-9)=2
W(7,25)%(2^64-15)=2
W(7,25)%(2^64-0)=2
W(7,25)%(2^64-1)=2
W(7,25)%(2^64-33)=2
W(7,25)%(2^64-3)=2
W(7,25)%(2^64-17)=2
W(7,25)%(2^64-5)=2
W(8,25)%(2^64-15)=4
W(8,25)%(2^64-9)=4
W(8,25)%(2^64-0)=4
W(8,25)%(2^64-1)=4
W(8,25)%(2^64-33)=4
W(8,25)%(2^64-3)=4
W(8,25)%(2^64-17)=4
W(8,25)%(2^64-5)=4
W(9,25)%(2^64-15)=12290
W(9,25)%(2^64-9)=12290
W(9,25)%(2^64-0)=12290
W(9,25)%(2^64-1)=12290
W(9,25)%(2^64-3)=12290
W(9,25)%(2^64-33)=12290
W(9,25)%(2^64-5)=12290
W(9,25)%(2^64-17)=12290
W(10,25)%(2^64-15)=392838
W(10,25)%(2^64-9)=392838
W(10,25)%(2^64-0)=392838
W(10,25)%(2^64-1)=392838
W(10,25)%(2^64-3)=392838
W(10,25)%(2^64-33)=392838
W(10,25)%(2^64-5)=392838
W(10,25)%(2^64-17)=392838
W(11,25)%(2^64-15)=2480062
W(11,25)%(2^64-9)=2480062
W(11,25)%(2^64-0)=2480062
W(11,25)%(2^64-1)=2480062
W(11,25)%(2^64-33)=2480062
W(11,25)%(2^64-3)=2480062
W(11,25)%(2^64-5)=2480062
W(11,25)%(2^64-17)=2480062
W(12,25)%(2^64-15)=9657426
W(12,25)%(2^64-9)=9657426
W(12,25)%(2^64-0)=9657426
W(12,25)%(2^64-1)=9657426
W(12,25)%(2^64-33)=9657426
W(12,25)%(2^64-5)=9657426
W(12,25)%(2^64-3)=9657426
W(12,25)%(2^64-17)=9657426
W(13,25)%(2^64-15)=1520800788
W(13,25)%(2^64-9)=1520800788
W(13,25)%(2^64-1)=1520800788
W(13,25)%(2^64-0)=1520800788
W(13,25)%(2^64-33)=1520800788
W(13,25)%(2^64-5)=1520800788
W(13,25)%(2^64-3)=1520800788
W(13,25)%(2^64-17)=1520800788
W(14,25)%(2^64-15)=81099699600
W(14,25)%(2^64-9)=81099699600
W(14,25)%(2^64-1)=81099699600
W(14,25)%(2^64-33)=81099699600
W(14,25)%(2^64-0)=81099699600
W(14,25)%(2^64-5)=81099699600
W(14,25)%(2^64-17)=81099699600
W(14,25)%(2^64-3)=81099699600
W(15,25)%(2^64-15)=1070947317284
W(15,25)%(2^64-9)=1070947317284
W(15,25)%(2^64-1)=1070947317284
W(15,25)%(2^64-33)=1070947317284
W(15,25)%(2^64-5)=1070947317284
W(15,25)%(2^64-0)=1070947317284
W(15,25)%(2^64-17)=1070947317284
W(15,25)%(2^64-3)=1070947317284
W(16,25)%(2^64-15)=7567210394496
W(16,25)%(2^64-9)=7567210394496
W(16,25)%(2^64-33)=7567210394496
W(16,25)%(2^64-5)=7567210394496
W(16,25)%(2^64-1)=7567210394496
W(16,25)%(2^64-0)=7567210394496
W(16,25)%(2^64-3)=7567210394496
W(16,25)%(2^64-17)=7567210394496
W(17,25)%(2^64-15)=323112665126676
W(17,25)%(2^64-9)=323112665126676
W(17,25)%(2^64-33)=323112665126676
W(17,25)%(2^64-1)=323112665126676
W(17,25)%(2^64-5)=323112665126676
W(17,25)%(2^64-0)=323112665126676
W(17,25)%(2^64-17)=323112665126676
W(17,25)%(2^64-3)=323112665126676
W(18,25)%(2^64-15)=17168200217797014
W(18,25)%(2^64-9)=17168200217797014
W(18,25)%(2^64-33)=17168200217797014
W(18,25)%(2^64-1)=17168200217797014
W(18,25)%(2^64-5)=17168200217797014
W(18,25)%(2^64-0)=17168200217797014
W(18,25)%(2^64-17)=17168200217797014
W(18,25)%(2^64-3)=17168200217797014
W(19,25)%(2^64-15)=359314690911084474
W(19,25)%(2^64-9)=359314690911084474
W(19,25)%(2^64-33)=359314690911084474
W(19,25)%(2^64-1)=359314690911084474
W(19,25)%(2^64-5)=359314690911084474
W(19,25)%(2^64-0)=359314690911084474
W(19,25)%(2^64-17)=359314690911084474
W(19,25)%(2^64-3)=359314690911084474
W(20,25)%(2^64-15)=3776799901766934940
W(20,25)%(2^64-9)=3776799901766934940
W(20,25)%(2^64-33)=3776799901766934940
W(20,25)%(2^64-1)=3776799901766934940
W(20,25)%(2^64-5)=3776799901766934940
W(20,25)%(2^64-0)=3776799901766934940
W(20,25)%(2^64-3)=3776799901766934940
W(20,25)%(2^64-17)=3776799901766934940
W(21,25)%(2^64-15)=7232511435196864588
W(21,25)%(2^64-9)=7232511435196864564
W(21,25)%(2^64-33)=7232511435196864660
W(21,25)%(2^64-5)=7232511435196864548
W(21,25)%(2^64-1)=7232511435196864532
W(21,25)%(2^64-0)=7232511435196864528
W(21,25)%(2^64-17)=7232511435196864596
W(21,25)%(2^64-3)=7232511435196864540
W(22,25)%(2^64-15)=162778388101501138
W(22,25)%(2^64-9)=162778388101499794
W(22,25)%(2^64-33)=162778388101505170
W(22,25)%(2^64-5)=162778388101498898
W(22,25)%(2^64-1)=162778388101498002
W(22,25)%(2^64-0)=162778388101497778
W(22,25)%(2^64-3)=162778388101498450
W(22,25)%(2^64-17)=162778388101501586
W(23,25)%(2^64-15)=2135191765218303950
W(23,25)%(2^64-9)=2135191765218270578
W(23,25)%(2^64-33)=2135191765218404066
W(23,25)%(2^64-5)=2135191765218248330
W(23,25)%(2^64-1)=2135191765218226082
W(23,25)%(2^64-0)=2135191765218220520
W(23,25)%(2^64-3)=2135191765218237206
W(23,25)%(2^64-17)=2135191765218315074
W(24,25)%(2^64-15)=18109500207517632754
W(24,25)%(2^64-9)=18109500207517139086
W(24,25)%(2^64-33)=18109500207519113758
W(24,25)%(2^64-5)=18109500207516809974
W(24,25)%(2^64-1)=18109500207516480862
W(24,25)%(2^64-0)=18109500207516398584
W(24,25)%(2^64-17)=18109500207517797310
W(24,25)%(2^64-3)=18109500207516645418
W(25,25)%(2^64-15)=5245835211300854865
W(25,25)%(2^64-33)=5245835211326527815
W(25,25)%(2^64-9)=5245835211292297215
W(25,25)%(2^64-5)=5245835211286592115
W(25,25)%(2^64-1)=5245835211280887015
W(25,25)%(2^64-0)=5245835211279460740
W(25,25)%(2^64-17)=5245835211303707415
W(25,25)%(2^64-3)=5245835211283739565
W(26,25)%(2^64-15)=5875303495333915447
W(26,25)%(2^64-33)=5875303496284769389
W(26,25)%(2^64-9)=5875303495016964133
W(26,25)%(2^64-5)=5875303494805663257
W(26,25)%(2^64-1)=5875303494594362381
W(26,25)%(2^64-0)=5875303494541537162
W(26,25)%(2^64-17)=5875303495439565885
W(26,25)%(2^64-3)=5875303494700012819
W(27,25)%(2^64-15)=14806236966393664954
W(27,25)%(2^64-33)=14806236995251054462
W(27,25)%(2^64-9)=14806236956774535118
W(27,25)%(2^64-1)=14806236943949028670
W(27,25)%(2^64-5)=14806236950361781894
W(27,25)%(2^64-0)=14806236942345840364
W(27,25)%(2^64-17)=14806236969600041566
W(27,25)%(2^64-3)=14806236947155405282
W(28,25)%(2^64-15)=8821211680285292875
W(28,25)%(2^64-33)=8821212183310432297
W(28,25)%(2^64-9)=8821211512610246401
W(28,25)%(2^64-1)=8821211289043517769
W(28,25)%(2^64-5)=8821211400826882085
W(28,25)%(2^64-0)=8821211261097676690
W(28,25)%(2^64-17)=8821211736176975033
W(28,25)%(2^64-3)=8821211344935199927
W(29,25)%(2^64-15)=12167787278085398054
W(29,25)%(2^64-33)=12167795788955162594
W(29,25)%(2^64-9)=12167784441128809874
W(29,25)%(2^64-1)=12167780658520025634
W(29,25)%(2^64-5)=12167782549824417754
W(29,25)%(2^64-0)=12167780185693927604
W(29,25)%(2^64-17)=12167788223737594114
W(29,25)%(2^64-3)=12167781604172221694
W(30,25)%(2^64-15)=11800994065033106276
W(30,25)%(2^64-33)=11801254454254358792
W(30,25)%(2^64-1)=11800791540083243208
W(30,25)%(2^64-9)=11800907268626022104
W(30,25)%(2^64-5)=11800849404354632656
W(30,25)%(2^64-0)=11800777074015395846
W(30,25)%(2^64-3)=11800820472218937932
W(30,25)%(2^64-17)=11801022997168801000
W(31,25)%(2^64-15)=8789085670403391278
W(31,25)%(2^64-33)=8796717064301228402
W(31,25)%(2^64-1)=8783150141816184626
W(31,25)%(2^64-5)=8784846007126815098
W(31,25)%(2^64-9)=8786541872437445570
W(31,25)%(2^64-0)=8782726175488527008
W(31,25)%(2^64-17)=8789933603058706514
W(31,25)%(2^64-3)=8783998074471499862
W(32,25)%(2^64-15)=14265238912822194812
W(32,25)%(2^64-33)=14430136866194615336
W(32,25)%(2^64-1)=14136984949088089960
W(32,25)%(2^64-5)=14173628938726405632
W(32,25)%(2^64-9)=14210272928364721304
W(32,25)%(2^64-0)=14127823951678511042
W(32,25)%(2^64-17)=14283560907641352648
W(32,25)%(2^64-3)=14155306943907247796
W(33,25)%(2^64-15)=17076373179218176320
W(33,25)%(2^64-33)=1506337507801232261
W(33,25)%(2^64-1)=14838933310768370468
W(33,25)%(2^64-5)=15478201844611172140
W(33,25)%(2^64-9)=16117470378453973812
W(33,25)%(2^64-0)=14679116177307670050
W(33,25)%(2^64-17)=17396007446139577156
W(33,25)%(2^64-3)=15158567577689771304
W(34,25)%(2^64-15)=9183668227301060899
W(34,25)%(2^64-33)=6301773155524829061
W(34,25)%(2^64-1)=9375503941603735582
W(34,25)%(2^64-5)=6685444584130178291
W(34,25)%(2^64-9)=3995385226656621008
W(34,25)%(2^64-0)=5436332762544737002
W(34,25)%(2^64-17)=17062010585419058065
W(34,25)%(2^64-3)=17253846299721732742
W(35,25)%(2^64-15)=4580042873707847880
W(35,25)%(2^64-33)=16812657140477506425
W(35,25)%(2^64-1)=13512531406596556872
W(35,25)%(2^64-5)=16230890132545368786
W(35,25)%(2^64-9)=502504784784629301
W(35,25)%(2^64-0)=3609569688254578118
W(35,25)%(2^64-17)=5939222236682254177
W(35,25)%(2^64-3)=14871710769570962803
W(36,25)%(2^64-15)=10357141621289609816
W(36,25)%(2^64-33)=14989114973143544517
W(36,25)%(2^64-1)=2655219220134492743
W(36,25)%(2^64-5)=18032014244542771466
W(36,25)%(2^64-9)=14962065195241503278
W(36,25)%(2^64-0)=3422706482459811700
W(36,25)%(2^64-17)=8822167096638981014
W(36,25)%(2^64-3)=1120244695483855711
W(37,25)%(2^64-15)=4026636480845464594
W(37,25)%(2^64-33)=3130037779843605828
W(37,25)%(2^64-1)=2674352795658242845
W(37,25)%(2^64-5)=425470409467398586
W(37,25)%(2^64-9)=16623332096986197558
W(37,25)%(2^64-0)=17071631447488131938
W(37,25)%(2^64-17)=12125567324604967152
W(37,25)%(2^64-3)=10773283639417585069
W(38,25)%(2^64-15)=6998931171863017761
W(38,25)%(2^64-33)=4982317124229917701
W(38,25)%(2^64-1)=10617046994907741388
W(38,25)%(2^64-5)=12218548770279450139
W(38,25)%(2^64-9)=13820050545653232386
W(38,25)%(2^64-0)=14828357569492526088
W(38,25)%(2^64-17)=17023054096407017368
W(38,25)%(2^64-3)=2194425845738560770
W(39,25)%(2^64-15)=221769856697629029
W(39,25)%(2^64-33)=8978369783018285927
W(39,25)%(2^64-1)=9808186869199917439
W(39,25)%(2^64-5)=9704459733230302912
W(39,25)%(2^64-9)=9600732597316948553
W(39,25)%(2^64-0)=5222432634773723818
W(39,25)%(2^64-17)=9393278325659020339
W(39,25)%(2^64-3)=532951264353301848
W(40,25)%(2^64-15)=10578052741953702345
W(40,25)%(2^64-33)=13263996211084761695
W(40,25)%(2^64-1)=290432697722773475
W(40,25)%(2^64-5)=11135500168728984974
W(40,25)%(2^64-9)=3533823567459591386
W(40,25)%(2^64-0)=2190851848622662648
W(40,25)%(2^64-3)=14936338469901411716
W(40,25)%(2^64-17)=6777214442932195393
W(41,25)%(2^64-15)=18181002915128575395
W(41,25)%(2^64-33)=7692234894085300347
W(41,25)%(2^64-1)=14041104618362298641
W(41,25)%(2^64-5)=17859181820586786938
W(41,25)%(2^64-9)=3230514977864087860
W(41,25)%(2^64-0)=8474899303872908074
W(41,25)%(2^64-17)=10866669526124885622
W(41,25)%(2^64-3)=6726771179024471454
W(42,25)%(2^64-15)=11524969900616186111
W(42,25)%(2^64-33)=13865644209680462560
W(42,25)%(2^64-1)=13803730616725330302
W(42,25)%(2^64-5)=18423153654799522802
W(42,25)%(2^64-9)=4595833241870617103
W(42,25)%(2^64-0)=12648874954504665522
W(42,25)%(2^64-17)=13834682431551269151
W(42,25)%(2^64-3)=16113442057924119876
W(43,25)%(2^64-15)=2576430222222390963
W(43,25)%(2^64-33)=16954862063649481244
W(43,25)%(2^64-1)=7790542534183094244
W(43,25)%(2^64-5)=8936024666811960711
W(43,25)%(2^64-9)=10081523316170664866
W(43,25)%(2^64-0)=12115860600192302670
W(43,25)%(2^64-17)=12372570165077586240
W(43,25)%(2^64-3)=17586653572761073573
W(44,25)%(2^64-15)=17749636305704925755
W(44,25)%(2^64-33)=2133090725617245474
W(44,25)%(2^64-5)=12081575869403546327
W(44,25)%(2^64-1)=13504410213820816986
W(44,25)%(2^64-9)=10659147070241082588
W(44,25)%(2^64-0)=9248496147943810328
W(44,25)%(2^64-17)=7815506107680575870
W(44,25)%(2^64-3)=3569570311600554985
W(45,25)%(2^64-15)=8034372774153937617
W(45,25)%(2^64-33)=5590116421606143281
W(45,25)%(2^64-5)=5372528164016907779
W(45,25)%(2^64-1)=8013041465669492010
W(45,25)%(2^64-9)=2741101908630315460
W(45,25)%(2^64-0)=4062903623634311400
W(45,25)%(2^64-17)=15952254610364658157
W(45,25)%(2^64-3)=15915020970914726712
W(46,25)%(2^64-15)=3735178059044084290
W(46,25)%(2^64-33)=2858557174682963297
W(46,25)%(2^64-5)=3861030710964467456
W(46,25)%(2^64-1)=15317114071940293805
W(46,25)%(2^64-9)=11044660484259302498
W(46,25)%(2^64-0)=4376228272614760084
W(46,25)%(2^64-17)=7544083138822750311
W(46,25)%(2^64-3)=341579222027466101
W(47,25)%(2^64-15)=18102680943020383283
W(47,25)%(2^64-33)=2294678570910755403
W(47,25)%(2^64-5)=16562231073131957768
W(47,25)%(2^64-1)=5682963521538031959
W(47,25)%(2^64-0)=17528888302320910290
W(47,25)%(2^64-9)=13671129676771186826
W(47,25)%(2^64-17)=3471308187604657935
W(47,25)%(2^64-3)=1314678369760862200
W(48,25)%(2^64-15)=8239680042523213292
W(48,25)%(2^64-33)=11003318472521251940
W(48,25)%(2^64-5)=6416438650171466831
W(48,25)%(2^64-1)=4399781813179563883
W(48,25)%(2^64-0)=4439487010130928870
W(48,25)%(2^64-17)=3836203841266577571
W(48,25)%(2^64-9)=845813242613419506
W(48,25)%(2^64-3)=8662363521457953098
W(49,25)%(2^64-15)=311675289891392198
W(49,25)%(2^64-33)=1226220781997756592
W(49,25)%(2^64-5)=5581172323726647518
W(49,25)%(2^64-1)=12943763170641733358
W(49,25)%(2^64-0)=12618339589106727790
W(49,25)%(2^64-17)=14686075378651587051
W(49,25)%(2^64-9)=6491818088374851952
W(49,25)%(2^64-3)=3616627152311391360
W(50,25)%(2^64-15)=7490666880981080310
W(50,25)%(2^64-33)=5850708075115405057
W(50,25)%(2^64-5)=11543297938384530806
W(50,25)%(2^64-1)=6823888944328848126
W(50,25)%(2^64-0)=7713173222682618082
W(50,25)%(2^64-17)=5543949554239649261
W(50,25)%(2^64-3)=3838935405120625433
W(50,25)%(2^64-9)=3679739001200090273
W(51,25)%(2^64-15)=3020523150064923307
W(51,25)%(2^64-33)=1116690659738016561
W(51,25)%(2^64-5)=2949444424957117210
W(51,25)%(2^64-1)=8434247291672575987
W(51,25)%(2^64-0)=15897605526866534306
W(51,25)%(2^64-17)=10141002095509250596
W(51,25)%(2^64-3)=6352143065615608496
W(51,25)%(2^64-9)=10629007973545573860
W(52,25)%(2^64-15)=6480993118149524142
W(52,25)%(2^64-33)=4140838053850936493
W(52,25)%(2^64-5)=6041887427717806343
W(52,25)%(2^64-1)=8797827952647246965
W(52,25)%(2^64-0)=3160438664791655276
W(52,25)%(2^64-17)=9406356377334275756
W(52,25)%(2^64-3)=1412910781226457419
W(52,25)%(2^64-9)=14448034027029012243
W(53,25)%(2^64-15)=1989045467662681758
W(53,25)%(2^64-33)=10599201784483551181
W(53,25)%(2^64-5)=11559339842093605718
W(53,25)%(2^64-1)=3910732886549241988
W(53,25)%(2^64-17)=8332636057973297433
W(53,25)%(2^64-0)=12173682486478057622
W(53,25)%(2^64-3)=3284304107994533722
W(53,25)%(2^64-9)=17920316701103990498
W(54,25)%(2^64-15)=16907056551592118758
W(54,25)%(2^64-33)=967800840446145522
W(54,25)%(2^64-5)=1498976597611820348
W(54,25)%(2^64-1)=4830567770895418291
W(54,25)%(2^64-17)=2975889250566257719
W(54,25)%(2^64-0)=12111122080267277630
W(54,25)%(2^64-3)=18298065452125966177
W(54,25)%(2^64-9)=6228247803194581394
W(55,25)%(2^64-15)=2056669567252187063
W(55,25)%(2^64-33)=15174628044402711378
W(55,25)%(2^64-5)=12734078216308792804
W(55,25)%(2^64-1)=13629303099561337207
W(55,25)%(2^64-17)=55592496318566962
W(55,25)%(2^64-0)=9269424163156943934
W(55,25)%(2^64-3)=7625266738385435599
W(55,25)%(2^64-9)=950012603826662392
W(56,25)%(2^64-15)=2605906317112036036
W(56,25)%(2^64-33)=8805266971808780615
W(56,25)%(2^64-5)=295249844032458801
W(56,25)%(2^64-1)=3696918831709682117
W(56,25)%(2^64-17)=4922015024650668069
W(56,25)%(2^64-0)=9545264672011094600
W(56,25)%(2^64-3)=1687090067372778256
W(56,25)%(2^64-9)=17812282462603399964
W(57,25)%(2^64-15)=12936527323109398237
W(57,25)%(2^64-33)=18390297746672707721
W(57,25)%(2^64-5)=10895545234502855496
W(57,25)%(2^64-1)=847862985537281172
W(57,25)%(2^64-17)=2536965827817182387
W(57,25)%(2^64-0)=6076249282172406584
W(57,25)%(2^64-3)=7058151353111963808
W(57,25)%(2^64-9)=11451727927384625676
W(58,25)%(2^64-15)=16236934282570160052
W(58,25)%(2^64-33)=15185269535056980987
W(58,25)%(2^64-5)=14657407895172751564
W(58,25)%(2^64-1)=3737702085296350171
W(58,25)%(2^64-0)=17547032940729642658
W(58,25)%(2^64-17)=7403909153169773626
W(58,25)%(2^64-3)=8878756994396508311
W(58,25)%(2^64-9)=9682561615848972514
W(59,25)%(2^64-15)=1345042213526693365
W(59,25)%(2^64-33)=8716882162046388166
W(59,25)%(2^64-5)=15710070472925222300
W(59,25)%(2^64-1)=169191255419904514
W(59,25)%(2^64-17)=18418966468893898749
W(59,25)%(2^64-0)=18084555188341887172
W(59,25)%(2^64-3)=1564643371668048718
W(59,25)%(2^64-9)=8504944485893986770
W(60,25)%(2^64-15)=7434574994974845861
W(60,25)%(2^64-33)=8057080275080339104
W(60,25)%(2^64-5)=16449609146447014220
W(60,25)%(2^64-1)=9563539416834527048
W(60,25)%(2^64-0)=9819065532571046582
W(60,25)%(2^64-3)=3985405856244468844
W(60,25)%(2^64-17)=4135811295630670450
W(60,25)%(2^64-9)=4244681229094446989

复制代码

由此推测，在我的机器上，计算一轮高度位30的大概5天左右. 而使用一个模需要36G内存，应该可以同时计算两个模。
但是如果要计算出W(60,30)那就需要很多轮了，时间花费比较大。当然如果有多台36G以上内存机器，就可以并行计算了

iseemu2009 · 发表于 2025-2-28 22:35:48

mathe 发表于 2025-2-28 20:33
使用大整数比较消耗内存，而且程序本身也很难并行化，不能充分利用CPU.
所以我试了一下，采用不同的模使用 ...

这是一道国外的征解题，既考思维能力，也考编程能力，更考验计算机的性能。

mathe · 发表于 2025-3-1 08:56:59

yigo 发表于 2025-2-26 12:02
长度为 n 的墙，一层的铺设方案数记为`F_n`, 则$F_n=F_{n-2}+F_{n-3},F_2=1,F_3=1,F_4=1$,
例如$F_9=5$ ...

这个方法宽度60对应的点的数目为8745217(N[n]=N[n-2]+N[n-3])，还可以，不算太大。
点之间连线数目为825604416 （E[n]=E[n-2]+E[n-3]+E[n-4]).
所以通过计算机来保存这个图还是有可能的。
然后我们需要使用双缓冲，保存两个点对应的权重数组。
开始权重数组初始化为1，然后每轮，每个值更新为所有相邻点上一轮权重值之和。看上去这个计算量也还可以。
关键是前面建图部分。需要需要对点做适当编码。由于点的数目不算太多，看上去这个计算量应该还行。

wayne · 发表于 2025-3-1 10:10:15

yigo 发表于 2025-2-26 12:02
长度为 n 的墙，一层的铺设方案数记为`F_n`, 则$F_n=F_{n-2}+F_{n-3},F_2=1,F_3=1,F_4=1$,
例如$F_9=5$ ...

确实很吃内存.w=30的时候,就是一个1897*1897的矩阵运算.

Block[{w=30,h=28,offset},offset=Ceiling[w/3];len=Sum[Binomial[offset+c,w-2offset-2c],{c,0,Floor[w/2]-offset}];
mat=ConstantArray[0,{len,len}];states=Flatten[Table[Permutations[Flatten[{ConstantArray[2,3offset-w+3c],ConstantArray[3,w-2offset-2c]}],{offset+c}],{c,0,Floor[w/2]-offset}],1];
Do[If[Length@Intersection[Accumulate[states[[i]]],Accumulate[states[[j]]]]==1,mat[[i,j]]=1;mat[[j,i]]=1;],{i,len},{j,i+1,len}];Total[Flatten[MatrixPower[mat,h-1]]]]

复制代码

W(30,m)的解:

{3,221490}
{4,3025552}
{5,47054902}
{6,727476474}
{7,12197221792}
{8,197913291570}
{9,3436223965722}
{10,56962090003246}
{11,1007720438618812}
{12,16879522589829476}
{13,302089555859830370}
{14,5088301462723893518}
{15,91808796148300180560}
{16,1551567154543051987416}
{17,28174558586878592809126}
{18,477225542588996664792450}
{19,8712581510423489755735442}
{20,147825618564886801407248168}
{21,2711527396249657773627781350}
{22,46069348846175636351375469424}
{23,848567050101343584172737241622}
{24,14433995561864231604126033765626}
{25,266851851333217064780761363832838}
{26,4543637427836323016345009219266474}
{27,84278137311704840407032564756114880}
{28,1436232808487659942960885259827737780}
{29,26717502809242041328475910348414617018}
{30,455652300248630590498434405265945026140}
{31,8497863623195960025390952605756731472584}
{32,145021488810044832183976502866634491970150}
{33,2710644212856561264558082955730853965549130}
{34,46285179295205940188747673889111238477865932}
{35,866799061845606620866834570963167314500714056}
{36,14808154423797373010176553858712140569934079842}
{37,277779078008842436134910479617974587815548409364}
{38,4747503523748304572938330123809732786729494643834}
{39,89183554834677680396767305897032411382240301864094}

复制代码

wayne · 发表于 2025-3-1 10:18:50

高度好说,因为是对数级别的复杂度, 主要是墙的宽度,宽度为n的时候,对应的矩阵就维度是指数级别的飙升.
递归公式是$W_{n+3} = W_{n+1}+W_{n}, W_3=1,W_4=1,W_5=2$

Sum[Multinomial[3Ceiling[n/3]-n+3c,n-2Ceiling[n/3]-2c],{c,0,Floor[n/2]-Ceiling[n/3]}]

复制代码

mathe算到宽度为60,意味着是8745217*8745217的矩阵运算.

{{3,1},{4,1},{5,2},{6,2},{7,3},{8,4},{9,5},{10,7},{11,9},{12,12},{13,16},{14,21},{15,28},{16,37},{17,49},{18,65},{19,86},{20,114},{21,151},{22,200},{23,265},{24,351},{25,465},{26,616},{27,816},{28,1081},{29,1432},{30,1897},{31,2513},{32,3329},{33,4410},{34,5842},{35,7739},{36,10252},{37,13581},{38,17991},{39,23833},{40,31572},{41,41824},{42,55405},{43,73396},{44,97229},{45,128801},{46,170625},{47,226030},{48,299426},{49,396655},{50,525456},{51,696081},{52,922111},{53,1221537},{54,1618192},{55,2143648},{56,2839729},{57,3761840},{58,4983377},{59,6601569},{60,8745217},{61,11584946},{62,15346786},{63,20330163},{64,26931732},{65,35676949},{66,47261895},{67,62608681},{68,82938844},{69,109870576},{70,145547525},{71,192809420},{72,255418101},{73,338356945},{74,448227521},{75,593775046},{76,786584466},{77,1042002567},{78,1380359512},{79,1828587033},{80,2422362079},{81,3208946545},{82,4250949112},{83,5631308624},{84,7459895657},{85,9882257736},{86,13091204281},{87,17342153393},{88,22973462017},{89,30433357674},{90,40315615410},{91,53406819691},{92,70748973084},{93,93722435101},{94,124155792775},{95,164471408185},{96,217878227876},{97,288627200960},{98,382349636061},{99,506505428836},{100,670976837021}}

复制代码

aimisiyou · 发表于 2025-3-1 10:36:08

若仅考虑两层，宽度为L的排列总数。能否有公式？

wayne · 发表于 2025-3-1 10:50:15

2层高的递归表达式是{a[3+n]==a[n]+a[2+n],a[3]==0,a[4]==0,a[5]==2}
3层高的递归表达式是{a[9+n]==a[n]-3 a[3+n]+a[4+n]+3 a[6+n]+a[7+n],a[3]==0,a[4]==0,a[5]==2,a[6]==2,a[7]==2,a[8]==4,a[9]==8,a[10]==12,a[11]==18}
4层高的递归表达式是{a[12+n]==-a[n]+a[2+n]+4 a[3+n]-a[5+n]-6 a[6+n]+a[7+n]-a[8+n]+4 a[9+n]+a[11+n],a[3]==0,a[4]==0,a[5]==2,a[6]==2,a[7]==2,a[8]==4,a[9]==10,a[10]==18,a[11]==28,a[12]==52,a[13]==104,a[14]==188}

wayne · 发表于 2025-3-1 11:03:37

mathe 发表于 2025-2-27 14:19

3层高的递推公式也是有的,所以可以轻松秒杀.

dd=LinearRecurrence[{0,1,3,0,1,-3,0,0,1},{0,0,2,2,2,4,8,12,18},100];
Transpose[{2+Range[Length[dd]],dd}]

复制代码

前面的跟mathe的是一致的,就不贴了,我贴100-150的:

{{100,201271695688369483296},{101,329214755370841009996},{102,538487822771424279538},{103,880790206290231824424},{104,1440685108349910974798},{105,2356490322565859378032},{106,3854448522050825581598},{107,6304618937072171216380},{108,10312297500583375816834},{109,16867550688392232945996},{110,27589804064686856929608},{111,45127908567267032123538},{112,73814519707073482063606},{113,120736446559044376054854},{114,197485393918082543307746},{115,323021606201825805918890},{116,528357848905494304023402},{117,864220879461929197351954},{118,1413583105637187884590104},{119,2312160284484048381494952},{120,3781939077037820684765156},{121,6186017151402702403595602},{122,10118303709794456490586614},{123,16550240243685647293733058},{124,27070787737776874235016950},{125,44278967445560186609796602},{126,72425929268584985662868212},{127,118465166020114346479237364},{128,193770321004051871695726186},{129,316944959909627056506424932},{130,518418440448027177441779632},{131,847963253563481553917668510},{132,1386990938634953383745420214},{133,2268664185589048792736038450},{134,3710793663668429673527468720},{135,6069646491481639937557672140},{136,9927959318675090419807151048},{137,16238898981435489551828219170},{138,26561535122713825930486370208},{139,43445996484810071284010805316},{140,71063460821060127056863962208},{141,116236612635816673066349470782},{142,190125135486489607994039182632},{143,310982626941072841185470538824},{144,508666011002089860623196961810},{145,832011464085846668792226784028},{146,1360899020979380165627194381610},{147,2225986329793869665387294809952},{148,3640986630203334260491238529938},{149,5955464983731941626392527262328},{150,9741195663300337016642108329174}}

复制代码

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 砌砖墙的趣题

点评

点评

评分

点评

点评

点评