CF1418E Expected Damage

一道比较反套路的题。
一般我们看到求期望都是直接去数数，然后DP一下之类的。但这道题是真的让你用概率的方法去算期望，还是蛮有意思的。

先把权值不小于$b_i$的怪兽称为大怪兽，其他的称之为小怪兽。显然只有护盾被$a_i$个大怪兽撞了之后才能对自己造成伤害。也就是说，在$[a_i+1,cnt(大怪兽)]$这个范围内的大怪兽能造成有效伤害。所以一个大怪兽造成伤害的概率就是$1-\frac{a_i}{cnt(大怪兽)}$。

接着来考虑小怪兽，因为小怪兽之间互不干扰，所以一个小怪兽能造成伤害的概率就是$1-\frac{a_i}{cnt(大怪兽)+1}$。然后根据期望的线性性质把他们加起来即可。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2e5+100;
const int mod=998244353;
int d[maxn];
ll pre[maxn];
int ksm(int num,int t){
	int res=1;
	for(;t;t>>=1,num=1ll*num*num%mod){
		if(t&1)res=1ll*res*num%mod;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	int n,m;cin>>n>>m;
	rep(i,1,n)cin>>d[i];
	
	sort(d+1,d+1+n);
	rep(i,1,n)pre[i]=(pre[i-1]+d[i])%mod;
	rep(i,1,m){
		int a,b;cin>>a>>b;
		int sm=lower_bound(d+1,d+1+n,b)-1-d;
		int bg=n-sm;
		if(bg<a){cout<<"0"<<endl;continue;}
		ll ans=(1-1ll*a*ksm(bg,mod-2)%mod)*(pre[n]-pre[sm])%mod+
				(1-1ll*a*ksm(bg+1,mod-2)%mod)*pre[sm]%mod;
		ans=(ans%mod+mod)%mod;
		cout<<ans<<endl;
	}
}