《某不科学的超数列求和2》备忘1
需积分: 0 65 浏览量
2022-08-03
20:23:05
上传
评论
收藏 71KB PDF 举报
《某不科学的超数列求和 2》备忘
更新记录
解题思路
我们先简化一下题目
∑
x
1
=1
n
∑
x
2
=1
x
1
...
∑
x
m
=1
x
m −1
1
其实就是求 m 个高度为[1,n]的整数，且依次单调不降的柱子的种类数。
这个就相当于将 n-1 次上升的机会分配给 m 个柱子，允许剩余，允许为空。允许剩余就可
以加 1 个空柱子，成 m+1 个柱子，于是变成了将 n-1 个物品分给 m+1 个人，可为 0，不许
剩余的方案数，用隔板法即可。结果是
C
n +m−1
m
我们考虑转化
x
m
i
，设
x
m
为 n，i 为 m
我们发现
C
n +m−1
m
=
(n+m−1)!
m!(n−1)!
=
∏
i=n
n+m −1
i
m!
如 果 将 n 看 做 变 量 ， m 看 做 常 数 ， 则 得 到 一 个 关 于 n 的 m 次 多 项 式 ， 不 妨 设 其 为
∑
i=0
m
a
i
n
i
，算出
a
i
复杂度
O(m
3
)
则可以得到
n
m
=
1
a
m
（
∑
i=0
m
a
i
n
i
−
∑
i=0
m−1
a
i
n
i
）
=
1
a
m
（ C
n−m +1
m
−
∑
i=0
m−1
a
i
n
i
）
=
1
a
m
(
∑
x
1
=1
n
∑
x
2
=1
x
1
...
∑
x
m
=1
x
m −1
1−
∑
i=0
m−1
a
i
n
i
)
将关于 n 的 m-1 次多项式继续展开，最终得到
n
m
=(b
1
∑
x
1 , 1
=1
n
∑
x
1, 2
=1
x
1 , 1
...
∑
x
1 , m
=1
x
1, m−1
1+b
2
∑
x
2 , 1
=1
n
∑
x
2, 2
=1
x
2 , 1
...
∑
x
2 , m−1
=1
x
2 , m−2
1+...+b
m
∑
x
m ,1
n
1+b
m+1
)
注意要将这些系数存下来，给 m+1 次展开时使用
于是再乘上题目要求的系数，以此类推，将 1 到 k 次全部展开成一个系数数乘很多串
∑
，一次展开的复杂度为
O(i
2
)
,总体复杂度就是
O(k
3
)
以此展开的再讲所有展
开后长度相等的
∑
串的系数加起来。
原题的式子变成
评论0