跳转至

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 单位可以通过正向或反向转换的组合唯一地转换为任何其他单位。

解法

方法一

1


1


1


1

评论