考虑第 \(i\) 时刻时，第 \(j\) 首歌刚好结束与第 \(i-j\) 时刻有关，因此设 \(dp_{i,j}\) 表示第 \(i\) 时刻第 \(j\) 首歌刚好结束的概率，那么 \(dp\) 转移方程为：
\[dp_{i,j}=\sum\limits_{k=1}^n dp_{i-t_j,k} \]很容易想到记录 \(\sum\limits_{j=1}^n dp_{i,j}\) 的值为 \(sum_i\)，这样转移时间就只有 \(O(1)\) 了。
答案为 \(\frac{\sum\limits_{i=x+1}^{x+t_1}dp_{i,1}}{n}\)，也就是 \(\frac{\sum\limits_{i=x+1-t_1}^x sum_i}{n}\)。时间复杂度 \(O(nx)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=998244353;
ll qpow(ll x,int y){
ll re=1;
while(y){
if(y&1) re=re*x%p;
x=x*x%p;
y>>=1;
}return re;
}int n,t[1005],x;
ll sum[10005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>t[i];
ll zjy=qpow(n,p-2),ans=0;
if(!x){
cout<<zjy;
return 0;
}sum[0]=1;
for(int i=1;i<=x;i++)
for(int j=1;j<=n;j++)
if(i>=t[j])
sum[i]=(sum[i]+sum[i-t[j]]*zjy%p)%p;
for(int i=x+1-t[1];i<=x;i++)
ans=(ans+sum[i]*zjy%p)%p;
cout<<ans;
return 0;
}