「BZOJ 3028」食物-生成函数

链接

BZOJ 3028

题解

先写出每种食物的生成函数:
汉堡:i=0x2i=11x2\sum\limits_{i = 0} ^ {\infty}x ^ {2i} = \frac {1} {1 - x ^ 2}
可乐:1+x1 + x
鸡腿:1+x+x2=1x31x1 + x + x ^ 2 = \frac {1 - x ^ 3} {1 - x}
蜜桃多:i=1x2i+1=x1x2\sum\limits_{i = 1} ^ {\infty}x ^ {2i + 1} = \frac {x} {1 - x ^ 2}
鸡块:i=1x4i=11x4\sum\limits_{i = 1} ^ {\infty}x ^ {4i} = \frac {1} {1 - x ^ 4}
包子:1+x+x2+x3=1x41x1 + x + x ^ 2 + x ^ 3 = \frac {1 - x ^ 4} {1 - x}
土豆炒肉片:1+x1 + x
面包:i=1x3i=11x3\sum\limits_{i = 1} ^ {\infty}x ^ {3i} = \frac {1} {1 - x ^ 3}

将上式全部相乘,得

f(x)=x(1x)4=x(1x)4f(x) = \frac {x} {(1 - x) ^ 4} = x(1 - x) ^ {-4}

暴力展开法

根据麦克劳林展开,我们有

f(x)=n=0f(n)(0)xnn!f(x)=\sum_{n = 0} ^ {\infty}f ^ {(n)} (0) \frac{x ^ n}{n!}

其中 f(n)f ^ {(n)} 表示 ffnn 阶导数,由于此题只需要知道 xnx ^ n 的系数,那么我们只要求 f(n)f ^ {(n)} 就行了。

f(n)(x)=[x(1x)4](n)f ^ {(n)}(x) = [x(1 - x) ^ {-4}] ^ {(n)}

根据莱布尼兹公式,有:

(uv)(n)=k=0n(kn)u(n)v(nk)(u \cdot v) ^ {(n)} = \sum_{k = 0} ^ n \binom {k} {n} u ^ {(n)}v ^ {(n - k)}

那么

f(n)(x)=k=0n(nk)x(k)[(1x)4](nk)f ^ {(n)}(x) = \sum_{k = 0} ^ n \binom {n} {k} x ^ {(k)} [(1 - x) ^ {-4}] ^ {(n - k)}

由于基本函数 (xα)(n)(x ^ {\alpha}) ^ {(n)}nn 阶导数为

i=1n(αi+1)xαn\prod_{i = 1} ^ n(\alpha - i + 1)x ^ {\alpha - n}

所以当 k>1k > 1 时,x(k)=0x ^ {(k)} = 0,故

f(n)=(n0)x(0)[(1x)4](n)+(n1)x(1)[(1x)4](n1)=x[(1x)4](n)+n[(1x)4](n1)=xi=1n(4i+1)(1x)4n+ni=1n1(4i+1)(1x)4n+1=xi=4n3i(1x)4n+ni=4n2i(1x)3n=(n+3)!3!x(1x)4n+n(n+2)!3!(1x)3n\begin{aligned}f ^ {(n)} &= \binom {n} {0} x ^ {(0)}[(1 - x) ^ {-4}] ^ {(n)} + \binom {n} {1} x ^ {(1)} [(1 - x) ^ {-4}] ^ {(n - 1)} \\ &= x[(1 - x) ^ {-4}] ^ {(n)} + n[(1 - x) ^ {-4}] ^ {(n - 1)} \\ &= x \prod_{i = 1} ^ n(-4 - i + 1)(1 - x) ^ {-4 - n} + n \prod_{i = 1} ^ {n - 1}(-4 - i + 1)(1 - x) ^ {-4 - n + 1} \\ &= x \prod_{i = -4} ^ {-n - 3}i(1 - x) ^ {-4 - n} + n \prod_{i = -4} ^ {-n - 2}i (1 - x) ^ {-3 - n} \\ &= \frac {(n + 3)!} {3!}x(1 - x) ^ {-4 - n} + \frac {n(n + 2)!}{3!}(1 - x) ^ {-3 - n} \end{aligned}

xnx ^ n 的系数

f(n)(0)n!=n(n+2)!3!n!(1)3n=n(n+1)(n+2)6\begin{aligned}\frac {f ^ {(n)}(0)} {n!} &= \frac {n(n + 2)!} {3!n!}(-1) ^ {-3 - n} \\ &= \frac {n(n + 1)(n + 2)} {6} \end{aligned}

广义二项式定理

f(x)f(x) 的右半部分用广义二项式定理展开,可得

f(x)=xk=0(4k)xkf(x) = x\sum_{k = 0} ^ {\infty}\binom {-4} {k}x ^ k

那么 xnx ^ n 的系数为

(4n1)=i=44n+2i(n1)!=(n+2)!(n1)!3!=n(n+1)(n+2)6\begin{aligned}\binom {-4} {n - 1} &= \frac {\prod\limits_{i = -4} ^ {- 4 - n + 2}i} {(n - 1)!} \\ &= \frac {(n + 2)!} {(n - 1)!3!} \\ &= \frac {n(n + 1)(n + 2)} {6} \end{aligned}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 3028」食物 29-07-2017
* 生成函数
* @author xehoth
*/
#include <bits/stdc++.h>
const int MOD = 10007;
const int INV_SIX = 1668;
const int MAXN = 1000;
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
register int n = 0;
static char s[MAXN];
std::cin >> s;
for (register char *c = s; *c; c++) n = (n * 10 + (*c ^ '0')) % MOD;
std::cout << n * (n + 1ll) * (n + 2ll) * INV_SIX % MOD;
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 题解
    1. 2.1. 暴力展开法
    2. 2.2. 广义二项式定理
  3. 3. 代码