一個多項式的差分的等價形式---棋盤上放車的種數

前幾天多校聯合比賽中，有一道題目是：對于函數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的形式做即可。

當然我的將多項式化成下降冪的形式是一般方法。可惜時限卡的太緊了。