学会 GF 能不能找到 GF
stripe_python
·
·
算法·理论
基础 GF 练习题,真的非常基础。
很多题可能都存在更为简单的组合意义做法,但是这里全都不写。
OGF
FPS24 A
你每天可以花费 1,3,4,6 元之一。求 k 天共花费 n 元的方案数。
:::::success[题解]
一天的 OGF 为 x+x^3+x^4+x^6,则答案为 [x^n](x+x^3+x^4+x^6)^k,于是
\begin{aligned}
[x^n](x+x^3+x^4+x^6)^k&= [x^n] \left(x^k (1+x^2)^k (1+x^3)^k\right)\\
&=[x^n] \left(x^k \sum_{i=0}^{k} \binom{k}{i} x^{2i} \sum_{j=0}^{k} \binom{k}{j} x^{3j}\right)\\
&=[x^n] \left(x^k\sum_{i=0}^{k} \sum_{j=0}^{k} \binom{k}{i} \binom{k}{j} x^{2i+3j}\right)\\
&= \sum_{i,j} \binom{k}{i} \binom{k}{j}
\end{aligned}
最后一个 \sum 的要求为 0 \le i \le k \land 0 \le j \le k \land 2i+3j=n-k。
FPS24 B
给出 n,求满足以下条件的整数四元组 (a,b,c,d) 的数目:
:::::success[题解]
四者的卷积为 \frac{1}{(1-x)^2},答案即为 x^n 项的系数。
| 注意到 \frac{1}{(1-x)^2}=\sum \limits_{n\ge 0}(n+1) x^n,证明考虑求导。于是答案为 n+1。 |
BZOJ3028
有 8 种不同颜色的无标号球,你总共需要选出 n 个。每种球的限制为:
- 偶数个;
-
-
- 奇数个;
-
-
- 不超过一个;
-
求选择的方案数。
::::::success[题解]
$$
F_1(x)=\sum_{i\ge 0}x^{2i}=\dfrac{1}{1-x^2}
$$
$$
F_2(x)=1+x
$$
$$
F_3(x)=1+x+x^2
$$
$$
F_4(x)=\sum_{i \ge 0}x^{2i+1}=\dfrac{x}{1-x^2}
$$
$$
F_5(x)=\sum_{i \ge 0}x^{4i}=\dfrac{1}{1-x^4}
$$
$$
F_6(x)=1+x+x^2+x^3
$$
$$
F_7(x)=1+x
$$
$$
F_8(x)=\sum_{i \ge 0}x^{3i}=\dfrac{1}{1-x^3}
$$
于是答案
$$
\begin{aligned}
F(x)&=\dfrac{x(1+x)^2(1+x+x^2)(1+x+x^2+x^3)}{(1-x^2)(1-x^3)(1-x^4)}\\
&=\dfrac{x}{(1-x)^4}\\
&=\sum_{n \ge 0} \binom{n+2}{n-1} x^i\\
[x^n] F(x)&=\binom{n+2}{3}
\end{aligned}
$$
::::::
### [FPS24 C](https://www.luogu.com.cn/problem/AT_fps_24_c)
求长度为 $n$,值域为 $\{0,1,2,\cdots,m\}$,总和为 $k$ 的序列数目。
:::::success[题解]
一个数的 OGF 为 $\sum \limits_{i=0}^m x^i=\frac{1-x^{m+1}}{1-x}$。将 $n$ 个数卷积得到序列的 OGF。于是答案为
$$
\begin{aligned}
[x^k] \left(\dfrac{1-x^{m+1}}{1-x} \right)^n &=[x^k] (1-x^{m+1})^n (1-x)^{-n}\\
&=[x^k] \left( \sum_{j=0}^n \binom{n}{j} (-1)^j x^{j(m+1)} \right) \left( \sum_{i=0}^\infty \binom{i+n-1}{n-1} x^i \right)\\
&= \sum _{i,j} (-1)^j \binom{n}{j} \binom{i+ n - 1}{n - 1}
\end{aligned}
$$
最后一个 $\sum$ 的要求为 $0 \le i \land 0 \le j \le n \land j(m+1)+i=k$。
[submission](https://atcoder.jp/contests/fps-24/submissions/75201146)。
:::::
### [FPS24 D](https://www.luogu.com.cn/problem/AT_fps_24_d)
求长度为 $n$,值域为 $\{0,1,2,\cdots,m\}$,排序后相邻元素奇偶性不同的序列数目。
:::::success[题解]
记原序列为 $a_i$,排序后序列为 $b_i$,显然只需对 $b_i$ 计数,答案乘 $n!$ 即可。
定义 $d_i=b_i-b_{i-1}$。特别地,令 $b_1=a_1, b_{n+1}=m-a_n$,则合法的 $d_i$ 满足以下条件:
- $\sum \limits_{i=1}^{n+1} d_i=m$;
- $\forall 1 \le i \le n+1, d_i \ge 0$;
- $d_1,d_{n+1} \in \{0,1,2,\cdots,m\}$;
- $\forall 2 \le i \le n, d_i$ 为奇数。
用 OGF 刻画:
- $d_1$ 和 $d_{n+1}$ 的 OGF 为 $\sum \limits_{i \ge 0} x^i=\frac{1}{1-x}$;
- $d_2 \sim d_n$ 的 OGF 为 $\sum \limits_{i \ge 1} x^{2i-1}=\frac{1}{1-x^2}$。
$n+1$ 个 OGF 的卷积取 $x^m$ 项系数为答案:
$$
\begin{aligned}
[x^m] \frac{1}{(1-x)^2} \times \frac{x^{n-1}}{(1-x^2)^{n-1}} &= [x^{m-n+1}] (1-x)^{-2}(1-x^2)^{1-n}\\
(1-x)^{-2} &= \sum_{i \ge 0}(i+1) x^i\\
(1-x^2)^{1-n} &= \sum_{j \ge 0}(-1)^{j} \binom{1-n}{j} x^{2j}\\
[x^{m-n+1}] (1-x)^{-2}(1-x^2)^{1-n} &= \sum_{i,j} (i+1) \binom{j+n-2}{n-2}
\end{aligned}
$$
最后一个 $\sum$ 的要求为 $0 \le i \land 0 \le j \land i+2j=m-n+1$。记得乘上 $n!$。
[submission](https://atcoder.jp/contests/fps-24/submissions/75207777)。
:::::
### [P11250](https://www.luogu.com.cn/problem/P11250)
有 $n$ 对手套,每只手套有标号,求从中取出 $m$ 只手套恰好包含 $k$ 对手套的方案数。
:::::success[题解]
二元 OGF 刻画之,用 $x$ 的幂表示取出的手套总数,$y$ 的幂表示配对成功的手套对数。
一对手套的 OGF 为 $1+2x+x^2y$。则答案为 $[x^m y^k] \left(1+2x+x^2y\right)^n$。于是
$$
\begin{aligned}
\left(1+2x+x^2y\right)^n&=\sum_{i=0}^n \binom{n}{i} (1+2x)^{n-i} (x^2y)^i\\
[y^k] \left(1+2x+x^2y\right)^n &=\binom{n}{k} (1+2x)^{n-k} x^{2k}\\
[y^k] \left(1+2x+x^2y\right)^n &=\binom{n}{k} x^{2k} \sum_{j=0}^{n-k} \binom{n-k}{j} 2^j x^j\\
[x^{m-2k}] (1+2x)^{n-k}&=\binom{n-k}{m-2k} 2^{m-2k}\\
[x^m y^k] \left(1+2x+x^2y\right)^n &= \binom{n}{k} \binom{n-k}{m-2k} 2^{m-2k}
\end{aligned}
$$
:::::
### [FPS24 H](https://www.luogu.com.cn/problem/AT_fps_24_h)
现有一个 $n \times m$ 的网格,你要从 $(0,0)$ 走到 $(n,m)$,每一步可以向下移动 $0$ 或 $1$ 个单位,向右移动任意个单位,不能不动。求操作序列的数目。
:::::success[题解]
考虑二元 OGF,用 $x,y$ 的指数刻画位置。则一次操作的 OGF 为 $(1+x) \sum \limits_{n \ge 0} y^n-1=\frac{x+y}{1-y}$。
枚举步数 $k$ 得到答案的 OGF,此时 $x^n y^m$ 项系数即为所求:
$$
\begin{aligned}
[x^n y^m] \sum _{k \ge 0} \left(\frac{x+y}{1-y}\right)^k &= [x^n y^m] \frac{1-y}{1-x-2y} \\
(1-x-2y)^{-1} &= \sum_{i,j \ge 0} \binom{i+j}{i} x^i (2y)^j\\
\frac{1-y}{1-x-2y} &= \sum_{i,j \ge 0} \binom{i+j}{i} 2^j x^i y^j-\sum_{i,j \ge 1} \binom{i+j-1}{i} 2^{j-1} x^i y^{j}\\
[x^n y^m] \frac{1-y}{1-x-2y} &= \binom{n+m}{m} 2^m - \binom{n+m-1}{m-1} 2^{m-1}
\end{aligned}
$$
:::::
### [P3223](https://www.luogu.com.cn/problem/P3223)
有 $n$ 个黑球,$m$ 个白球和两个红球排成一列,并且任意白球不相邻,红球也不能相邻,球均有标号,求方案数。
:::::success[题解]
忽略球的标号,最后将答案乘上 $n!m!2!$ 即可。
三元 OGF 刻画,用 $x,y,z$ 表示黑球 / 白球 / 红球,并且设 $F,G,H$ 分别表示以黑球 / 白球 / 红球结尾的 OGF,$T$ 为答案 OGF,于是
$$
T=1+F+G+H
$$
考虑追加三种颜色的球
$$
\begin{aligned}
F&=x(1+F+G+H)=xT \\
G&=y(1+F+H)=y(T-G) \implies G=\frac{y}{1+y}T\\
H&=z(1+F+G)=z(T-H) \implies H=\frac{z}{1+z} T
\end{aligned}
$$
将三式代入解出 $T
\begin{aligned}
T&=1+xT+\frac{y}{1+y}T+\frac{z}{1+z} T\\
T &= \left(1-x-\frac{y}{1+y}-\frac{z}{1+z}\right)^{-1}\\
T &= \sum_{k \ge 0} \frac{z^k}{(1-x-\frac{y}{1+y} )^{k+1} (1+z)^k}\\
[z^2] T &= \left(1-x-\frac{y}{1+y} \right)^{-3} -\left(1-x-\frac{y}{1+y} \right)^{-2}\\
[x^n y^m z^2] T &= \binom{n+2}{2}\binom{n+3}{m}-(n+1) \binom{n+2}{m}
\end{aligned}
EGF
FPS24 E
求长为 n,值域为 \{1,2,\cdots,m\} 且数字 i 至多出现 i 次的序列数目。
:::::success[题解]
单个数字的 EGF 为 \sum \limits_{j=0}^i \frac{x^j}{j!},答案即所有 EGF 卷积的 x^n 项系数
\left[\frac{x^n}{n!}\right] \prod_{i=1}^m \sum \limits_{j=0}^i \frac{x^j}{j!}
| 暴力多项式卷积,复杂度 O(n^2 m) 可以通过。submission。 |
FPS24 F
有 n 个有标号球,你需要将其染上红蓝黄三色,使得染蓝色的球数为偶数,染黄色的球数为奇数,求方案数。
:::::success[题解]
写出三种颜色的 EGF:
- 红色:\sum\limits_{n\ge 0} \frac{x^n}{n!}=e^x;
- 蓝色:\sum\limits_{n \ge 0} \frac{x^{2n}}{(2n)!}=\frac{e^x+e^{-x}}{2}(即 \sinh x);
- 黄色:\sum \limits_{n\ge 1} \frac{x^{2n-1}}{(2n-1)!}=\frac{e^x-e^{-x}}{2}(即 \cosh x)。
三者卷积的 x^n 项即为答案。
\begin{aligned}
\left[\frac{x^n}{n!}\right] \frac{e^x(e^x+e^{-x})(e^x-e^{-x})}{4} &= \left[\frac{x^n}{n!}\right] \frac{e^{3x}-e^{-x}}{4} \\
&=\frac{3^n-(-1)^n}{4}
\end{aligned}
:::::
PGF
QOJ1426
你需要依次完成 n 个任务,每完成一个任务有 p_i 的概率获得 i 点得分,其中 0 \le i \le k。得分上限为 m,求最终得分的期望。
:::::success[题解]
列出一个任务的 PGF 为 P(x)=\sum \limits_{i=0}^k p_i x^i,则 n 次任务的 PGF 即 F=P^n。答案为
\sum _{i \ge 0} \min(i,m) \times f_i
$$
\begin{aligned}
F(x)&=P^n(x)\\
F'(x)&=nP'(x)P^{n-1}(x)\\
F'(x)P(x)&=nF(x)P'(x)\\
[x^j] F'(x)P(x)&=[x^j]nF(x)P'(x) \\
\sum_{i=0}^k (j-i+1)\times p_i \times f_{j-i+1}&=n\sum_{i=1}^k i\times p_i\times f_{j-i+1}
\end{aligned}
$$
可以在 $O(mk)$ 的时间内求解系数。
:::::
## 哈集幂
### [P3214](https://www.luogu.com.cn/problem/P3214)
你需要选出 $\{1,2,\cdots,n\}$ 的 $m$ 个非空不同子集,使得这些集合的对称差为空,求方案数。