题解 | #子数列求积#

算法：前缀积与逆元

鉴于序列是静态的，前缀和思想的变体——前缀积是解决该问题的最优范式。

核心逻辑

定义前缀积数组 表示从 到 的乘积。 理论上，区间 的乘积可以表示为： 在模 意义下转化为：

零值处理

为了解决 导致的“信息坍缩”和“不可逆”问题，我们需要引入双层数据结构：

1. 非零前缀积数组 (NonZeroPre)： 计算前缀积时，遇到 则视为 进行累乘。这保留了所有非零元素的乘积信息。
2. 零计数前缀和数组 (ZeroCnt)： 记录前缀区间内 的出现次数。

查询逻辑

对于查询 ：

1. 首先利用 ZeroCnt 检查区间 内是否存在 。
2. 若存在 ，直接返回 。
3. 若不存在 ，使用 NonZeroPre 结合模逆元计算结果。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

ll power(ll a, ll b) {
    ll res = 1LL;
    a %= MOD;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}

ll modInv(ll x) {
    if (x % MOD == 0)
        return -1;
    return power(x, MOD - 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<ll> NonZeroPre(n + 1, 0);
    vector<int> ZeroCnt(n + 1, 0);

    NonZeroPre[0] = 1LL;
    for (int i = 1; i <= n; i++) {
        if (a[i - 1] == 0) {
            ZeroCnt[i] = ZeroCnt[i - 1] + 1;
            NonZeroPre[i] = NonZeroPre[i - 1];
        } else {
            ZeroCnt[i] = ZeroCnt[i - 1];
            NonZeroPre[i] = (NonZeroPre[i - 1] * a[i - 1]) % MOD;
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        int cnt = ZeroCnt[r] - ZeroCnt[l - 1];
        if (cnt > 0) {
            cout << "0 ";
            continue;
        }

        ll inv_val = modInv(NonZeroPre[l - 1]);
        ll res = (NonZeroPre[r] * inv_val) % MOD;
        cout << res << " ";
    }

    cout << "\n";
}