C++(clang++ 11.0.1) 解法, 执行用时: 640ms, 内存消耗: 512K, 提交时间: 2023-08-02 22:08:21

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=1e3+10,mod=9999991;
int y[N];
int pre[N],suf[N],inv[N];
int qz(int x,int y){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
void init(int n){
	int i;
	inv[0]=1;
	For(i,1,n) inv[i]=inv[i-1]*qz(i,mod-2)%mod;
}
int calc(int x,int n){
	int i,res=0;
	pre[0]=x;
	For(i,1,n) pre[i]=pre[i-1]*(x-i)%mod;
	suf[n+1]=1;
	FOR(i,n,0) suf[i]=suf[i+1]*(x-i)%mod;
	For(i,0,n){
		int temp=y[i];
		if(i) temp=temp*pre[i-1]%mod;
		temp=temp*suf[i+1]%mod;
		temp=temp*inv[i]%mod;
		temp=temp*inv[n-i]%mod;
		if((n-i)%2) temp=-temp;
		temp%=mod;
		temp=(temp+mod)%mod;
		res=(res+temp)%mod;
	}
	return res;
}
signed main(){
	int t,n,m,i;
	init(1e3+1);
	cin>>t;
	while(t--){
		cin>>n>>m;
		For(i,0,n) cin>>y[i];
		y[n+1]=calc(n+1,n);
		For(i,1,n+1) y[i]=(y[i]+y[i-1])%mod;
		while(m--){
			int l,r;
			cin>>l>>r;
			int ans=(calc(r,n+1)-calc(l-1,n+1))%mod;
			ans=(ans+mod)%mod;
			cout<<ans<<'\n';
		}
	}
	return 0;
}