Problem Description
There is a given integer array nums and a query array queries. Each query consists of two integers (l, r), requesting the value of nums[l] * nums[l + 1] * ... * nums[r]. The size of the nums array can be up to 10^5, and the length of queries can be up to 10^4. Since the result of the multiplication can be very large, the output must be the remainder when divided by 10^9 + 7.
Input Format
The first line contains the size of the array n and the number of queries q. The second line contains an array nums of n integers, followed by q lines where each line contains the query values l and r.
Output Format
Output the results of the calculations for each query, one result per line.
Example
5 3
2 3 4 5 6
0 2
1 3
2 4
Output
24
60
120
Solution Explanation
To solve this problem, we need a method to quickly compute the product over a range. Simply iterating through the range for each query to calculate the product would lead to a time complexity of O(q * n), which could result in up to 10^9 operations in the worst case. This is impractical, so we use a Prefix Product strategy to reduce time complexity.
Prefix Product Method
First, we store the cumulative product of the elements in the nums array to quickly calculate the results of the queries.
C#
int mod = 1000000007;
int[] prefixProduct = new int[n + 1];
prefixProduct[0] = 1;
for (int i = 1; i <= n; i++) {
prefixProduct[i] = (int)((1L * prefixProduct[i - 1] * nums[i - 1]) % mod);
}
Here, prefixProduct[i] stores the value of nums[0] * nums[1] * ... * nums[i - 1]. With this structure, we can easily and quickly compute the product over a range.
Calculating the Range Product
Now, for each query (l, r), the range product nums[l] * nums[l + 1] * ... * nums[r] can be calculated as follows:
C#
int result = (int)((1L * prefixProduct[r + 1] * modInverse(prefixProduct[l]) % mod) % mod);
Here, the modInverse function calculates the modular inverse. The inverse can be implemented as follows:
C#
int modInverse(int a) {
return power(a, mod - 2);
}
int power(int x, int y) {
int res = 1;
while (y > 0) {
if ((y & 1) == 1) {
res = (int)((1L * res * x) % mod);
}
y >>= 1;
x = (int)((1L * x * x) % mod);
}
return res;
}
Final Code
Based on the above explanation, the complete code would look like this:
C#
using System;
class Program {
static int mod = 1000000007;
static void Main() {
string[] firstLine = Console.ReadLine().Split();
int n = int.Parse(firstLine[0]);
int q = int.Parse(firstLine[1]);
int[] nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int[] prefixProduct = new int[n + 1];
prefixProduct[0] = 1;
for (int i = 1; i <= n; i++) {
prefixProduct[i] = (int)((1L * prefixProduct[i - 1] * nums[i - 1]) % mod);
}
for (int i = 0; i < q; i++) {
string[] query = Console.ReadLine().Split();
int l = int.Parse(query[0]);
int r = int.Parse(query[1]);
int result = (int)((1L * prefixProduct[r + 1] * modInverse(prefixProduct[l]) % mod) % mod);
Console.WriteLine(result);
}
}
static int modInverse(int a) {
return power(a, mod - 2);
}
static int power(int x, int y) {
int res = 1;
while (y > 0) {
if ((y & 1) == 1) {
res = (int)((1L * res * x) % mod);
}
y >>= 1;
x = (int)((1L * x * x) % mod);
}
return res;
}
}
Conclusion
In this lecture, we learned how to effectively calculate the product over an array range by using the Prefix Product method and the concept of modular inverses. This method can be applied to handle more complex query processes as well. By utilizing the features of the C# language, efficient code can be written, further enhancing algorithm problem-solving skills.
Additionally, the Prefix Product technique used in this problem can be useful in various forms of query problems, so it is good to try applying it to different problems. Thank you!