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

前几天多校联合比赛中，有一道题目是：对于函数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的形式做即可。

当然我的将多项式化成下降幂的形式是一般方法。可惜时限卡的太紧了。