<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_3ffc29ec2c710c8ee7b3513e96d9e67d, O_RDWR) failed: No space left on device (28) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  session_start(): Failed to read session data: files (path: ) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/auth.php</b> on line <b>430</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
====== 2020.08.08-2020.08.14 周报 ======

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

无。
===== _wzx27 =====

==== 专题 ====

[[Matrix Exponentiation]]

==== 题目 ====
牛客九

|  [[20200808比赛记录#A - Groundhog and 2-Power Representation|A - Groundhog and 2-Power Representation]]  |  [[20200808比赛记录#G - Groundhog Chasing Death|G - Groundhog Chasing Death]]  |
牛客十

|  [[20200810比赛记录#D - Hearthstone Battleground | D - Hearthstone Battleground]]  |
==== 比赛 ====

===== Infinity37 =====

==== 专题 ====
暂无。
==== 题目 ====
牛客九

|  [[20200808比赛记录#f_-_groundhog_looking_dowdy| F - Groundhog Looking Dowdy]]  |  [[20200808比赛记录#k_-_the_flee_plan_of_groundhog | K - The Flee Plan of Groundhog]]  |
牛客十

|  [[20200810比赛记录#e_-_game | E - Game]]  |  [[20200810比赛记录#j_-_identical_trees | J - Identical Trees]]  |
==== 比赛 ====
暂无。
===== Zars19 =====

==== 专题 ====

无。
==== 题目 ====

无。
==== 比赛 ====

◉ Codeforces Round 662 (Div. 2)

◉ [[Codeforces Round 663 (Div. 2)]] **DONE**

◉ Codeforces Round 664 (Div. 1)

◉ AtCoder Grand Contest 047
===== 本周推荐 =====
==== Infinity37 ====

**来源**：luoguP3296

**tag**:树hash，费用流转移dp

**概述**：

给定一颗树和两套01权值，现在可以花费1的代价修改某点的权值，问最小修改几次可以使得第一套权值和第二套权值的树同构。

**答案**：

先找到重心，以重心为根对树进行hash，如果有两个重心那就增加一个重心连接两个重心再进行树hash。

我们设状态$F_{i,j}$代表第一套权值的$i$子树与第二套权值的$j$子树同构的最小代价。具体转移要使用一个二分图完备匹配的费用流，对$i,j$这两棵树的所有子树，hash值相同并且树高相同的连接一条边，我们假设这两个点是$u,v$，这条边的流量为1，费用为$F_{u,v}$，然后依次转移即可。

**comments**:费用流转移dp的另一道题目，和第十场的题目主要区别在于无根树的处理，找到重心进行树hash

==== _wzx27 ====

**来源**：[[https://atcoder.jp/contests/agc047/tasks/agc047_c|AGC047C]]

**tag**：FFT、原根

**概述**：

给出 $n$ 个数，两两乘积模 $P$ 的和。

**答案**：

如果从类似生成函数的角度入手，把贡献累计在 $x^i$ 的指数 $i$ 上就可以用 $\text{FFT}$ 求出贡献。但注意到只把指数作为模 $P$ 的值会有问题，由于 $x^i \cdot x^j = x^{i+j}$，但我们实际想要的是 $i*j$ 的答案。于是考虑原根的对数来表示就可以转化成乘法了。

先预处理出每个原根的幂次 $g^i \% P$ 的值和 $x = g^i \% p$ 的对应幂次 $i$,然后做一次 $\text{FFT}$ 即可，但注意要减去同一个数乘了自己的贡献。

**comments**：一个原根的经典用法，需要掌握。

==== Zars19 ====

**来源**：CF1388E - Uncle Bogdan and Projections

**tag**：计算几何，Convex Hull Trick

**概述**：

给 $x$ 轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x$ 轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。

**答案**：

如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。

而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta$ 为投影线与 $x$ 轴正方向的夹角， $(x,y)$ 投影在横坐标 $x-\frac y{tan(\theta)}$ 的位置。以 $-\frac 1{tan(\theta)}$ 为自变量，则 $y_i$ 为斜率， $x_i$ 为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)}$ 可以二分。最小值同理。

**comments**：Convex Hull Trick可以适用在很多题上><