当前位置：首页 > news >正文

离散与组合数学杂记

news 2025/7/18 5:45:23

生成函数

概念

又称母函数把一个无穷数列 ${a_n\}$ （默认从 $0$ 项起）表示成 $G(x)=∑i≥0aixiG(x)=\displaystyle\sum_{i\ge0} a_ix^i$ 的函数形式。例如：

$a_i=2^i$ ： $G(x)=∑i≥02ixiG(x)=\displaystyle\sum_{i\ge 0} 2^i x^i$ ；
$a_i=1$ ： $G(x)=∑i≥0xiG(x)=\displaystyle\sum _{i\ge 0} x^i$ 。

应用

用来帮助推导数列的通项公式（比如斐波那契数列）也可以作为条件形式以数列形式给出的象征。一个特别的转化：逆运用等比数列求和公式，可以得到： $11−ax=∑i≥0aixi\displaystyle\dfrac{1}{1-ax}=\sum_{i\ge0}a^ix^i$ ，等号左边不带求和符号部分的，称为生成函数的封闭形式。

生成函数的乘法运算有意义，其卷积形式是函数直接相乘。对于 $A(x)=∑i≥0aixiA(x)=\displaystyle\sum_{i\ge0}a_ix^i$ 和 $A(x)=∑i≥0bixiA(x)=\displaystyle\sum_{i\ge0}b_ix^i$ ：
$A×B=∑i≥0n(xi∑j=0iajbi−j)A\times B=\sum_{i\ge0}^n\left(x^i\sum_{j=0}^ia_jb_{i-j}\right)$

洛谷 P10780 BZOJ3028 食物

题意

题目传送门。

思路

根据上文，将这个背包问题转化为，考虑每一种物品拿的个数的生成函数，并用封闭形式表示：

偶数个形如 ${1,0,1,0,1,......\}$ ： $∑k≥0x2k=11−x2\displaystyle\sum_{k\ge 0} x^{2k}=\frac{1}{1-x^2}$ ；
$0$ 或 $1$ 个形如 ${1,1,0,0,0,......\}$ ： $1 + x$ ；
$0$ 或 $1$ 或 $2$ 个形如 ${1,1,1,0,0,......\}$ ： $1+x+x^2$ ；
奇数个形如 ${0,1,0,1,0,......\}$ ： $∑k≥0x2k+1=x∑k≥0x2k=x1−x2\displaystyle\sum_{k\ge 0}x^{2k+1}=x\displaystyle\sum_{k\ge 0} x^{2k}=\frac{x}{1-x^2}$ ；
$4$ 的倍数个类似第一条： $∑k≥0x4k=11−x4\displaystyle\sum_{k\ge 0}x^{4k}=\frac{1}{1-x^4}$ ；
$0$ 或 $1$ 或 $2$ 或 $3$ 个形如 ${1,1,1,0,0,......\}$ ： $1+x+x^2+x^3$ ；
$3$ 的倍数个类似第一条： $∑k≥0x3k=11−x3\displaystyle\sum_{k\ge 0}x^{3k}=\frac{1}{1-x^3}$ .

全部乘起来，并用二项式定理化简 $1+x+x^2$ 和 $1+x+x^2+x^3$ ：
$x(1−x)4\frac{x}{(1-x)^4}$

考虑推 $1(1−x)k=(11−x)k\dfrac{1}{(1-x)^k}=\left(\dfrac{1}{1-x}\right)^k$ 是哪个生成函数的封闭形式与该生成函数的第 $n$ 项系数，因为 $11−ax=∑i≥0aixi\displaystyle\dfrac{1}{1-ax}=\sum_{i\ge0}a^ix^i$ ， $a = 1$ 时， $11−x=1+x+x2+x3+...\dfrac{1}{1-x}=1+x+x^2+x^3+...$ 。 $k$ 次方展开后，相当于选 $k$ 个自然数和为 $n$ 的方案数：先给 $k$ 个数加 $1$ 转化问题为 $k$ 个正整数和为 $n + k$ ，运用插板法得知方案数为 $(n+k−1k−1)\dbinom{n+k-1}{k-1}$ 。

回到这一题 $1(1−x)4\frac{1}{(1-x)^4}$ 的第 $n - 1$ 项系数为 $(n−23)\dbinom{n-2}{3}$ ，乘回 $x$ 后即为答案。代码略。

Polya 计数

等我完全理解完再回来补。先给结论：用 $k$ 中颜色给 $n$ 个点的环染色方案数为 $1n∑i=0n−1kgcd⁡(n,i)\dfrac{1}{n}\displaystyle\sum_{i=0}^{n-1}k^{\gcd(n,i)}$ ，可否感性理解呢？

洛谷 P4980 【模板】Pólya 定理

题意

用 $n$ 种颜色给 $n$ 个点染色的方案数。两种方案相同，当且仅当一种方案能够旋转变为“另一方案”。

$n≤109n\le 10^9$ 。

思路

问题是如何快速算出 $1n∑i=0n−1ngcd⁡(n,i)\dfrac{1}{n}\displaystyle\sum_{i=0}^{n-1}n^{\gcd(n,i)}$ 。不妨暴力枚举 $n$ 的约数 $d=gcd⁡(n,i)d=\gcd(n,i)$ ，变为：
$1n∑d∣nndφ(nd)\dfrac{1}{n}\displaystyle\sum_{d|n}n^d\varphi(\frac{n}{d})$

$n$ 太大了不能预处理 $φ\varphi$ ，记得勤取模。时间复杂度为 $T(n)=∑i≥0{O(i)+O(n/i)}=O(n3/4)T(n)=\displaystyle\sum_{i\ge 0}\{O(\sqrt{i})+O(\sqrt{n/i})\}=O(n^{3/4})$ （根据主定理推得）。代码略。

第二类斯特林数

~~为什么先说第二类，因为第二类好像常用一些。~~

斯特林数将两个典型的模型的方案数求解变成一个类似组合数的东西。

概念

${nm}\begin{Bmatrix} n\\ m \end{Bmatrix}$ 表示，将 $n$ 个不同的球放进 $m$ 个相同的盒子里，且每个盒子都非空的方案数。

其递推式的推导：

球 $n$ 单开一个盒子，那么剩下 $n - 1$ 个球放进 $m - 1$ 个盒子： ${n−1m−1}\begin{Bmatrix} n-1\\ m-1 \end{Bmatrix}$ ；
球 $n$ 放进非空的 $m$ 个盒子： $m{n−1m}m\begin{Bmatrix} n-1\\ m \end{Bmatrix}$ 。

所以 ${nm}={n−1m−1}+m{n−1m}\begin{Bmatrix} n\\ m \end{Bmatrix}=\begin{Bmatrix} n-1\\ m-1 \end{Bmatrix}+m\begin{Bmatrix} n-1\\ m \end{Bmatrix}$ 。

特别的， ${n0}=[n=0]\begin{Bmatrix} n\\ 0 \end{Bmatrix}=[n=0]$ ，中括号表示艾弗森括号。

可以 $O(n^2)$ 预处理。

应用

先证明其通项公式，发现其满足下降幂性质：
在这里插入图片描述

CF932E Team Work

题意

给定 $n, k$ ，求 $∑i=1n(ni)ik\displaystyle\sum_{i=1}^n\dbinom{n}{i}i^k$ 。

$n≤109n\le 10^9$ ， $k≤5000k\le 5000$ 。

思路

把组合数用阶乘拆开，再运用斯特林数下降幂的性质：

$∑i=0nn!i!(n−i)!∑j=0k{kj}i!(i−j)!\sum_{i=0}^n\frac{n!}{i!(n-i)!}\sum_{j=0}^k\begin{Bmatrix} k\\ j \end{Bmatrix}\frac{i!}{(i-j)!}$

改变 $i$ 和 $j$ 的枚举顺序， $i$ 从 $j$ 开始到 $n$ ：
$∑j=0k{kj}∑i=jnn!(n−i)!(i−j)!\sum_{j=0}^k\begin{Bmatrix} k\\ j \end{Bmatrix}\sum_{i=j}^n\frac{n!}{(n-i)!(i-j)!}$

强制变成组合数：
$∑j=0k{kj}n!(n−j)!∑i=jn(n−j)!(n−i)!(i−j)!\sum_{j=0}^k\begin{Bmatrix} k\\ j \end{Bmatrix}\frac{n!}{(n-j)!}\sum_{i=j}^n\frac{(n-j)!}{(n-i)!(i-j)!}$

$∑j=0k{kj}n!(n−j)!∑i=jn(n−ji−j)\sum_{j=0}^k\begin{Bmatrix} k\\ j \end{Bmatrix}\frac{n!}{(n-j)!}\sum_{i=j}^n\binom{n-j}{i-j}$

化成 $2$ 次幂形式：
$∑j=0k{nm}n!(n−j)!∑i=0n−j(n−ji)\sum_{j=0}^k\begin{Bmatrix} n\\ m \end{Bmatrix}\frac{n!}{(n-j)!}\sum_{i=0}^{n-j}\binom{n-j}{i}$

$∑j=0k{kj}n!(n−j)!×2n−j\sum_{j=0}^k\begin{Bmatrix} k\\ j \end{Bmatrix}\frac{n!}{(n-j)!}\times2^{n-j}$

$O(k^2)$ 时间复杂度预处理第二类斯特林数即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5002,mod=1e9+7;
ll n,k;
ll S2[N][N],p2[N];
ll qpow(ll x,ll k)
{ll ret=1;while(k){if(k&1)ret=ret*x%mod;x=x*x%mod;k>>=1;}return ret;
}
void init()
{S2[0][0]=1;for(int i=1;i<N;i++)for(int j=1;j<N;j++)S2[i][j]=(S2[i-1][j-1]+j*S2[i-1][j]%mod)%mod;
}
int main()
{scanf("%lld%lld",&n,&k);init();ll ans=0;for(int j=0;j<=min(n,k);j++){ll ret=S2[k][j]*qpow(2,n-j)%mod,mul=1;for(int t=n-j+1;t<=n;t++)ret=ret*t%mod;ans=(ans+ret)%mod;}printf("%lld",ans);return 0;
}

第一类斯特林数

概念

$[nm]\begin{bmatrix} n\\ m \end{bmatrix}$ 表示，将 $n$ 个不同的球摆成 $m$ 个环的方案数。两个环相同，当且仅当一个环通过旋转可以变成第二个环。

其递推式的推导：

球 $n$ 单开一个环，那么剩下 $n - 1$ 个球成 $m - 1$ 个环： $[n−1m−1]\begin{bmatrix} n-1\\ m-1 \end{bmatrix}$ ；
球 $n$ 放进 $m$ 个环，在放了的 $(n - 1)$ 个球后面都可以放： $(n−1)[n−1m](n-1)\begin{bmatrix} n-1\\ m \end{bmatrix}$ 。

所以 $[nm]=[n−1m−1]+(n−1)[n−1m]\begin{bmatrix} n\\ m \end{bmatrix}=\begin{bmatrix} n-1\\ m-1 \end{bmatrix}+(n-1)\begin{bmatrix} n-1\\ m \end{bmatrix}$ 。

特别的， $[nm]=[n=0]\begin{bmatrix} n\\ m \end{bmatrix}=[n=0]$ ，中括号为艾弗森括号。

洛谷 P4609 FJOI2016 建筑师

题意

小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 $n$ 个建筑，每个建筑的高度是 $1$ 到 $n$ 之间的一个整数。

小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 $A$ 个建筑，从最右边（所有建筑都在左边）看能看到 $B$ 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 $i$ 的左(右)边没有任何建造比它高，则建筑 $i$ 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

$\leq n \leq 50000, \ 1 \leq A, B \leq 100, \ 1 \leq T \leq 200000$ 。

思路

中间那个左右都能看见的，高度必然是极值 $n$ 。

除去中间的，左边要看到 $a - 1$ 个，右边要看到 $b - 1$ 个。不妨将能看到的和其左/右边比它矮的看成 $a - 1 + b - 1 = a + b - 2$ 个环（反正互换位置之后，尽管某些环的元素种类改变，但是环的个数不改变），就可以用第一类斯特林数的含义，将剩下 $n - 1$ 和分成 $a + b - 2$ 个环，即 $[n−1a+b−2]\begin{bmatrix} n-1\\ a+b-2 \end{bmatrix}$ 。

然后再 $a + b - 2$ 个环中选各自最大值 $a - 1$ 个，成为左边能看见的（排列方式唯一，必然是从矮到高），即 $(a+b−2a−1)\dbinom{a+b-2}{a-1}$ 。

于是答案为 $[n−1a+b−2](a+b−2a−1)\begin{bmatrix} n-1\\ a+b-2 \end{bmatrix}\dbinom{a+b-2}{a-1}$ 。

预处理第一类斯特林数即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e4+9,M=202,mod=1e9+7;
ll T;
ll S1[N][M],fac[N],inv[N];
ll qpow(ll x,ll k)
{ll ret=1;while(k){if(k&1)ret=ret*x%mod;x=x*x%mod;k>>=1;}return ret;
}
void init()
{S1[0][0]=1;for(int i=1;i<N;i++)for(int j=1;j<M;j++)S1[i][j]=(S1[i-1][j-1]+(i-1)*S1[i-1][j]%mod)%mod;fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;inv[N-1]=qpow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m)
{return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{scanf("%lld",&T);init();while(T--){ll n,a,b;scanf("%lld%lld%lld",&n,&a,&b);printf("%lld\n",S1[n-1][a+b-2]*C(a+b-2,a-1)%mod);}return 0;
}

无根树的 prufer 序列

概念

prufer 序列将节点数为 $n$ 的无根树转化为长为 $n - 2$ 的序列。其表示期望与根的编号无关——定义为每次选择一个编号最小的叶节点并删除，然后在序列中记录其所连接的节点编号，直到剩下两个节点。

在这里插入图片描述
如上图是一棵有 $7$ 个节点的树的 prufer 序列形成过程。

用 prufer 序列同样可以还原出一棵树来。

求法

求一棵树的 prufer 序列。可以维护每个节点的度数，以节点编号为第一关键字扔进堆里排序，当度为 $0$ 时舍弃这个节点。容易做到 $O(nlog⁡n)O(n\log n)$ 。

有 $O (n)$ 的更优秀的算法：“剥叶子”的过程中，每次只会让其父亲节点度数减 $1$ ，因此每删除一个叶节点，至多产生一个新叶节点。

因此可以用一个单调指针 $p os$ 维护当前度数为 $0$ 的最小结点， $p os$ 枚举到了先删 $p os$ ，然后看 $fa_{pos}$ 是否度数变为 $0$ ，如果为 $0$ 就顺带删去了；没准是条链，因此可以 while 一路删上去。

用 prufer 还原一棵树亦然。

P6086 【模板】Prufer 序列

思路

如上所述。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,m,mod,k;
ll fa[N],siz[N];
ll fz(ll x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
void join(ll u,ll v)
{ll fu=fz(u),fv=fz(v);if(fu==fv)return;fa[fu]=fv;siz[fv]+=siz[fu];k--;
}
ll qpow(ll x,ll k)
{ll ret=1;while(k){if(k&1)ret=ret*x%mod;x=x*x%mod;k>>=1;}return ret;
}
int main()
{scanf("%lld%lld%lld",&n,&m,&mod);if(mod==1){puts("0");return 0;}k=n;for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;for(int i=1;i<=m;i++){ll u,v;scanf("%lld%lld",&u,&v);join(u,v);}if(k==1){puts("1");return 0;}ll ans=1;for(int i=1;i<=n;i++)if(i==fz(i))ans=ans*siz[i]%mod;ans=ans*qpow(n,k-2)%mod;printf("%lld",ans);return 0;
}