q1uple 数学讲课

CF1264D Beautiful Bracket Sequence

难点在于刻画答案。

你直接考虑枚举每个括号序列最中间的那个左右括号交界的位置算答案。

考虑枚举到一个位置 $ i $，现在 $ i $ 左边有 $ l $ 个左括号，右边有 $ r $ 个右括号，左边有 $ x $ 个问号，右边有 $ y $ 个问号，那么答案即为：

\[\sum\limits_{i=0}^x (l+i) \dbinom{x}{i} \dbinom{y}{l+i-r} \]

实际意义就是枚举这个贡献的长度是多少，然后直接组合数算方案。

把那个 $ (l+i) $ 拆成两个，然后分别用范德蒙德卷积即可。

CF932E Team Work

推式子题。

要你求 $ \sum\limits_{i=0}^n \dbinom{n}{i} i^x $

用到的重要东西就是第二类斯特林数的公式。

递推式：

\[\begin{Bmatrix} n \\m \end{Bmatrix} = \begin{Bmatrix} {n-1} \\{m-1} \end{Bmatrix} + m\begin{Bmatrix} {n-1} \\{m} \end{Bmatrix} \]

证明就是考虑其组合意义，将 $ n $ 个数划分成 $ m $ 个集合的方案数。现在要新加入一个数，那么就是要么这个数单开一个集合，要么这个数放在原来的集合中的任意一个。

第二类斯特林数重要公式：

\[m^n = \sum\limits_{i=0}^{m} \begin{Bmatrix} {n} \\{i} \end{Bmatrix} i! {\dbinom{m}{i}} \]

证明还是考虑组合意义，左边的组合意义显然为 $ n $ 个不相同的球放进 $ m $ 个不相同的盒子中的方案数。

第二类斯特林数在球与盒子上的定义是：$ n $ 个不相同的球放进 $ m $ 个相同的盒子中，且不能有盒子为空的方案数。

后面的意思就是考虑直接枚举有多少个非空的盒子，第二类斯特林数乘上阶乘变成不相同的盒子，组合数选用哪些盒子。

知道这个公式之后直接推式子：

\[\sum\limits_{i=0}^n \dbinom{n}{i} \sum\limits_{j=0}^{i} \begin{Bmatrix} {x} \\{j} \end{Bmatrix} j! \dbinom{i}{j} \]

然后进行一些常规操作之后化成：

\[\sum\limits_{i=0}^n \sum\limits_{j=0}^i \dfrac{n!}{(n-i)!(i-j)!} \begin{Bmatrix} {x} \\{j} \end{Bmatrix} \]

考虑一下这个接下来怎么化，你先交换求和符号把斯特林数丢到前面去：

\[\sum\limits_{j=0}^n \begin{Bmatrix} {x} \\{j} \end{Bmatrix} \sum\limits_{i=0}^n \dfrac{n!}{(n-i)!(i-j)!} \]

为了消掉后面这个东西，考虑直接用组合数的那个求和公式。

考虑给后面两个分式下面的东西构造成组合数，即：

\[\sum\limits_{j=0}^n \begin{Bmatrix} {x} \\{j} \end{Bmatrix} \dfrac{n!}{(n-j)!} \sum\limits_{i=0}^n \dbinom{n-i}{n-j} \]

然后后面这部分就可以直接化简为 $ 2^{n-j} $ 了。

做完了。

P4091 [HEOI2016/TJOI2016] 求和

重要的东西只有第二类斯特林数的通项公式：$ \begin{Bmatrix} n \ m \end{Bmatrix} m! = \sum\limits_{i=1}^{m} (-1)^{m-i} \dbinom{m}{i} i^n $。

题目就是直接把通项公式带进去，后面是 dirty work。

P10982 Connected Graph

这题我会！！！

首先考虑 $ n $ 个点不要求联通的无向图有多少个，为 $ 2^{\binom{n}{2}} $，理解为每条边都可以选或不选，记这个东西为 $ g(n) $。

然后考虑容斥，用总数减去不连通的图。

考虑枚举 1 所在的连通块的大小，这样可以算到不重不漏。

\[f(n) = g(n) - \sum\limits_{i=1}^{n-1} \binom{n-1}{i-1} f(i) g(n-i) \]

后面的意义就是，在剩下的点里面再选出 $ i-1 $ 个点，然后 $ f(i) $ 是这个联通块的方案，剩下的 $ n-i $ 个点无所谓，方案是 $ g(n-i) $。

P4841 [集训队作业2013] 城市规划

有一个很重要的东西是 $ \exp $ 的组合意义。

其组合意义为：将 $ n $ 个不同的元素划分为若干个非空的子集，大小为 $ i $ 的集合内有 $ f_i $ 种方案，记总方案数为 $ g_n $，则 $ f $ 和 $ g $ 的 $ EGF $ 满足 $ G(x) = \exp(F(x)) $。

看一下在这题上考虑，将求 $ n $ 个点的无向连通图，现在已知 $ g(n) = 2^{\binom{n}{2}} $ 表示 $ n $ 个点的无向图个数。

那么考虑一下非连通图事实上为数个连通图放在一起而成，即等价于把 $ n $ 个点划分成数个子集，这个和上面 $ \exp $ 的组合意义恰好是相同的。

那么即答案为 $ f(x) $，则根据 $ \exp $ 的组合意义就有：$ G(x) = e^{F(x)} $。

则 $ F(x) = \ln G(x) $。

你已知 $ G(x) $ 所以直接搞个多项式 $ \ln $

P5748 集合划分计数

你直接上 $ \exp $ 的组合意义。

令 $ f_i $ 表示集合大小为 $ i $ 集合内的方案数，当 $ i \ge 1 $ 时显然为 \(1\)，当 $ i=0 $ 时为 $ 0 $。

即 $ F(x) = e^x - 1 $

由 $ \exp $ 组合意义，$ G(x) = \exp(F(x)) = \exp(e^{x}-1) $。

直接多项式 $ \exp $ 即可。

P4389 付公主的背包

已严肃完成今日组合对象符号化大学习。

$ SEQ $ 构造：用 $ A $ 拼成的序列，形如 $ { A,AA,AAA,\cdots } $ 用 $ {01} $ 串来举例，其中 $ {011} $ 与 $ {101} $ 是两种不同的方案。

又写作：$ SEQ(A) = { (a_1,a_2,a_3,\cdots,a_m) | m \ge 0，a \in A } $

计算式：$ SEQ(A) = F(x) = \dfrac{1}{1-A(x)} $

$ MSET $ 构造：写作 $ MSET(A) = \prod\limits_{a \in A} \sum\limits_{k=0} {a}^k $，意义相当于是将 \(A\) 中的所有元素先取出来，然后再合并再一起，可以理解为完全背包。

$ MSET(A) = F(x) = \prod\limits_{i=1} a_i \sum\limits_{i | k} \dfrac{i x^k}{k} $

这题就是 $ MSET $ 构造，直接套上面的公式即可。

P5219 无聊的水题 I

EGF : 无标号，OGF : 有标号

由于是树上问题且和度数有关，所以考虑 $ prufer $ 序列。

题意转化为给你一个 $ n-2 $ 的序列，问你有多少种方案，使得出现次数最多的数出现次数为 $ m $。

考虑容斥，算最多出现次数 $ \le m $ 的减去最多出现次数 $ \le m-1 $ 的。

直接写出一个数的 EGF：$ F(x) = \sum\limits_{i=0}^{m-1} \dfrac{x^i}{i!} $。

然后一共有 $ n $ 个数，所以总答案为 $ F^n (x) $。直接多项式快速幂即可。