证明/推公式用的。

多项式的题目可以考虑。

Δ 0 f ( x ) = x Δ n f ( x ) = Δ n − 1 f ( x + 1 ) − Δ n − 1 f ( x ) \Delta^0f(x)=x\\ \Delta^nf(x)=\Delta^{n-1}f(x+1)-\Delta^{n-1}f(x) Δ0f(x)=xΔnf(x)=Δn−1f(x+1)−Δn−1f(x)

令 E f ( x ) = f ( x + 1 ) Ef(x)=f(x+1) Ef(x)=f(x+1)

则 Δ f ( x ) = E f ( x ) − f ( x ) = ( E − 1 ) f ( x ) \Delta f(x)=Ef(x)-f(x)=(E-1)f(x) Δf(x)=Ef(x)−f(x)=(E−1)f(x) 于是 Δ n f ( x ) = ( E − 1 ) n f ( x ) = ∑ k ≥ 0 ( n k ) ( − 1 ) n − k E k f ( x ) = ∑ k ≥ 0 ( n k ) ( − 1 ) n − k f ( x + k ) \Delta^nf(x)=(E-1)^nf(x)\\ =\sum_{k\ge 0}\binom{n}{k}(-1)^{n-k}E^kf(x)\\ =\sum_{k\ge 0}\binom{n}{k}(-1)^{n-k}f(x+k) Δnf(x)=(E−1)nf(x)=k≥0∑​(kn​)(−1)n−kEkf(x)=k≥0∑​(kn​)(−1)n−kf(x+k)

将多项式写成二项式系数和的形式 f ( x ) = ∑ k = 0 d C k ( x k ) f(x)=\sum_{k=0}^dC_k\binom{x}{k} f(x)=k=0∑d​Ck​(kx​) 其中 C k C_k Ck​为 C k = Δ k f ( 0 ) C_k=\Delta ^kf(0) Ck​=Δkf(0) 于是得到类似离散意义下的泰勒级数 f ( x ) = f ( x ) = ∑ k = 0 d Δ k f ( 0 ) ( x k ) f(x)=f(x)=\sum_{k=0}^d\Delta ^kf(0)\binom{x}{k} f(x)=f(x)=k=0∑d​Δkf(0)(kx​)

AtCoder 137 F

已知： f ( x ) f(x) f(x)在p个点的值： f ( i ) ≡ a i ( m o d p ) f(i) \equiv a_i \pmod p f(i)≡ai​(modp) ( 0 ≤ i ≤ p − 1 ) (0 \leq i \leq p-1) (0≤i≤p−1)

求： f ( x ) = b p − 1 x p − 1 + b p − 2 x p − 2 + … + b 0 f(x) = b_{p-1} x^{p-1} + b_{p-2} x^{p-2} + \ldots + b_0 f(x)=bp−1​xp−1+bp−2​xp−2+…+b0​的所有系数 b i b_i bi​

如果对某个等式 f i ≡ a i ( m o d p ) f_i \equiv a_i \pmod p fi​≡ai​(modp) 计算第 i i i阶差分，对所有的 j < i ， f ′ j i j>i j>i的 b j x j b_jx^j bj​xj这个差分只有 b i x i b_ix^i bi​xi的项。

我们可以证明 ∑ j = 0 i ( − 1 ) j C i j ( i − j ) i = i ! \sum_{j=0}^{i} (-1)^jC_i^j(i-j)^i=i! ∑j=0i​(−1)jCij​(i−j)i=i! ( ∵ ( i ! , p ) = 1 \because (i!, p)=1 ∵(i!,p)=1),于是只有一个解。