CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://112.74.186.118/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/08/08--2020/08/14 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

==== 专题 ====

[[..:qgjyf2001:线性基]]

==== 比赛 ====

无

==== 题目 ====

无

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:生成函数_1|生成函数 1]]

[[..:jxm2001:多项式_3|多项式 3]]

[[..:jxm2001:生成函数_2|生成函数 2]]

==== 比赛 ====

无

==== 题目 ====

见专题部分

===== 王赵安 =====

==== 专题 ====

[[..:lgwza:匈牙利算法|匈牙利算法]]

[[..:lgwza:图匹配|图匹配]]

[[..:lgwza:增广路定理|增广路定理]]

[[..:lgwza:网络流简介|网络流简介]]

[[..:lgwza:Dinic 算法|Dinic 算法]]

[[..:lgwza:类 Dinic 算法|类 Dinic 算法]]
==== 比赛 ====

[[..:lgwza:Codeforces Round 662 (Div. 2)|Codeforces Round #662 (Div. 2)]] ''%%pro:3/4/6%%''  ''%%rk:1278/13194%%''

[[..:lgwza:Codeforces Round 663 (Div. 2)|Codeforces Round #663 (Div. 2)]] ''%%pro:3/5/5%%''  ''%%rk:1137/13140%%''

[[..:lgwza:Codeforces Round 664 (Div. 2)|Codeforces Round #664 (Div. 2)]] ''%%pro:3/4/6%%''  ''%%rk:1243/16242%%''



==== 题目 ====

===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P3812|洛谷P3812]]

=== 标签 ===

线性基

=== 题意 ===

求若干数异或和的最值

=== 题解 ===

线性基的模板题

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/CF923E|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)$。

=== 评价 ===

不错的生成函数练习题。

==== 王赵安 ====

[[https://www.luogu.com.cn/problem/P2756|P2756 飞行员配对方案问题]]

**标签**

二分图最大匹配

**题意**

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

**题解**

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

**评价**

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

用户工具

站点工具

页面工具
