[HDU4812]D Tree(点分治,逆元)

发布于 2018-02-26  111 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4812]D Tree(点分治,逆元)

Description

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 10 6 + 3) equals to K?
Can you help them in solving this problem?

Http

HDU

Tag

点分治,逆元

题目大意

给出一棵树,求一条起点终点字典序最小的点对,使得点对经过路径上点权之积在\(mod 1e6+3\)下等于给定的\(K\)

解决思路

考虑点分治。每一次从重心出发,求出所有点到重心的路径上除重心以外的点权之积。这里要去掉重心的原因是,我们在拼路径的时候,直接拼的话就会重复算一遍重心的点权。那么,类似这一题的方法,记录\(Min[i]\)表示到重心路径上除重心外的点权之积为\(i\)的编号最小的点,我们可以每一次遍历重心的一棵子树,用之前遍历过的其他子树的信息来与这一次的遍历构造答案。在这一次遍历完之后,再用这一次的信息来更新\(Min\)。
另外为了方便地求出比如已知\(x\)和\(x*y==z (mod p)\),先预处理出\([1,Mod]\)内所有数关于\(Mod\)的逆元。递推即可。
最后,题目明确指出了可能的爆栈风险,所以需要在提交的地方选择\(C++\)并在代码首部加入\(pragma\)一句以扩大栈空间。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4812]D Tree(点分治,逆元)


HNCJ OIer