Digit Tree
题目描述
ZS the Coder has a large tree. It can be represented as an undirected connected graph of $n$ vertices numbered from $0$ to $n-1$ and $n-1$ edges between them. There is a single nonzero digit written on each edge.
One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer $M$, which is coprime to $10$, i.e. $(M, 10)=1$.
ZS consider an ordered pair of distinct vertices $(u, v)$ interesting when if he would follow the shortest path from vertex $u$ to vertex $v$ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by $M$.
Formally, ZS consider an ordered pair of distinct vertices $(u, v)$ interesting if the following states true:
- let $a_1=u, a_2, \ldots, a_k=v$ be the sequence of vertices on the shortest path from $u$ to $v$ in the order of encountering them;
- let $d_i (1 \le i \lt k)$ be the digit written on the edge between vertices $a_i$ and $a_i+1$;
- the integer $\overline{d_1d_2 \ldots d_{k-1}}=\sum_{i=1}^{k-1} 10^{k-1-i}d_i$ is divisible by $M$.
Help ZS the Coder find the number of interesting pairs!
题意概述
给定一棵有$n$个节点的树和一个与$10$互质的数$M$,树上每条边的权值都是小于$10$的正整数。定义$dist_{u, v}$为依次写下从$u$到$v$路径上每条边的权值所得到的数字。求满足$M \mid dist_{u, v}$的点对个数。
数据范围:$2 \le n \le 10^5, \ 1 \le M \le 10^9$。
算法分析
设当前枚举到的节点为$x$。令$depth_u$表示$u$在$x$及它子树中的深度。对于在$x$第$(i+1)$棵子树中的节点$u$和在前$i$棵子树中的节点$v$,有:
$$
\begin{align}
M \mid dist_{u, v} \Leftrightarrow 10^{depth_v}dist_{u, x}+dist_{x, v} \equiv 0 \pmod M \\
M \mid dist_{v, u} \Leftrightarrow 10^{depth_u}dist_{v, x}+dist_{x, u} \equiv 0 \pmod M
\end{align}
$$
对于$(1)$式,化简得$dist_{u, x} \equiv -10^{-depth_v}dist_{x, v} \pmod M$;对于$(2)$式,化简得$10^{-depth_u}dist_{x, u} \equiv -dist_{v, x} \pmod M$。用两个 map 分别存下前$i$棵子树中$10^{-depth_v}dist_{x, v}$和$dist_{v, x}$的值,在处理第$(i+1)$棵子树时直接加上可行的方案数。
代码
1 |
|