実数 \(t\) について、時刻 \(0\) から \(t\) 秒後の時刻を時刻 \(t\) とします。

各非負整数. \(t=0,1,\ldots, X\) について、時刻 \(t\) に曲が切り替わる(新しく曲が選ばれ再生され始める)確率を \(p[t]\) とします。

時刻 \((X+0.5)\) にプレイリストの \(1\) 番目の曲が再生されている事象のうち、その曲が再生され始めた時刻が時刻 \(X, (X-1),\ldots, (X-T_1+1)\) である事象は互いに排反であり、また、各事象はこれらのうちどれか \(1\) つをみたします。よって、各 \(t=X, (X-1),\ldots, (X-T_1+1)\) について、「時刻 \(t\) に \(1\) 番目の曲が再生され始めた確率」を足し合わせれば良いことがわかります。(該当時刻に \(1\) 番目の曲が再生され始めた場合、必ず時刻 \((X+0.5)\) にその曲が流れている事に注意してください。)全ての曲が等確率で選ばれることから、時刻 \(t\) に \(1\) 番目の曲が再生され始めた確率は、(時刻 \(t\) に \(1\) 番目の曲が再生され始めた確率)\(\times\frac{1}{N}\) となります。

よって、答えは、\(T_1\leq X+1\) ならば、

\[ \frac{1}{N}(p[X-T_1+1]+p[X-T_1+2]+\cdots+p[X]), \]

\(X\leq T_1\) ならば

\[ \frac{1}{N}(p[0]+p[X-T_1+2]+\cdots+p[X]) \]

となります。

よって、各 \(p[i]\) を求めれば良いです。 これは動的計画法によって求めることができます。 まず、\(p[0]=1\) です。\(t\geq 1\) について、時刻 \(t\) の直前まで再生され始めていた曲によって分類することで、\(p[t]\) は、 \(k=1,2,\ldots,N\) について、「ちょうど時刻 \(t-T_k\) に\(k\) 番目の曲が再生され始めた確率」の和として求めることができることがわかります。先と同じ議論からこの確率は \(t-T_k<0\) ならば \(0\), \(t-T_k\geq 0\) ならば \(\frac{1}{N}p[t-T_k]\) となります。よって、便宜上 \(t<0\) に対して \(p[t]=0\) とすれば、 \(p[t]=\frac{1}{N}(p[t-T_1]+p[t-T_2]+\cdots+p[t-T_N])\) として求めることができます。

各 \(t\) に対する \(p[t]\) の計算に \(O(N)\) なので \(t=1,2,\ldots,X\) に対して全体で \(O(NX)\), そこから答えの計算に \(O(\min(T_1,X))\) なので、全体で \(O(NX)\) であり、十分高速にこの問題を解くことができました。modint 等を用いる場合は、法とする整数を \(P\) (今回は\(P=998244353\)) として \(\frac{1}{N}\) をかける操作に \(O(\log P)\) かかるので更新のたびに毎回行うと定数倍が重くなる事に注意してください。

c++ による実装例:

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main(void) {
	int n,x;
	mint r,ans;
	
	cin>>n>>x;
	vector<int>t(n);
	for(int i=0;i<n;i++)cin>>t[i];

	vector<mint>p(x+1);
	r=((mint)1)/((mint)n);
	p[0]=1;
	if(t[0]>x)ans+=p[0]/((mint)n);
	for(int i=1;i<=x;i++){
		for(int j=0;j<n;j++)if(t[j]<=i)p[i]+=p[i-t[j]];
		p[i]*=r;
		if(i+t[0]>x)ans+=p[i]*r;
	}

	cout<<ans.val()<<endl;
	return 0;
}