仓库管理员的最优入库方案问题

mathe

如果仅仅对给定的m,n计数，还是13#的方法会更加有效，但是需要改进。

我们知道总层数为k的树，其中k-1层子树至少有两个。
为此，我们可以通过动态规划的方法计算给定黑白点组合和层数，子树的数目。13#给出了比较有效的计算顺序，只是那里的计算不包含层数，而这里应该再添加一个层数
由于最大层数为${m+n-1}/2$,而不同黑白点数目组合也不超过$2n$,所以只需要维护一个大小不超过$n(m+n-1)$的表格。
而13#方法的另外一个问题是从一个子树变换到另外一个子树时需要遍历那两个方程之一的解，复杂度很高，实际上这一步也可能通过动态规划来做，于是复杂度不会超过$O(mn)$,所以总时间复杂度不会超过$O(m^2n^2)$,而空间复杂为为$O(mn)$

mathe

现在上面这个计数算法的c版本实现成功了，原先算法设计中有点bug,花费了不少时间查错。现在版本使用c中int类型，稍大规模就要溢出，还需要进一步完善

mathe

2	3	1
3	4	2
4	5	3
5	6	6
6	7	11
7	8	23
8	9	47
9	10	106
10	11	235
11	12	551
12	13	1301
13	14	3159
14	15	7741
15	16	19320
16	17	48629
17	18	123867
18	19	317955
19	20	823065
20	21	2144505
21	22	5623756
22	23	14828074
23	24	39299897
24	25	104636890
25	26	279793450
26	27	751065460
27	28	2023443032
28	29	5469566585
29	30	14830871802
30	31	40330829030
31	32	109972410221
32	33	300628862480
33	34	823779631721
34	35	2262366343746
35	36	6226306037178
36	37	17169677490714
37	38	47436313524262
38	39	131290543779126
39	40	363990257783343
40	41	1010748076717151
41	42	2810986483493475
42	43	7828986221515605
43	44	21835027912963086
44	45	60978390985918906
45	46	170508699155987862
46	47	477355090753926460
47	48	1337946100045842285
48	49	3754194185716399992
49	50	10545233702911509534
50	51	29650945107763261531
51	52	83453838443384019701
52	53	235105687101888719584
53	54	662938933002209627441
54	55	1870953015095482429652
55	56	5284664207525664213829
56	57	14939085337180746355566
57	58	42263974955306727781419
58	59	119658805094937105691820
59	60	339028211512423891688777
60	61	961243233639785344919176
61	62	2727262741095797582221596
62	63	7742965484889942077995284
63	64	21997089323359313345245965
64	65	62530511740700762556497214
65	66	177860429663307725889568506
66	67	506196780047997923896917090
67	68	1441466514390993079627089660
68	69	4107027983726675748574105451
69	70	11707975085109065447981840723
70	71	33393376702424236289672201975
71	72	95292117715257766905774917747
72	73	272060601835578553646260100204
73	74	777106520339207273555977107291
74	75	2220731733613705624556577459989
75	76	6349023566288361498460378262949
76	77	18159669233225554314045397809352
77	78	51962991177347038094292652008233
78	79	148751315639081644600971284313911
79	80	425993902725552870237427186803242
80	81	1220442849627155768642016018665937
81	82	3497830604170469202903845457503189
82	83	10028668624620644992182332607081494
83	84	28763851562393387023260046860410189
84	85	82528937606397463492066759942909577
85	86	236873932549768979670225075165706000
86	87	680105921158354015451394217097159564
87	88	1953352862527071767266334857497900935
88	89	5612113171411162958611869451001568807
89	90	16129114526453014428399330969621997260
90	91	46369236460936604985435980533014104412
91	92	133346525334880183154734554212495821960
92	93	383586157123256981968757440598369542228
93	94	1103750283120809542081726218017034985435
94	95	3176893930023198882230778966195738823044
95	96	9146521863939247744757005452823121037239
96	97	26340746927568355448185930849816902815332
97	98	75878125200573260074116449602262928034021
98	99	218634714568656691720341715032648263880985
99	100	630134658347465720563607281977639527019590

mathe

3	4	2
4	9	4
5	16	9
6	25	22
7	36	59
8	49	165
9	64	496
10	81	1540
11	100	4960
12	121	16390
13	144	55408
14	169	190572
15	196	665699
16	225	2354932
17	256	8424025
18	289	30424768
19	324	110823984
20	361	406734060
21	400	1502876903
22	441	5586976572
23	484	20884546416
24	529	78460794158
25	576	296124542120
26	625	1122346648913
27	676	4270387848473
28	729	16306781486064
29	784	62476518448854
30	841	240110929120323
31	900	925471008725688
32	961	3576742339562354
33	1024	13858378071668164
34	1089	53823242166325365
35	1156	209507127236520257
36	1225	817228209531058168
37	1296	3194127956059847925
38	1369	12507735436868320178
39	1444	49065838682077543116
40	1521	192803109011754828577
41	1600	758833024052785531214
42	1681	2991173698007584866949
43	1764	11807788265428345268951
44	1849	46676417145532511555986
45	1936	184757059151600200964799
46	2025	732240124602775300011431
47	2116	2905567844262839549011761
48	2209	11542798884848404779311674
49	2304	45906359222118760197623437
50	2401	182766451590253041892450548
51	2500	728389199814734434456161754
52	2601	2905738166496617144231134099
53	2704	11602698412518195685914657256
54	2809	46371974813212181003024225064
55	2916	185494748496499611900421217484
56	3025	742631326551264737554728779512
57	3136	2975551363102126396315168033387
58	3249	11931685256365711329903429125361
59	3364	47881145411216634425327128039475
60	3481	192284612320232832369870790173701
61	3600	772736096464298589254258296620143
62	3721	3107523849163593537210779645844604
63	3844	12505030757335439091581586454363017
64	3969	50353882210731972120391953070110403
65	4096	202885198064954649955372844976540145
66	4225	817953629483348919009340817061449020
67	4356	3299590218673435359129938922007269423
68	4489	13317931459365456586462917680204393281
69	4624	53783834624401066085953770835614339837
70	4761	217319180907315495088579370259754550139
71	4900	878555196006759717717444654899390798514
72	5041	3553517065856577049496248110164837453190
73	5184	14380038590420145286028636909289443549281
74	5329	58219459594441375137701844176103997598589
75	5476	235818122338611774283080481840337834851073
76	5625	955612260190136658227021251929736419297212
77	5776	3874151763561584282255751951152313408527617
78	5929	15712922889941363258425966660924628979340512
79	6084	63755551274877960937125635776014143473139913
80	6241	258794553223363693494241439874499240347631400
81	6400	1050906199036687415311008374834703101544057231
82	6561	4269138366817317400927125255995293001615810010
83	6724	17349216920378417702664551252272785392787446036
84	6889	70530823479024430572328177630860999349594372670
85	7056	286836005421507277597255505382450304296426778046
86	7225	1166918023838862512108721960331277900708982519364
87	7396	4748926693114807565019536243592970522485856672959
88	7569	19332837735401288721827709555372396551218944436056
89	7744	78729496075598242987093721806353710295604734796870
90	7921	320713969802287167993538413588000613443550264099850
91	8100	1306874079060315805253941996431870917162793205600613
92	8281	5326992602131068068801752727801707896706605987568978
93	8464	21720011234206654601671753380265834494386543113196335
94	8649	88585942906684082706175260391143705697418700496734179
95	8836	361404615686947947741782120394628020122955690260212537
96	9025	1474837189746969417734641306962167612357025475885518041
97	9216	6020234897200464001800662206020567717823766615572282414
98	9409	24580986664889670605768247846844524269490990825442690332
99	9604	100392050587511384969394051363517188947692695073023022418

mathe

4	7	2
5	14	3
6	23	6
7	34	11
8	47	23
9	62	47
10	79	106
11	98	235
12	119	551
13	142	1301
14	167	3159
15	194	7741
16	223	19320
17	254	48629
18	287	123867
19	322	317955
20	359	823065
21	398	2144505
22	439	5623756
23	482	14828074
24	527	39299897
25	574	104636890
26	623	279793450
27	674	751065460
28	727	2023443032
29	782	5469566585
30	839	14830871802
31	898	40330829030
32	959	109972410221
33	1022	300628862480
34	1087	823779631721
35	1154	2262366343746
36	1223	6226306037178
37	1294	17169677490714
38	1367	47436313524262
39	1442	131290543779126
40	1519	363990257783343
41	1598	1010748076717151
42	1679	2810986483493475
43	1762	7828986221515605
44	1847	21835027912963086
45	1934	60978390985918906
46	2023	170508699155987862
47	2114	477355090753926460
48	2207	1337946100045842285
49	2302	3754194185716399992
50	2399	10545233702911509534
51	2498	29650945107763261531
52	2599	83453838443384019701
53	2702	235105687101888719584
54	2807	662938933002209627441
55	2914	1870953015095482429652
56	3023	5284664207525664213829
57	3134	14939085337180746355566
58	3247	42263974955306727781419
59	3362	119658805094937105691820
60	3479	339028211512423891688777
61	3598	961243233639785344919176
62	3719	2727262741095797582221596
63	3842	7742965484889942077995284
64	3967	21997089323359313345245965
65	4094	62530511740700762556497214
66	4223	177860429663307725889568506
67	4354	506196780047997923896917090
68	4487	1441466514390993079627089660
69	4622	4107027983726675748574105451
70	4759	11707975085109065447981840723
71	4898	33393376702424236289672201975
72	5039	95292117715257766905774917747
73	5182	272060601835578553646260100204
74	5327	777106520339207273555977107291
75	5474	2220731733613705624556577459989
76	5623	6349023566288361498460378262949
77	5774	18159669233225554314045397809352
78	5927	51962991177347038094292652008233
79	6082	148751315639081644600971284313911
80	6239	425993902725552870237427186803242
81	6398	1220442849627155768642016018665937
82	6559	3497830604170469202903845457503189
83	6722	10028668624620644992182332607081494
84	6887	28763851562393387023260046860410189
85	7054	82528937606397463492066759942909577
86	7223	236873932549768979670225075165706000
87	7394	680105921158354015451394217097159564
88	7567	1953352862527071767266334857497900935
89	7742	5612113171411162958611869451001568807
90	7919	16129114526453014428399330969621997260
91	8098	46369236460936604985435980533014104412
92	8279	133346525334880183154734554212495821960
93	8462	383586157123256981968757440598369542228
94	8647	1103750283120809542081726218017034985435
95	8834	3176893930023198882230778966195738823044
96	9023	9146521863939247744757005452823121037239
97	9214	26340746927568355448185930849816902815332
98	9407	75878125200573260074116449602262928034021
99	9602	218634714568656691720341715032648263880985

mathe

46#同A000055匹配，所以这个问题的解应该和序列A054924关联
我们还可以得出`f(n,n+1)=f(n+1,n^2-2)`,验证了17#hujunhua得出的关系
添加代码到附件:

hujunhua

17#楼的缩减公式还可以得到以下推论：
`f(n+1,n^2-3)=f(n+1,2n)`
`f(n+1,n^2-4)=f(n+1,3n)`
......
`f(n+1,n^2-1-k)=f(n+1,kn),(1\le k\le n-2, \gcd(k,n+1)=1)`