方法一
• 根据二项式定理可知：
(ax+by)
k
=
=
• 取i=n,x
n
y
m
的系数为
• 其中a
n
和b
m
可以用快速幂来计算，在lg(n)+lg(m)内完成。
• 计算 可以用递推来求解。
• 状态：f[i,j]表示从i个数中选j个数的方案数。f[k,n]就是答案。
• 根据第i数选还是不选来进行分析：
1.选择第i个数：此情况的方案数等价于从i-1个数中选择j-1个
数的方案数即f[i-1,j-1];
2.不选第i个数：此情况的方案数等价于从i-1个数中选择j个数
的方案数即f[i-1,j]
所以f[i,j]=f[i-1,j-1]+f[i-1,j]
• 边界条件：f[i,0]=1,f[i,i]=1。 时间复杂度为O(n*k)。
评论0
最新资源