C++程序数组中范围乘积

问题描述

给定一个长度为n的整数数组nums和一个长度为m的查询二维数组queries。

每个queries[i][j]询问是给定数组nums在范围[queries[i][0], queries[i][1]]中所有数的乘积。

你需要返回一个数组answer，其中answer[i]是第i个查询的答案模303700049的结果。

1 <= nums.length <= 10^5
1 <= nums[i] <= 1000
1 <= queries[i][0] <= queries[i][1] < nums.length

本题采用数学优化方法实现，将数组分块，先预处理出第 $i$ 个块内元素的乘积，查询时通过块内元素乘积和块外元素乘积得到答案。

代码如下：

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 1000 + 10, mod = 303700049;

int n, m, w;
int nums[N], s[M];
LL sum[N];
int block[N], l[N], r[N], len;

LL qmi(LL a, LL b, LL c)   //快速幂
{
    LL res = 1 % c;
    while (b)
    {
        if (b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return res;
}

void init()
{
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        block[i] = (i - 1) / len + 1;
        if (block[i] != block[i - 1])
        {
            l[block[i]] = i;
            r[block[i - 1]] = i - 1;
        }
        sum[i] = (sum[i - 1] * nums[i]) % mod;
        sum[i] %= mod;
    }
    r[block[n]] = n;
}

LL calc(int l, int r)
{
    if (block[l] == block[r])
    {
        LL ans = 1;
        for (int i = l; i <= r; i++)
        {
            ans = ((ans % mod) * (nums[i] % mod)) % mod;
        }
        return ans;
    }
    LL ans = 1;
    int bl = block[l], br = block[r];
    for (int i = l; i <= r && block[i] == bl; i++)
    {
        ans = ((ans % mod) * (nums[i] % mod)) % mod;
    }
    for (int i = bl + 1; i <= br - 1; i++)
    {
        ans = ((ans % mod) * (s[i] % mod)) % mod;
    }
    for (int i = r; i >= l && block[i] == br; i--)
    {
        ans = ((ans % mod) * (nums[i] % mod)) % mod;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
    }
    init();
    for (int i = 1; i <= block[n]; i++)
    {
        int l = r[i - 1] + 1, r = l + len - 1;
        if (r > n) r = n;
        s[i] = calc(l, r);
    }
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        LL x = calc(l, r);
        LL ans;
        if (l > len)
        {
            ans = sum[l - 1] * qmi(sum[r], mod - 2, mod) % mod;
        }
        else if (r <= len)
        {
            ans = sum[r] * qmi(sum[l - 1], mod - 2, mod) % mod;
        }
        else
        {
            ans = sum[len] * qmi(sum[l - 1], mod - 2, mod) % mod * qmi(sum[r], mod - 2, mod) % mod;
        }
        ans = (ans % mod) * (x % mod) % mod;
        cout << ans << endl;
    }
    return 0;
}

算法思路

对于本问题，我们可以采取数学优化的方法，在预处理中将数组分块，分别预处理出每个块内的元素乘积。此后，在查询时，我们可以通过每个块内的元素乘积和块外元素乘积的乘积得到范围乘积的答案。数学原理如下：

设查询区间为[l，r]，则范围乘积为x = nums[l] * nums[l + 1] * ... * nums[r]，显然，x除去[l, r]内部的数，剩下的数即为[l, r]外部的数。

所以，我们可以分为以下几种不同的情况：

全部在块内：暴力做即可。
全部在块外：

记s1=l，s2=r，块的大小为len，则[l, s1 – 1]和[s2 + 1, r]的所有元素乘积可以通过前缀乘积“预处理出来”。然后，根据除法取余的缩放公式（逆元）可以通过前缀乘积来判断[l, s1 – 1]和[s2 + 1, r]内的元素乘积。
一部分在块内，一部分在块外：

知道了如何处理情况1和2，我们就可以处理这种情况了。具体来说，先通过前缀乘积把中间部分的乘积O(1)计算得到，然后对左右两部分套用上述方法即可。

代码说明

定义变量：

“`c++
int n, m, w; // n是数组元素个数，m是查询个数，w是区间大小
int nums[N], s[M]; // 数组nums表示原数组，s表示块的所有数的乘积
LL sum[N]; // 用来存储前缀积的数组
int block[N], l[N], r[N], len; // block存储每个元素属于哪个块，l和r则分别存储每个块的左右端点，len是每个块的大小

关于块的大小`len`的设定，可以通过计算得到。可以先设定`len=100`，如果100长度的块有10个以上（即元素个数大于等于1000）则减小`len`的大小，否则增大`len`的大小。

接下来是数据预处理，包括块的处理和求前缀积：

```cpp
void init()
{
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        block[i] = (i - 1) / len + 1;
        if (block[i] != block[i - 1])
        {
            l[block[i]] = i;
            r[block[i - 1]] = i - 1;
        }
        sum[i] = (sum[i - 1] * nums[i]) % mod;  // 求前缀积
        sum[i] %= mod;  // 取余
    }
    r[block[n]] = n;
}

然后再通过暴力枚举每个块内元素的乘积来求出块s中所有元素的乘积：

for (int i = 1; i <= block[n]; i++)
{
    int l = r[i - 1] + 1, r = l + len - 1;
    if (r > n) r = n;
    s[i] = calc(l, r);
}

最后再来处理查询：

while (m--)
{
    int l, r;
    cin >> l >> r;
    LL x = calc(l, r);  // 得到当前查询区间[l, r]内的元素乘积
    LL ans;
    if (l > len)
    {
        ans = sum[l - 1] * qmi(sum[r], mod - 2, mod) % mod;
    }
    else if (r <= len)
    {
        ans = sum[r] * qmi(sum[l - 1], mod - 2, mod) % mod;
    }
    else
    {
        ans = sum[len] * qmi(sum[l - 1], mod - 2, mod) % mod * qmi(sum[r], mod - 2, mod) % mod;
    }
    ans = (ans % mod) * (x % mod) % mod;
    cout << ans << endl;
}

其中，calc函数用于计算当前查询区间[l, r]中的所有元素的乘积。使用逆元求解带模的除法取余。

LL qmi(LL a, LL b, LL c)   //快速幂
{
    LL res = 1 % c;
    while (b)
    {
        if (b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return res;
}

LL calc(int l, int r)
{
    if (block[l] == block[r])
    {
        LL ans = 1;
        for (int i = l; i <= r; i++)
        {
            ans = ((ans % mod) * (nums[i] % mod)) % mod;
        }
        return ans;
    }
    LL ans = 1;
    int bl = block[l], br = block[r];
    for (int i = l; i <= r && block[i] == bl; i++)
    {
        ans = ((ans % mod) * (nums[i] % mod)) % mod;
    }
    for (int i = bl + 1; i <= br - 1; i++)
    {
        ans = ((ans % mod) * (s[i] % mod)) % mod;
    }
    for (int i = r; i >= l && block[i] == br; i--)
    {
        ans = ((ans % mod) * (nums[i] % mod)) % mod;
    }
    return ans;
}