一个多项式的差分的等价形式---棋盘上放车的种数
前几天多校联合比赛中,有一道题目是:对于函数F(x)=(x
+ a1)(x + a2)*...*(x + an),求
ΔkF(0)
/ k!, 其中ΔkF(x)
表示函数F(x)的k阶差商在
x
处的值。
作者给出了一个巧妙的等价方式。将F(0)等价为在n列且第i列的格子数为ai+i-1的棋盘上放置n个车的方法数。这里默认a1
< a2< .. < an。
这样ΔF(0)也就有了组合意义。它相当于在棋盘上放置n-1个车的方法数。
由于ΔF(0)
= F(1) – F(0) , F(1)可以理解为在棋盘下面再加一行。
F(1)可以分为两种情况。最底下没有车:那么就是相当于F(0)
; 最底下一行有一个车
:
就是相当于原棋盘上放着n
- 1个车。所以得出ΔF(0)的组合意义。
同样的ΔkF(0)意义为在棋盘上放置n-k个车的方法数。
现在成功的将代数式
ΔkF(0)
/ k! 转化成组合问题即
---
在特定棋盘上放置n-k个车的方法数。这个采用dp的形式做即可。
当然我的将多项式化成下降幂的形式是一般方法。可惜时限卡的太紧了。
posted on 2010-07-18 21:32
wangzhihao 阅读(395)
评论(0) 编辑 收藏 引用 所属分类:
等价