「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}$$

代码

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