跳转至

3535. 单位转换 II 🔒

题目描述

有 n 种单位，编号从 0 到 n - 1。

给定一个二维整数数组 conversions，长度为 n - 1，其中 conversions[i] = [sourceUniti, targetUniti, conversionFactori] ，表示一个 sourceUniti 类型的单位等于 conversionFactori 个 targetUniti 类型的单位。

同时给定一个长度为 q 的 2 维整数数组 queries，其中 queries[i] = [unitAi, unitBi]。

返回一个长度为 q 的数组 answer，其中 answer[i] 表示多少个 unitBi 类型的单位等于 1 个 unitAi 类型的单位，并且当 p 和 q 互质的时候可以表示为 p/q。以 pq-1 返回每个 answer[i] 对 109 + 7 取模 的值，其中 q-1 表示 q 模 109 + 7 的乘法逆元。

 

示例 1：

输入：conversions = [[0,1,2],[0,2,6]], queries = [[1,2],[1,0]]

输出：[3,500000004]

解释：

  • 在第一次查询中，我们可以反向使用 conversions[0]，然后使用 conversions[1] 将单位 1 转换为 3 个单位的类型 2。
  • 在第二次查询中，我们可以反向使用 conversions[0] 将单位 1 转换为 1/2 个单位的类型 0。我们返回 500000004 因为它是 2 的乘法逆元。

示例 2：

输入：conversions = [[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]], queries = [[1,2],[0,4],[6,5],[4,6],[6,1]]

输出：[3,12,1,2,83333334]

解释：

  • 在第一次查询中，我们可以反向使用 conversions[0]，然后使用 conversions[1] 将单位 1 转换为 3 个单位的类型 2。
  • 在第二次查询中，我们可以使用 conversions[1]，然后使用 conversions[3] 将单位 0 转换为 12 个单位的类型 4。
  • 在第三次查询中，我们可以使用 conversions[5]，反向使用 conversions[2]，conversions[1]，然后使用 conversions[4] 将单位 6 转换为 1 个单位的类型 5。
  • 在第四次查询中，我们可以反向使用 conversions[3]，反向使用 conversions[1]，conversions[2]，然后使用 conversions[5] 将单位 4 转换为 2 个单位的类型 6。
  • 在第五次查询中，我们可以反向使用 conversions[5]，反向使用 conversions[2]，然后使用 conversions[0] 将单位 6 转换为 1/12 个单位的类型 1。我们返回 83333334 因为它是 12 的乘法逆元。

 

提示：

  • 2 <= n <= 105
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 109
  • 1 <= q <= 105
  • queries.length == q
  • 0 <= unitAi, unitBi < n
  • 保证 0 单位可以通过正向或反向转换的组合唯一地转换为任何其他单位。

解法

方法一：DFS + 模逆元

由题意可知，转换关系构成一棵以 \(0\) 为根的有向树。从根节点 \(0\) 出发 DFS，维护 res[i] 表示 \(1\) 个单位 \(0\) 等于多少个单位 \(i\)。

对于查询 \((unitA, unitB)\)，答案为 \(\frac{res[unitB]}{res[unitA]}\)，对 \(10^9 + 7\) 取模即 res[unitB] * res[unitA]^(MOD - 2) % MOD，其中 MOD - 2 利用费马小定理求模逆。

时间复杂度 \(O(n + q \log MOD)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为单位种类数，而 \(q\) 为查询次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def queryConversions(
        self, conversions: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        def dfs(s: int, mul: int) -> None:
            res[s] = mul
            for t, w in g[s]:
                dfs(t, mul * w % mod)

        mod = 10**9 + 7
        n = len(conversions) + 1
        g = [[] for _ in range(n)]
        for s, t, w in conversions:
            g[s].append((t, w))
        res = [0] * n
        dfs(0, 1)
        ans = []
        for x, y in queries:
            ans.append(res[y] * pow(res[x], mod - 2, mod) % mod)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private final int mod = (int) 1e9 + 7;
    private List<int[]>[] g;
    private int[] res;

    public int[] queryConversions(int[][] conversions, int[][] queries) {
        int n = conversions.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : conversions) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }

        res = new int[n];
        dfs(0, 1);

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            ans[i] = (int) ((long) res[y] * qpow(res[x], mod - 2) % mod);
        }
        return ans;
    }

    private void dfs(int s, long mul) {
        res[s] = (int) mul;
        for (var e : g[s]) {
            dfs(e[0], mul * e[1] % mod);
        }
    }

    private long qpow(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> queryConversions(vector<vector<int>>& conversions, vector<vector<int>>& queries) {
        const int mod = 1e9 + 7;
        int n = conversions.size() + 1;
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : conversions) {
            g[e[0]].emplace_back(e[1], e[2]);
        }

        vector<int> res(n);

        auto dfs = [&](this auto&& dfs, int s, long long mul) -> void {
            res[s] = mul;
            for (auto [t, w] : g[s]) {
                dfs(t, mul * w % mod);
            }
        };
        dfs(0, 1);

        auto qpow = [&](long long x, int n) {
            long long res = 1;
            while (n) {
                if (n & 1) {
                    res = res * x % mod;
                }
                x = x * x % mod;
                n >>= 1;
            }
            return res;
        };

        vector<int> ans;
        for (auto& q : queries) {
            ans.push_back(res[q[1]] * qpow(res[q[0]], mod - 2) % mod);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func queryConversions(conversions [][]int, queries [][]int) []int {
    const mod = int(1e9 + 7)
    n := len(conversions) + 1

    g := make([][]struct{ t, w int }, n)
    for _, e := range conversions {
        s, t, w := e[0], e[1], e[2]
        g[s] = append(g[s], struct{ t, w int }{t, w})
    }

    res := make([]int, n)

    var dfs func(int, int)
    dfs = func(s, mul int) {
        res[s] = mul
        for _, e := range g[s] {
            dfs(e.t, mul*e.w%mod)
        }
    }
    dfs(0, 1)

    qpow := func(x, n int) int {
        res := 1
        for n > 0 {
            if n&1 > 0 {
                res = res * x % mod
            }
            x = x * x % mod
            n >>= 1
        }
        return res
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = res[q[1]] * qpow(res[q[0]], mod-2) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function queryConversions(conversions: number[][], queries: number[][]): number[] {
    const mod = BigInt(1e9 + 7);
    const n = conversions.length + 1;

    const g: { t: number; w: number }[][] = Array.from({ length: n }, () => []);
    for (const [s, t, w] of conversions) {
        g[s].push({ t, w });
    }

    const res: number[] = Array(n).fill(0);

    const dfs = (s: number, mul: number): void => {
        res[s] = mul;
        for (const { t, w } of g[s]) {
            dfs(t, Number((BigInt(mul) * BigInt(w)) % mod));
        }
    };
    dfs(0, 1);

    const qpow = (x: number, n: number): number => {
        let res = 1n;
        let a = BigInt(x);
        while (n > 0) {
            if (n & 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            n >>= 1;
        }
        return Number(res);
    };

    const ans: number[] = [];
    for (const [x, y] of queries) {
        ans.push(Number((BigInt(res[y]) * BigInt(qpow(res[x], 1e9 + 5))) % mod));
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
impl Solution {
    pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        const MOD: i64 = 1_000_000_007;
        let n = conversions.len() + 1;

        let mut g = vec![Vec::<(usize, i64)>::new(); n];
        for e in conversions {
            g[e[0] as usize].push((e[1] as usize, e[2] as i64));
        }

        let mut res = vec![0_i64; n];

        fn dfs(s: usize, mul: i64, g: &Vec<Vec<(usize, i64)>>, res: &mut Vec<i64>) {
            res[s] = mul;
            for &(t, w) in &g[s] {
                dfs(t, mul * w % MOD, g, res);
            }
        }

        dfs(0, 1, &g, &mut res);

        fn qpow(mut x: i64, mut n: i32) -> i64 {
            let mut res = 1_i64;
            while n > 0 {
                if n & 1 == 1 {
                    res = res * x % MOD;
                }
                x = x * x % MOD;
                n >>= 1;
            }
            res
        }

        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let x = q[0] as usize;
            let y = q[1] as usize;
            ans.push((res[y] * qpow(res[x], 1_000_000_005) % MOD) as i32);
        }
        ans
    }
}

评论