题目： 给你一个次数不超过的函数在点上的取值，以及一个整数，就的值。 答案对取模。 题解： 当然这题可以推广成很多题,例如:求中的连续的m项。 我们首先要会普通的拉格朗日插值， 还要会在取值连续时的做法， 你还要会多项式乘法，由于本题对取模，所以用，元根是 前置知识有点多啊啊啊 由于是连续的点，即$$ 我们设 为多项式 我们可以先把等多项式用拉格朗日插值的方法预处理出来，再用把这些多项式乘起来得到 代码： #include<bits/stdc++.h> using namespace std; #define next Next #define int long long cons...

题意： 给你一棵个点的树和条路径，每条路径都有一个权值。 有k组询问，每次询问给你一条路径和一个值。 问你被这条路径包含的所有路径中的第K小的路径的值 题解： 我用的是树上莫队+平衡树(或分块)的方法 平衡树的话是,分块的话就是 稍微口胡一下树上莫队： 把一颗树的欧拉序搞出来，对于查询的两点（假设入栈早）。 如果是一条链， 否则,,同时莫队是要加入 平衡树有什么用？ 我们看到题目中求第K大的值，就想到了用平衡树来维护值。 因为平衡树支持插入，删除和查找K大值，和莫队很配。 但其实分块更加优，分块能更好的和莫队配合。 因为分块的插入，查询，总的复杂度是(n，m同阶) 现在要处理的就是如何判断一条...

经过同学的指点，发现F题有一只log的做法——点分树。首先两个点在点分树上的lca一定在原树上这两个点的路径上。所以我们把x-y的路径分成x-点分树上的lca 和 点分树上的lca-y的两条路径。用树链剖分的方法维护一下点分树上的点到其他点的信息即可。