题解 | 子数列求积

#include <iostream>


using namespace std;


const int M = 1e9 + 7;

const int N = 1e5 + 10;

long long tree[N];
int a[N];
int n,q;


long long qpow(long long x,int y){
    long long res = 1 % M;
    while(y){
        if((y & 1) == 1){
            res = res * x % M;
        }
        y = y >> 1;
        x = (long long)x * x % M;
    }
    return res;
}

void init(){
    for(int i = 1;i <= n;i++){
        tree[i] = 1;
    }
}

int lowbit(int i){
    return i & -i;
}

void update(int i,long long val){
    while(i <= n){
        tree[i] = tree[i] * val % M;
        i += lowbit(i);
    }
}

long long query(int i){
    long long res = 1;
    while(i > 0){
        res = res * tree[i] % M;
        i -= lowbit(i);
    }
    return res;
}

long long inv(int num){
    return qpow(num,M - 2);
}


int range_query(int l,int r){

    return query(r) * inv(query(l - 1)) % M; 

}


int main(){

    cin>>n>>q;

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

    init();

    for(int i = 1;i <= n;i++){
        update(i,a[i]);
    }

    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<range_query(l,r)<<" ";
    }

    return 0;
}