题解 | 子数列求积

题目是离线区间查询，想到使用前缀和比较合适。对于区间[l,r]的所有ai乘积，若暂不考虑取模，它的值应该等于区间[1,r]的所有ai乘积除以[1,l-1]的所有ai乘积即pre[r]/pre[l-1]。故预处理pre[i]表示前i个数相乘并模1E9+7的值。由于此题需要对1E9+7取模，因此查询时的除法应使用逆元来计算，可以使用快速幂求逆元。

#include <iostream>
#include <vector>

constexpr int P = 1E9+7;

int quickPower(int a,int b){
  int res = 1;
  for(; b; a=1LL*a*a%P,b>>=1){
    if(b & 1){
      res = 1LL*res*a%P;
    }
  }
  return res;
}

int inv(int a){
  return quickPower(a,P-2);
}

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

  int n,q;
  std::cin >> n >> q;

  std::vector<int> a(n+1);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i];
  }

  std::vector<int> pre(n+1);
  pre[0] = 1;
  for(int i = 1; i <= n; i++){
    pre[i] = 1LL*pre[i-1]*a[i]%P;
  }

  for(int qi = 0; qi < q; qi++){
    int l,r;
    std::cin >> l >> r;

    std::cout << 1LL*pre[r]*inv(pre[l-1])%P << " \n"[qi+1==q];
  }
}