LOJ 6495~6497「雅礼集训 2018 Day1」

最新推荐文章于 2020-05-22 21:59:08 发布

扩展的灰

最新推荐文章于 2020-05-22 21:59:08 发布

阅读量1.4k

点赞数 1

分类专栏： OI 图论 --------连通性求解策略 ----动态规划 --------树形dp-DAG上dp --------期望dp --------序列形dp 数学 ----组合数学 ----概率/期望 ----多项式相关文章标签：动态规划 FFT 圆方树扩展的灰

本文链接：https://blog.csdn.net/JacaJava/article/details/85724377

版权

博客详细解析了雅礼集训2018第一天的三道题目，涉及动态规划、树状数组、圆方树和扩展的灰等相关算法。通过讲解和代码示例展示了如何将复杂问题转化为O(n^4)、O(n log n)的解决方案，适合进阶学习者参考。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

.
真是看懂std就秒的三道题，但是看懂就很难啊
（感谢superguymj和memset0两个大佬的代码）
稍微说一下题解

--------------------------------------------------------

「雅礼集训 2018 Day1」树

这道题的正解被superguymj大佬吊打了，原来 $O(n·2^n)$ 变成了 $O(n^4)$
取整？直接打表就行了不管了
对于取模的答案，首先考虑dp，我们记 $F (i, j)$ 表示i个节点高度为j的方案数，期望最后除个 $n!$ 就行了
怎么转移？发现没法转移？麦老大给出了一个非常通俗的方法 $F(i,j)=\sum_{x=1}^i\big[(\sum_{y=1}^{j-2}F(i-x,j)*F(x,y)*C(i-2,x-1)+$