====== 2022 牛客暑期多校训练营3 ======

===== D =====
给定一棵树和一个起点，1号节点为终点，随机选其中K条边变成指向终点的单向边，在树上随机游走，求到达终点的期望步数。

不考虑选单向边，设 $f_x$ 为从 $x$ 走到其父亲的期望步数，则有 $f_x=\dfrac{1+\sum_v (1+f_v+f_x)}{d(x)}$，化简可得$f_x=d(x)+\sum_vf_v=2size(x)-1 $，其中 $size(x)$ 为 $x$ 的子树大小。\\
设出发点 $s$，其到 $1$ 的路径 $L$ 为 $s,v_k,\cdots,v_1,1$，则答案 $ans=f_s+f_{v_k}+\cdots+f_{v_1}$\\
考虑单向边 (v,u) 带来的影响，当该边到 $L$ 的路径上没有单项边时会对答案产生贡献，设路径长度为 $len$, $L$ 与该路径交点到 $1$ 的路径长度为 $L^\prime$,则对答案的贡献为
$$
-\dfrac{2*size(v)*\sum_{i=0}^{L^\prime-1}C_{n-1-len-i}^{K-1}}{C_{n-1}^{K-1}}
$$
预处理前缀和，时间复杂度 $O(n)$
===== G =====

**题目大意：给两个凸包，各有速度，求相撞时间**

**设两个凸包为$A$和$B$，实际上可以认为$B$不动，$A$以速度$V$运动**

**设$A$凸包加上位移$M$后与$B$凸包有交，那么闵可夫斯基和可以在$O(nlogn)$的时间复杂度内求出位移$M$的合法区域$P$**

**若$P$中包含原点，则答案为$0$**

**从原点向$V$引一条射线，与$P$相交，求所有交点，取距离最短的那一个即可**

===== I =====
**本题需要求$E(x^k)$，在组合意义中一般处理的是方案数，于是考虑$n!E(x^k)$的组合意义**

**首先枚举哪些元素在对应位置上，然后其他元素错排：**
$$
n!E(x^k)=\sum_{i=0}^nC_n^ii^kD_{n-i}
$$

**套路：看到形如$n^k$的东西，需要想到第二类斯特林数**

**因为$n^k$表示把$k$个不同的球放入$n$个不同盒子（盒子可以为空）的方案数，我们枚举$i$为非空盒的个数，可得到**
$$
n^k=\sum_{i=0}^kS(k,i)\times i!\times C(n,i)
$$

**然后将$i^k$用第二类斯特林数替换：**
$$
n!E(x^k)=\sum_{i=0}^nC_n^iD_{n-i}\sum_{j=0}^kS(k,j)j!C_i^j
$$
**发现$C_n^i*C_i^j$具有组合意义，可替换成$C_n^j*C_{n-j}^{i-j}$：**
$$
n!E(x^k)=\sum_{j=0}^kS(k,j)j!C_n^j\sum_{i=0}^nC_{n-j}^{i-j}D_{n-i}
$$
**直接将$i$替换成$i+j$：**
$$
n!E(x^k)=\sum_{j=0}^kS(k,j)j!C_n^j\sum_{i=0}^{n-j}C_{n-j}^{i}D_{n-i-j}
$$
**当$j>n$时，后面那个$\sum_i=0$，否则有组合意义，实际上相当于长度为$n-j$的所有排列数，也就是$(n-j)!$：**
$$
n!E(x^k)=\sum_{j=0}^{min(k,n)}S(k,j)j!C_n^j(n-j)!
$$
**当$j>k$时$S(k,j)=0$，再将组合数拆开，可得到：**
$$
n!E(x^k)=\sum_{j=0}^nS(k,j)n!\\
E(x^k)=\sum_{i=0}^nS(k,i)
$$

**发现模数$862118861=857×997×1009$，可以分别考虑每个质数，再使用中国剩余定理合并**

**由贝尔数的相关知识可以知道**
$$
B_n=\sum_{k=0}^nS(n,k)
$$
**于是当$k\leq n$时，答案就是$B_n$**

**考虑到$k\leq n+5*10^3$，所以当$k>n$时，答案可以表示为**
$$
E(x^k)=B_n-\sum\limits_{i=n+1}^kS(k,i)
$$

**现在考虑如何快速求$B_n$**

**贝尔数满足Touchard同余，则有**
$$
B_{n+p}\equiv B_n+B_{n+1}(mod\,p)
$$
**这是常系数齐次线性递推，可以在$O(k^2logn)$的复杂度内求出$B_n$**

**现在考虑如何快速求$\sum\limits_{i=n+1}^kS(k,i)$**

**由题解给出的公式，有**
$$
S(x,x-n)=\sum\limits_{k=0}^{n-1}E(n,k)*C_{x+n-k-1}^{2n}\\
E(n,k)=(2n-k-1)C_{n-1}^{k-1}+(k+1)
$$
**组合数可以用卢卡斯定理快速计算，然后利用上述公式进行递推即可求解**

===== Replay =====

首先开的是C题。啥思路都没。

之后看到了A。前缀lca，写了个倍增很快切掉了。

之后看到了J。是个模拟+最短路。高湘一去写了，不久后写完了。

之后继续来看C。想着大概暴力可以过，于是高湘一去写了一个暴力。但是sort的cmp函数写的出了锅。是因为在两个字符串相等的时候返回了1。于是炸了好几发。

期间在不停的waH题。是一个后缀自动机。但是属实是对后缀自动机的一些操作不够熟悉，导致到最后也没过。

同时也在不停的waF题。是一个tarjan。如果是比较靠后的场次，这种题本来是应该我来写的。也是出现了许多细节问题，导致最后也没有过。

===== Dirt =====

C：sort的cmp函数出锅。以及有一发是因为没有注释掉freopen

H：出错形式多种多样，总之是在各种调试细节，以及尝试各种能过样例的方法。