「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$，故

故 $x ^ n$ 的系数

广义二项式定理

对 $f(x)$ 的右半部分用广义二项式定理展开，可得
$$f(x) = x\sum_{k = 0} ^ {\infty}\binom {-4} {k}x ^ k$$

那么 $x ^ n$ 的系数为

代码

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;
}