线性基

无

无

生成函数 1

多项式 3

生成函数 2

无

见专题部分

匈牙利算法

图匹配

增广路定理

网络流简介

Dinic 算法

类 Dinic 算法

Codeforces Round #662 (Div. 2) pro:3/4/6 rk:1278/13194

Codeforces Round #663 (Div. 2) pro:3/5/5 rk:1137/13140

Codeforces Round #664 (Div. 2) pro:3/4/6 rk:1243/16242

洛谷P3812

线性基

求若干数异或和的最值

线性基的模板题

CF923E

生成函数，$\text{NTT}$

给定一个数 $x\in [0,n]$，其中 $x=i$ 的概率为 $p_i$。每次操作将 $x$ 等概率变成 $[0,x]$ 中的某个数。问 $m$ 轮操作后 $x=i$ 的概率。

设 $f_{k,i}$ 表示 $k$ 轮操作后 $x=k$ 的概率，显然有 $f_{0,i}=p_i$，并可以得到递推式

$$f_{k,i}=\sum_{j=i}^{n} \frac {f_{k-1,j}}{j+1}$$

考虑构造生成函数优化递推过程

$$ \begin{equation}\begin{split} F_k(x)&=\sum_{i=0}^n f_{k,i}x^i\\ &=\sum_{i=0}^n \sum_{j=i}^{n} \frac {f_{k-1,j}}{j+1}x^i\\ &=\sum_{j=0}^n \frac {f_{k-1,j}}{j+1}\sum_{i=0}^j x^i\\ &=\frac 1{x-1}\sum_{j=0}^n f_{k-1,j}\frac {x^{j+1}-1}{j+1}\\ &=\frac 1{x-1}\sum_{j=0}^n f_{k-1,j}\int_1^x t^j \mathrm{d}t\\ &=\frac 1{x-1}\int_1^x F_{k-1}(t)\mathrm{d}t \end{split}\end{equation} $$ 由于 $\frac 1{x-1}$ 和 $\int_1^x$ 不利于更进一步处理，于是考虑构造辅助函数 $G_k(x)=F_k(x+1)$

$$ \begin{equation}\begin{split} G_k(x)&=\frac 1x\int_1^{x+1} F_{k-1}(t)\mathrm{d}t\\ &=\frac 1x\int_0^{x} F_{k-1}(t+1)\mathrm{d}t\\ &=\frac 1x\int_0^{x} G_{k-1}(t)\mathrm{d}t\\ &=\sum_{i=0}^n \frac {g_{k-1,i}}{i+1}x^i \end{split}\end{equation} $$ 于是有 $g_{k,i}=\frac {g_{k-1,i}}{i+1}$，所以 $g_{m,i}=\frac {g_{0,i}}{(i+1)^m}$。

接下来考虑 $g_{k,i}$ 与 $f_{k,i}$ 之间的转化，简记 $g_i=g_{k,i},f_i=f_{k,i}$，于是有

$$g_i=\sum_{j=i}^n {j\choose i}f_j=\sum_{j=i}^n \frac{j!}{i!(j-i)!}f_j=\frac 1{i!}\sum_{j=0}^{n-i}\frac {(i+j)!f_{i+j}}{j!}$$

记 $a_i=\frac 1{i!},b_i=(n-i)!f_{n-i}$，于是有 $g_i=\sum_{j=0}^{n-i}a_ib_{n-i-j}$。

直接 $\text{NTT}$ 可以由 $F_0(x)$ 求出 $G_0(x)$ 进而求出 $G_m(x)$。考虑对 $\sum_{i=0}^n \frac 1{i!}x^i$ 求逆再与 $G_m(x)$ 卷积即可求出 $F_m(x)$，总时间复杂度 $O(n\log n)$。

不错的生成函数练习题。

P2756 飞行员配对方案问题

标签

二分图最大匹配

题意

两个国家的飞行员进行配对。

题解

可用匈牙利算法求解。也可以转化为最大流问题解决，首先建一个源点和一个汇点，源点与外籍飞行员间建立一条有向边(外籍飞行员方向)，汇点与英籍飞行员建立一条有向边(英籍飞行员方向)，所有边的容量为1，也就是说流量最多为1，然后求最大流。

评价

二分图最大匹配模板题，也是网络流建模的简单题。