一個(gè)多項(xiàng)式的差分的等價(jià)形式---棋盤(pán)上放車(chē)的種數(shù)

前幾天多校聯(lián)合比賽中，有一道題目是：對(duì)于函數(shù)F(x)=(x + a1)(x + a2)*...*(x + an)，求

ΔkF(0) / k!, 其中ΔkF(x) 表示函數(shù)F(x)的k階差商在 x 處的值。

作者給出了一個(gè)巧妙的等價(jià)方式。將F(0)等價(jià)為在n列且第i列的格子數(shù)為ai+i-1的棋盤(pán)上放置n個(gè)車(chē)的方法數(shù)。這里默認(rèn)a1 < a2< .. < an。

這樣ΔF(0)也就有了組合意義。它相當(dāng)于在棋盤(pán)上放置n-1個(gè)車(chē)的方法數(shù)。

由于ΔF(0) = F(1) – F(0) , F(1)可以理解為在棋盤(pán)下面再加一行。 F(1)可以分為兩種情況。最底下沒(méi)有車(chē)：那么就是相當(dāng)于F(0) ; 最底下一行有一個(gè)車(chē) : 就是相當(dāng)于原棋盤(pán)上放著n - 1個(gè)車(chē)。所以得出ΔF(0)的組合意義。

同樣的ΔkF(0)意義為在棋盤(pán)上放置n-k個(gè)車(chē)的方法數(shù)。

現(xiàn)在成功的將代數(shù)式 ΔkF(0) / k! 轉(zhuǎn)化成組合問(wèn)題即 --- 在特定棋盤(pán)上放置n-k個(gè)車(chē)的方法數(shù)。這個(gè)采用dp的形式做即可。

當(dāng)然我的將多項(xiàng)式化成下降冪的形式是一般方法。可惜時(shí)限卡的太緊了。