CVBB ACM Team

到此差别页面的链接

--- 2022-2023:teams:kunkunkun:2022-nowcoder-3 [2022/07/31 14:10]
sd_ltt
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-3 [2022/08/31 14:55] (当前版本)
purplewonder
@@ 行 1: / 行 1: @@
 ====== 2022 牛客暑期多校训练营3 ======
 ===== D =====
 给定一棵树和一个起点，1号节点为终点，随机选其中K条边变成指向终点的单向边，在树上随机游走，求到达终点的期望步数。
@@ 行 10: / 行 11: @@
 $$
 预处理前缀和，时间复杂度 $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：出错形式多种多样，总之是在各种调试细节，以及尝试各种能过样例的方法。

CVBB ACM Team

用户工具

站点工具

页面工具