题解 CF715C 【Digit Tree】

2018-12-25 09:09:08


树上统计显然是点分治。

考虑怎么统计。设当前的根为 $root$ ,根到 $x$ 的路径上的数是 $d_1$ ,根到 $y$ 的路径上的数是 $d_2$ ,根到 $y$ 的距离(此时 $y$ 的深度)为 $dep$ 。

若 $x\to y$ 这条路径合法,显然需要满足:

$$d_1\cdot10^{dep}+d_2\equiv0\pmod m$$

这样子不好搞,我们要把 $d_2$ 和 $dep$ 放到一起去。

因为 $\gcd(10,m)=1$ 即 $m$ 与 $10$ 互质,所以可以把两边同时除以 $10^{dep}$ ,得到:

$$d_1+d_2\cdot10^{-dep}\equiv0\pmod m$$

这样变得很好搞。 $10^{-dep}$ 求个逆元就行,可以预处理一下 $10$ 的幂。

用一个map来记录 $d_1$ ,用pair来记录<d2,dep>这样的二元组。统计答案时枚举二元组,然后到map里找对应的数量累加即可。

注意, $0$ 也能被 $m$ 整除。

细节见「代码」