NOIP 模拟 9

标签：直接 NOIP sum 然后 父亲 choose prod 模拟

A 送信卒

直接二分。

B 共轭树图

看了好多篇题解都说的不太清楚，随便观察一下得知子树间互不影响，且没有边相交，在不连直接父亲的情况下，孩子的父亲一定比祖先的父亲靠上，所以这道题考虑的是和祖先的关系，而不是与孩子的关系，然后这个时候可简单地设计出一种状态，\(f_{u,i}\) 表示 \(u\) 节点连向深度为 \(i\) 的父亲的方案数，如果不考虑连直接父亲的情况，转移是比较简单的，\(f_{u,i}=\prod\sum_{k=1}^if_{v,k}\)，如果加上直接连父亲的，就会导致边相交，不合法，考虑合法的部分，\(f_{v,i+1}\) 就是这一部分，对于孩子连向 \(i+1\) 就相当于连到了 \(u\)，然后转移就是 \(f_{u,i}=\prod\sum_{k=1}^{i+1}f_{v,k}\)，除了 \(n\)，都有 \(f_{i,dep_i}=0\)。
发现上面的替代很不自然，考虑 \(f_{u,i}\) 表示在新树中，\(u\) 的深度为 \(i\) 的方案数，这样 \(v\) 可以向上随便连，深度就为 \([2,i+1]\)，所以 \(f_{u,i}=\prod\sum_{k=2}^{i+1}f_{v,k}\)，这个初值除了 \(n\) 都有 \(f_{u,1}=0\)。

C 摸鱼军训

把小于 \(x\) 的看成 \(0\)，大于的看成 \(1\)，然后手玩发现就是 \(1\) 往前平移，然后查答案就是找到第 \(k\) 个 \(1\) 的位置减去 \(k\) 即可，本质就是前 \(k\) 大排好序了，然后 \(x\) 每次移动都会装上一个 \(1\)。

D 神奇园艺师

对于一个质因数，都达到中位数一定最小，调整法证明即可。有一种暴力就是直接统计每个质数，然后将所有指数排序后，统计每个指数的贡献，枚举左边选多少个，右边选多少个，假设左边选了 \(a\) 个，右边选了 \(b\) 个，如果 \(a<b\) 那么贡献是负的，如果 \(a=b\) 那么没有贡献，否则贡献就是负的，暴力枚举可以做到 \(\mathcal{O}(n^3\log n)\) 的复杂度。
上面的做法太暴力了，并且这个东西一看推式子就很有前途，对于排名为 \(i\) 的数，正贡献的系数是 \(\sum_{a=0}^{i-1}\sum_{b=a+1}^{n-i}{i-1\choose a}{n-i\choose b}\)，首先完全不用推的前缀和就可以减去一个枚举，然后发现 \(a\) 和 \(b\) 没联系，设 \(d=b-a\)，有

\[\begin{aligned} &\sum_{d=1}^{n-i}\sum_{a=0}^{i-1}{i-1\choose a}{n-i\choose a+d}\\ =&\sum_{d=1}^{n-i}\sum_{a=0}^{\min(i-1,n-i-d)}{i-1\choose a}{n-i\choose n-i-a-d}\\ =&\sum_{d=1}^{n-i}{n-1\choose n-i-d}\\ =&\sum_{d=0}^{n-i-1}{n-1\choose d} \end{aligned} \]

中间是一个范德蒙德卷积式，然后就化成了组合数前缀和的形式，直接预处理即可。

总结

这场做了一整场 T2，一直在想和孩子的联系来设计状态，T3 看了一眼不咋会，T4 直接摆了，其实这场全是可做题，太菜了。

标签：直接,NOIP,sum,然后,父亲,choose,prod,模拟
From： https://www.cnblogs.com/Ishar-zdl/p/18551116