首先我们得意识到一个事实：假设当前已经播放过$x$种歌了，那么下一首新歌的概率都是$\frac{1}{n-x}$。

$n\leq 8$

我们直接$dfs$，每次爆搜新听到的歌是哪一首，顺便记一下概率是多少，一旦$\geq S$就把答案累计进去即可。

$n\leq 20,S\leq 100$

不知道我为什么设置了这么个范围。

$n\leq 20$

我们考虑$dp_{sta}$表示当前听到的歌构成了$sta$这个二进制状态的概率是多少。

转移的时候直接枚举下一首歌是谁即可。

dp[0]=1;
for (int sta=0;sta<(1<<n);sta++)
{
    ll x=popcount(sta); //x:sta二进制下1的个数
    if (sum[sta]>=S) continue; //sum[sta]:sta这个集合的和
    x=pw(n-x,mod-2); //每一个数字都是1/(n-x)的概率被选到。
    for (int i=0;i<n;i++)
        if (((sta>>i)&1)==0)
        {
            if (sum[sta]+a[i]<S) add(dp[sta|(1<<i)],dp[sta]*x);
            else add(ans[i],dp[sta]*x);
        }
}
for (int i=0;i<n;i++) cout<<ans[i]<<" "; cout<<endl;

$n\leq 100,S\leq 1000$

我们考虑这样一个事实：对于一个集合$10101$来说，它出现的概率根本不需要dp来计算，直接可以等价成这样一个数学模型：

你有$5$个元素需要排列，问前三个数字恰好是$135$或者$153,315,351,513,531$的概率是多少。

这个概率直接就是$\frac{3!}{A_5^3}$。（此处，$A_5^3$就是从$5$个元素里面，有序的取出$3$个元素的概率）。

也就是说：集合里$1$的元素个数相同，出现的概率就是相同的。

那么我们直接枚举结束时候听到的歌是谁（假设是$x$），然后把其余的歌拿出来。

$dp_{i,j,k}$表示考虑了前$i$首歌，当前一共选中了$j$首，它们的和是$k$的方案数有多少种。

这个是个经典$01$背包，时间复杂度$O(n^2S)$，空间复杂度可以优化到$O(nS)$，也就是我们直接用$dp_{j,k}$来算答案。

当计算完这个之后，$x$的答案就是：

$\sum_j\sum_{k<S,k+a[x]\geq S}dp_{j,k}\times \frac{j!}{A_n^{j+1}}$

由于对每一个$x$都要做一遍背包，复杂度是$O(n^3S)$。

ll dp[105][10005];
void add(ll &x,ll y) {x=((x+y)%mod+mod)%mod;}
void ins(int i)
{
    for (int j=n-1;j>=0;j--)
	for (int k=0;k<S-a[i];k++)
	{
		add(dp[j+1][k+a[i]],dp[j][k]);
	}
}
void work(int id)
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for (int i=1;i<=n;i++) if (i!=id) ins(i);
    //上面是在计算不含id的方案数
    
    ll ret=0;
    for (int j=0;j<=n-1;j++)
        for (int s=S-a[i];s<S;s++) //枚举合法的状态，算答案
        {
            //j!/A(n,j+1)
            //fac[j]:j!   inv[j]:1/A(n,j) 也就是A(n,j)^(n-2)%mod
            ll gai=dp[j][s]*fac[j]%mod*inv[j+1]%mod;
            add(ret,gai);
        }
	cout<<ret<<" ";
}
for (int i=1;i<=n;i++) work(i);

正解

我们在上述基础上考虑。

实际上那个dp，我们按任意顺序添加元素，最终的dp数组都是那个最终的数组。

那么我们考虑一下，能否把$ins(i)$的影响，在最终的dp数组里面拿掉呢？

我们来看看$ins(i)$干了个啥。

void ins(int i)
{
    for (int j=n-1;j>=0;j--)
	for (int k=0;k<S-a[i];k++)
	{
		add(dp[j+1][k+a[i]],dp[j][k]);
	}
}

这不就是顺着一行一行递推上去的吗？我们再倒着一行一行撤销回来不就可以了？

void del(int i)
{
	for (int j=0;j<=n-1;j++) //刚才从n-1到0,现在从0到n-1
	for (int k=0;k<S-a[i];k++)
	{
		add(dp[j+1][k+a[i]],-dp[j][k]);	
	}	
}

这样，对于每一个$x$，我们只需要$O(nS)$的速度就可以得到最终的dp数组，再通过$O(nS)$的速度还原回去即可。

复杂度$O(n^2S)$。

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
int n,S,a[maxn];
ll ni;
ll pw(ll x,ll mi)
{
	ll ret=1;
	while (mi)
	{
		if(mi&1) ret=ret*x%mod;
		x=x*x%mod; mi=mi>>1;
	}
	return ret;
}
void add(ll &x,ll y) {x=((x+y)%mod+mod)%mod;}
ll dp[105][10005]; //听了i首歌，共j的愉悦程度的方案数 

void del(int i)
{
	for (int j=0;j<=n-1;j++)
	for (int k=0;k<S-a[i];k++)
	{
		add(dp[j+1][k+a[i]],-dp[j][k]);	
	}	
}

void ins(int i)
{
	for (int j=n-1;j>=0;j--)
	for (int k=0;k<S-a[i];k++)
	{
		add(dp[j+1][k+a[i]],dp[j][k]);
	}
}

void init() 
{
	dp[0][0]=1;
	for (int i=1;i<=n;i++) ins(i);
}
ll fac[105],inv[105];
void work()
{
	for (int i=1;i<=n;i++)
	{
		del(i);
		ll ret=0;
		for (int j=0;j<=n-1;j++)
		for (int s=S-a[i];s<S;s++) //听了a[i]就超啦
		{
			//j!/A(n,j+1)
			ll gai=dp[j][s]*fac[j]%mod*inv[j+1]%mod;
			add(ret,gai);
		} 
		ins(i);
		cout<<ret<<" ";
	}
	cout<<endl;
}
 
int main()
{
	cin>>n>>S; 
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; //i!
	inv[0]=1;
	for (int i=1;i<=n;i++) inv[i]=inv[i-1]*(n-i+1)%mod; //A(n,i)
	for (int i=1;i<=n;i++) inv[i]=pw(inv[i],mod-2); //1/A(n,i)
	for (int i=1;i<=n;i++) cin>>a[i];
	init();
	work();
}