Unit Ratio Queries
Asked at Apple· Screen
Reported by the problem's creator, not verified
A converter knows how some units of measure relate. There are n units numbered 0 to n - 1, and they fall into independent families (like length units or temperature units): units of the same family can be converted into each other, units of different families cannot. Each entry conversions[i] = [source, target, factor] says that one unit of source equals exactly factor units of target, and the conversion also works the other way: one unit of target equals 1 / factor units of source. Units that have no conversions are families of their own.
Examples
Example 1
Input: n =
6, conversions =[[0,1,3],[2,1,5],[3,4,2]], queries =[[0,2],[2,0],[3,4],[4,3],[0,3],[5,5],[5,1]]Output:
[200000002,666666673,2,500000004,-1,1,-1]Explanation: Units 0, 1, 2 form one family and 3, 4 another, while unit 5 stands alone. One unit 0 is 3 units 1 and one unit 2 is 5 units 1, so one unit 0 is 3/5 of a unit 2; 3/5 modulo 1000000007 is 200000002 because 5 * 200000002 leaves remainder 3. The reverse ratio 5/3 is 666666673. Units 3 and 4 give 2 and the inverse of 2. Units 0 and 3 are in different families, unit 5 against itself is 1, and unit 5 against any other unit is -1.
Example 2
Input: n =
4, conversions =[[0,1,2],[1,2,3],[2,3,5]], queries =[[0,3],[3,0],[1,3],[2,2]]Output:
[30,233333335,15,1]Explanation: One unit 0 is 2 units 1, which is 6 units 2, which is 30 units 3. Going the other way the ratio is 1/30, which is 233333335 modulo 1000000007 because 30 233333335 leaves remainder 1. Units 1 to 3 give 3 5 = 15, and a unit against itself is 1.