随笔-21  评论-10  文章-21  trackbacks-0

一个多项式的差分的等价形式---棋盘上放车的种数

前几天多校联合比赛中,有一道题目是:对于函数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 阅读(352) 评论(0)  编辑 收藏 引用 所属分类: 等价

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理