【BZOJ】3028: 食物-生成函數&萊布尼茨公式

傳送門：bzoj3028

題解

Step 1

構造生成函數：

A ( x ) = 1 1 − x 2 A(x)=\dfrac 1{1-x^2} A(x)=1−x21​

B ( x ) = 1 + x B(x)=1+x B(x)=1+x

C ( x ) = 1 + x + x 2 C(x)=1+x+x^2 C(x)=1+x+x2

D ( x ) = x 1 − x 2 D(x)=\dfrac {x}{1-x^2} D(x)=1−x2x​

E ( x ) = 1 1 − x 4 E(x)=\dfrac{1}{1-x^4} E(x)=1−x41​

F ( x ) = 1 + x + x 2 + x 3 F(x)=1+x+x^2+x^3 F(x)=1+x+x2+x3

G ( x ) = 1 + x G(x)=1+x G(x)=1+x

H ( x ) = 1 1 − x 3 H(x)=\dfrac 1{1-x^3} H(x)=1−x31​

全部卷積起來就是： x ( 1 − x ) 4 \dfrac{x}{(1-x)^4} (1−x)4x​

Step 2

f ( x ) = x ( 1 − x ) 4 f(x)=\dfrac{x}{(1-x)^4} f(x)=(1−x)4x​

花式求解 [ x n ] [x^n] [xn]：

泰勒展開

[ x n ] = f ( n ) ( 0 ) n ! [x^n]=\dfrac{f^{(n)}(0)}{n!} [xn]=n!f(n)(0)​

引入萊布尼茨公式：

( f ∗ g ) ( n ) = ∑ i = 0 n ( n i ) f ( i ) g ( n − i ) (f *g)^{(n)}=\sum\limits_{i=0}^n\binom{n}{i}f^{(i)}g^{(n-i)} (f∗g)(n)=i=0∑n​(in​)f(i)g(n−i)

證明略。

f ( x ) = x , g ( x ) = ( 1 − x ) − 4 f(x)=x,g(x)=(1-x)^{-4} f(x)=x,g(x)=(1−x)−4

由于 f i = 0 ( i ≠ 1 ) f^i=0(i\neq 1) fi=0(i̸​=1)，是以隻需要求 g ( n − 1 ) ( 0 ) g^{(n-1)}(0) g(n−1)(0)即 ( n + 2 ) ! 6 \dfrac{(n+2)!}{6} 6(n+2)!​

a n s = n ( n + 2 ) ! n ! 6 = n ( n + 1 ) ( n + 2 ) 6 ans=n\dfrac{(n+2)!}{n!6}=\dfrac{n(n+1)(n+2)}{6} ans=nn!6(n+2)!​=6n(n+1)(n+2)​

廣義二項式定理

( x + y ) a = ∑ i = 0 ∞ ( a i ) x i y a − i (x+y)^a=\sum\limits_{i=0}^{\infty}\binom{a}{i}x^i y^{a-i} (x+y)a=i=0∑∞​(ia​)xiya−i

其中 a &lt; 0 a&lt;0 a<0設 ( a i ) = ∏ k = 0 i − 1 ( a − k ) i ! \binom{a}{i}=\dfrac{\prod\limits_{k=0}^{i-1}(a-k)}{i!} (ia​)=i!k=0∏i−1​(a−k)​

廣義二項式展開 ( 1 − x ) − 4 = ∑ i = 0 ∞ ( − 4 i ) ( − x ) i (1-x)^{-4}=\sum\limits_{i=0}^{\infty}\binom{-4}{i}(-x)^i (1−x)−4=i=0∑∞​(i−4​)(−x)i

[ x n ] = ( − 1 ) n − 1 ( − 4 n − 1 ) = ∏ i = 0 n − 2 ( 4 + i ) ( n − 1 ) ! = n ( n + 1 ) ( n + 2 ) 6 [x^n]=(-1)^{n-1}\binom{-4}{n-1}=\dfrac{\prod\limits_{i=0}^{n-2}(4+i)}{(n-1)!}=\dfrac{n(n+1)(n+2)}{6} [xn]=(−1)n−1(n−1−4​)=(n−1)!i=0∏n−2​(4+i)​=6n(n+1)(n+2)​

組合意義

1 1 − x = ∑ i = 0 ∞ x i \dfrac{1}{1-x}=\sum\limits_{i=0}^{\infty}x^i 1−x1​=i=0∑∞​xi

表示選任意個的生成函數。

1 ( 1 − x ) 4 \dfrac{1}{(1-x)^4} (1−x)41​即為選四個自然數和為特定值的方案數。

插闆法 ( n − 1 + 3 3 ) = n ( n + 1 ) ( n + 2 ) 6 \dbinom{n-1+3}{3}=\dfrac{n(n+1)(n+2)}{6} (3n−1+3​)=6n(n+1)(n+2)​