题解 | 子数列求积

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

typedef long long ll;

const ll p = 1000000007;

ll fast_pow_mod(ll base, ll exp, ll p) {
	if (base == 0) return 0;
	else if (exp == 0 || base == 1) return 1;
	
	ll result = 1;
	while (exp > 0) {
		if (exp & 1) {
			result = (result * base) % p;  
		}
		base = (base * base) % p;
		exp >>= 1;
	}
	return result;	
} 
//类似于前缀和
int main() {
	int n, q;
	cin >> n >> q;
	ll a[n + 1], tmp;
	a[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> tmp;
		a[i] = (a[i - 1] * tmp) % p; 
	}
	int left, right;
	while (q-- > 0) {
		cin >> left >> right;
		//a[right] * (a[left] ^ -1)同余 
		ll base = a[right] % p;
		ll inverse = fast_pow_mod(a[left - 1], p - 2, p);
		cout << (base * inverse) % p << " ";
	}
}