「Codeforces 653G」Move by Prime – 题解

主要思路

这些 3000+ 题目里做过最小清新的。

首先肯定可以想到,分解质因子之后,对于一个 \(p^c\),把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。

继续阅读「Codeforces 653G」Move by Prime – 题解

Universal OJ#450. 「集训队作业2018」复读机 – 题解

主要思路

首先对于 \(d = 1\),答案就是 \(k^n\)。

对于 \(d = 2\),其实发现可以用生成函数来直接乘:\( A(x) = \sum_{i = 0}^\infty \frac{1}{i!} x^i [2 | i] \),那么答案就是 \( A^k(x)[x^n] \)。发现可以变通奇偶性,所以 \(A(x) = \frac{e^x + e^{-x}}{2}\),然后试着二项式展开:

继续阅读Universal OJ#450. 「集训队作业2018」复读机 – 题解

P3978:[TJOI2015]概率论 – 题解

推导思路

第一次坐到这种类型的题,社会社会(抱拳)。

先考虑怎么算分母:如果有 \(f_i\) 代表大小为 \(i\) 的树的种类数,那么可以显然得到 \(f_i = \sum_{j = 0}^{n – 1} f_j f_{n – j – 1}\)。得到这一步之后,分治 FFT?不,数据范围到达了惊人的 \(10^9\),所以分治 FFT 显然不现实。我们可以继续推:

继续阅读P3978:[TJOI2015]概率论 – 题解

HNOI 2018 省队集训 Day 1 – 解题报告

A – Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

继续阅读HNOI 2018 省队集训 Day 1 – 解题报告