洛谷4365 [九省联考2018]秘密袭击coat
Luogu LOJ 分析 首先把第 $k$ 大转化掉： 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...
Luogu LOJ 分析 首先把第 $k$ 大转化掉： 不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。 看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都...
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。 至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。 代码 // =...
Luogu LOJ 分析 考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。 首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即 总时间复杂度为 $\mathcal{O}(n^2m)$。 代码 // ============...
CodeForces Luogu 分析 设 $dp_{i,j}$ 表示以 $i$ 为根的子树，$i$ 的权值为 $j$ 的方案数。容易得到转移 前缀和优化即可做到 $\mathcal{O}(D)$ 转移，总时间复杂度 $\mathcal{O}(nD)$。 考虑优化。可以发现，$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式（可以理解为每个叶子节点都为一次式，往上合并时做乘法从而次...
已知 $n$ 次多项式 $P(x)$ 在 $n+1$ 个点的值 $P(x_0),P(x_1),\cdots,P(x_n)$，则
Luogu 分析 完全图的生成树个数为 $n^{n-2}$ ，每条边会出现 $2n^{n-3}$ 次。 容易得到答案为 考虑怎么计算 $\sum_{i=n+1}^{2n-1}i^k$ 。可以发现 $i^k$ 是完全积性函数，直接线性筛后求前缀和即可。 整理一下思路： 首先线性筛求出 $i^k$ ，然后求出它的前缀和。此部分时间复杂度为 $O(k)$。 然后利用算出的前缀和，递推计算出 ...