跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
legal_string
»
各季度训练计划及训练记录
»
2020_08_08--2020_08_14_周报
2020-2021:teams:legal_string:各季度训练计划及训练记录:2020_08_08--2020_08_14_周报
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
[[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,然后求最大流。 **评价** 二分图最大匹配模板题,也是网络流建模的简单题。
2020-2021/teams/legal_string/各季度训练计划及训练记录/2020_08_08--2020_08_14_周报.txt
· 最后更改: 2020/08/14 14:45 由
jxm2001
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部