Atcoder FPS 24

A - Snack

题意

有 $d$ 天，每天可以选择花费 $1/3/4/6$ 元购买四种不同的零食，求 $d$ 天总共恰好花费 $n$ 元的购买方案数。

两个购买方案不同当且仅当存在一天购买的零食不同.

$d\le 2\times 10^5, n\le 10^6$ 。

解法

定义：

普通生成函数（OGF）：一个序列 $\left\langle a_n\right\rangle$ 的 OGF 是一个形式幂级数（可以看作无限长的多项式） $A(x) = \sum_{i=0}^{\infty} a_i x^i$ ，其中 $a_i$ 是数列的第 $i$ 项。

通过类比一般多项式的乘法，可以得到 OGF 的加法和乘法。

设 $a,b$ 的 OGF 分别是 $F(x), G(x)$ ，则：

OGF 的加法： $F(x) + G(x)$ 对应的数列是 $\left\langle a_n + b_n \right\rangle$ 。
OGF 的乘法： $F(x) G(x)$ 对应的数列是 $\langle \sum_{i=0}^n a_i b_{n-i} \rangle$ 。

在形式幂级数中，我们不关心 $x$ 的具体取值，只关心系数的含义，就相当于把系数挂在了一个多项式上，再用这个多项式去进行进一步的各种计算。

而多项式的乘法就是一种卷积，当我们要找 $x^2$ 的系数时，就是找 $x^0$ 和 $x^2$ 的系数相乘加上 $x^1$ 和 $x^1$ 的系数相乘再加上 $x^2$ 和 $x^0$ 的系数相乘。这正好对应了把总数为 $2$ 的物品分成两部分去计数的过程。所以，我们要把花费放在指数上，而方案放在系数上，这样就可以通过多项式乘法来进行计数。

举例：
有 $3$ 块红色的地砖和 $2$ 块蓝色的地砖，求选出 $4$ 块地砖的方案数（两个方案不同当且仅当选出的红砖个数不同或选出的蓝砖数量不同）。

手动枚举一下，可能的方案只有 $(3,1),(2,2)$ ，所以答案是 $2$ 。

用 OGF 解决这个问题，写出红色地砖的 OGF： $R(x) = 1 + x + x^2 + x^3$ ，表示选 $0/1/2/3$ 块红色地砖的方案数分别是 $1/1/1/1$ 。蓝色地砖的 OGF 是 $B(x) = 1 + x + x^2$ 。所以最后的答案就是 $[x^4]R(x)B(x)$ ，其中 $[x^n]F(x)$ 表示形式幂级数 $F(x)$ 中 $x^n$ 的系数。相乘，结果为 $R(x)B(x) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5$ ，所以答案是 $2$ 。

可以发现，我们顺带求出了需要选出任意块地砖的各自方案数。

回到本题，我们的序列第 $i$ 个元素表示花费 $i$ 元的购买方案数。则每一天的 OGF 就是 $x+x^3+x^4+x^6$ ，因为每一天可以选择花费 $1/3/4/6$ 元购买零食。

所以总花费就是第一天花费加第二天花费加 $\ldots$ 加第 $d$ 天花费，对应的 OGF 就是 $(x+x^3+x^4+x^6)^d$ 。因为每一天的选择规则都一样，且第一天的选择和第二天的选择是独立的，根据乘法原理，总方案数的 OGF 就是 $d$ 个每天的 OGF 相乘。

那么，答案就是 $[x^n](x+x^3+x^4+x^6)^d$ 。

后面稍微进行一些代数变形即可解决本题：

$\begin{aligned} [x^n](x+x^3+x^4+x^6)^d &= [x^{n-d}](1+x^2+x^3+x^5)^d \\ &= [x^{n-d}](1+x^2)^d(1+x^3)^d\\ \end{aligned}$

我们只需要枚举左边的项每一次的系数，就知道右边项对应的系数，通过二项式定理计算就可以解决本题。

答案即为

$\sum_{i,j\in \mathbb N, 2i+3j = n-d} \binom{d}{i} \binom{d}{j}$

复杂度 $O(d)$ 。

参考代码。

B - Tuple of Integers

题意

给定 $n$ ，求满足条件的非负整数四元组 $(a,b,c,d)$ 个数：

$a+b+c+d = n$ ；
$a\in \{0, 1\}$ ；
$b\in \{0, 1, 2\}$ ；
$c$ 是偶数；
$d$ 是 3 的倍数。

$0\le n\le 10^9$ 。

解法

一样的，写出每一个数的 OGF：
$A(x) = 1 + x$ ， $B(x) = 1 + x + x^2$ ， $C(x) = 1 + x^2 + x^4 + \ldots$ ， $D(x) = 1 + x^3 + x^6 + \ldots$ 。

高中等比数列求和有如下公式：

$\sum_{i=0}^{\infty} a_1 q^i = \dfrac{a_1}{1-q} \quad (|q|<1)$

现在 $C(x)$ 和 $D(x)$ 是无穷级数，我们类比等比数列求和可以把它们写成封闭形式。

$\begin{aligned} C(x) = \sum_{i=0}^{\infty} x^{2i} &= \dfrac{1}{1-x^2}\\ D(x) = \sum_{i=0}^{\infty} x^{3i} &= \dfrac{1}{1-x^3} \end{aligned}$

在对形式幂级数进行运算时，我们不关心级数的敛散性，只关心每一项系数，所以可以直接使用这个公式， $\dfrac{1}{1-x^2}$ 虽然看上去不像一个幂级数，但是它在形式幂级数的意义下，就是 $\sum_{i=0}^{\infty} x^{2i}$ 。在运算时，使用分式会更加方便，我们也把这种形式叫做原来幂级数的封闭形式。

所以答案就是

$\begin{aligned} [x^n]A(x)B(x)C(x)D(x) &= [x^n]\dfrac{(1+x)(1+x+x^2)}{(1-x^2)(1-x^3)}\\ &= [x^n]\dfrac{1}{(1-x)^2} \end{aligned}$

接下来我们介绍如何求 $[x^n]\dfrac{1}{(1-x)^k}$ 。一个简单的方法是使用牛顿二项式定理（或泰勒展开），但是我们在此给出一种组合意义证明。

$\dfrac{1}{(1-x)^k} = \left(\sum_{n=0}^{\infty} x^n\right)^k$ ，我们考察 $x^n$ 的系数如何来的，就是要在每个括号中选择一个次数，使得总和为 $n$ 。这就相当于把 $n$ 个相同的球放入 $k$ 个不同的盒子中，允许某些盒子为空。根据插板法，答案就是 $\dbinom{n+k-1}{k-1}$ 。

回到原题，答案就是 $\dbinom{n+2-1}{2-1} = n+1$ 。

参考代码

C - Sequence

题意

求满足条件的长度为 $n$ 的序列个数：

每个元素是不大于 $m$ 的非负整数；
总和为 $s$ 。

$n,m,s\le 2\times 10^5$ 。

解法

答案是 $[x^s](1+x+\ldots+x^m)^n$ 。

进行代数变形：

$\begin{aligned} [x^s](1+x+\ldots+x^m)^n = [x^s]\left(\dfrac{1-x^{m+1}}{1-x}\right)^n = [x^s](1-x^{m+1})^n(1-x)^{-n}. \end{aligned}$

之后只需要枚举两边系数即可，左右的系数我们都已经会处理了，答案就是

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} \binom{s -k(m+1) + n - 1}{n - 1}.$

参考代码

D - Sequence 2

题意

求满足条件的长度为 $n$ 的序列个数：

每个元素是不大于 $m$ 的非负整数；
所有元素按从大到小排序之后，相邻的数奇偶性不同。

$n,m\le 2\times 10^5$ 。

解法

对原数组 $\left\langle a\right\rangle$ 排完序之后得到 $\left\langle b\right\rangle$ ，考虑 $\left\langle b\right\rangle$ 的差分序列 $\left\langle d\right\rangle$ ：

$d_i = \begin{cases} b_1, & i = 1\\ b_i - b_{i-1} & i > 1 \end{cases}$

因为每个数都不同，只需要计算差分序列的个数，再乘以 $n!$ 即可。

差分序列的条件如下：

$d_1$ 是非负整数；
$d_2, d_3, \ldots d_n$ 是正奇数；
$d_1 + d_2 + \ldots + d_n \le m$ 。

因此，这样的差分序列个数就是

$\sum_{i=0}^m [x^i] \dfrac{1}{1-x} \left(\dfrac{x}{1-x^2}\right)^{n-1} = [x^{m-n+1}] \dfrac{1}{(1-x)^{n+1}(1+x)^{n-1}}.$

（此处用到了如下性质： $\sum_{i=0}^m [x^i]F(x) = [x^m]\dfrac{F(x)}{1-x}$ ，可以把 $\dfrac{1}{1-x}$ 看作一个前缀和算子）

参考代码

E - Sequence 3

题意

求满足条件的长度为 $n$ 的序列个数：

每个元素是不大于 $m$ 的正整数；
$i$ 最多出现了 $i$ 次。

$n,m \le 300$ 。

解法

为解决本题，我们要介绍一种新的生成函数——指数生成函数（EGF）。

定义：
指数生成函数（EGF）：一个序列 $\left\langle a_n\right\rangle$ 的 EGF 是一个形式幂级数 $A(x) = \displaystyle\sum_{i=0}^{\infty} a_i \dfrac{x^i}{i!}$ ，其中 $a_i$ 是数列的第 $i$ 项。

可以得到 EGF 的加法和乘法的运算法则。
设 $a,b$ 的 EGF 分别是 $F(x), G(x)$ ，则：

EGF 的加法： $F(x) + G(x)$ 对应的数列是 $\left\langle a_n + b_n \right\rangle$ 。
EGF 的乘法： $F(x) G(x)$ 对应的数列是 $\left\langle \sum_{i=0}^n \dbinom{n}{i} a_i b_{n-i} \right\rangle$ 。