「BZOJ 3028」食物-生成函数

链接

BZOJ 3028

题解

先写出每种食物的生成函数:

汉堡:$\sum\limits_{i = 0} ^ {\infty}x ^ {2i} = \frac {1} {1 - x ^ 2}$
可乐:$1 + x$
鸡腿:$1 + x + x ^ 2 = \frac {1 - x ^ 3} {1 - x}$
蜜桃多:$\sum\limits_{i = 1} ^ {\infty}x ^ {2i + 1} = \frac {x} {1 - x ^ 2}$
鸡块:$\sum\limits_{i = 1} ^ {\infty}x ^ {4i} = \frac {1} {1 - x ^ 4}$
包子:$1 + x + x ^ 2 + x ^ 3 = \frac {1 - x ^ 4} {1 - x}$
土豆炒肉片:$1 + x$
面包:$\sum\limits_{i = 1} ^ {\infty}x ^ {3i} = \frac {1} {1 - x ^ 3}$

将上式全部相乘,得
$$f(x) = \frac {x} {(1 - x) ^ 4} = x(1 - x) ^ {-4}$$

暴力展开法

根据麦克劳林展开,我们有
$$f(x)=\sum_{n = 0} ^ {\infty}f ^ {(n)} (0) \frac{x ^ n}{n!}$$
其中 $f ^ {(n)}$ 表示 $f$ 的 $n$ 阶导数,由于此题只需要知道 $x ^ n$ 的系数,那么我们只要求 $f ^ {(n)}$ 就行了。

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

根据莱布尼兹公式,有:
$$(u \cdot v) ^ {(n)} = \sum_{k = 0} ^ n \binom {k} {n} u ^ {(n)}v ^ {(n - k)}$$

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

由于基本函数 $(x ^ {\alpha}) ^ {(n)}$ 的 $n$ 阶导数为
$$\prod_{i = 1} ^ n(\alpha - i + 1)x ^ {\alpha - n}$$

所以当 $k > 1$ 时,$x ^ {(k)} = 0$,故
$$\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}$$

故 $x ^ n$ 的系数
$$\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) = x\sum_{k = 0} ^ {\infty}\binom {-4} {k}x ^ k$$

那么 $x ^ n$ 的系数为
$$\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;
}
分享到