C++14(g++5.4) 解法, 执行用时: 52ms, 内存消耗: 648K, 提交时间: 2020-09-12 00:16:41

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=5e3+5,mod=998244353;
int n,d,a[M];
ll dp[2][M],fac[M],inv[M];
int main()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)inv[i]=inv[i-1]*inv[i]%mod;
    int now=0;
    dp[0][0]=1;
    for(int l=1,r;l<=n;l=r+1)
    {
        now^=1;
        for(int i=0;i<=n;i++)dp[now][i]=dp[now^1][i];
        r=l;
        while(r<n&&a[r+1]<=a[r]+d)r++;
        for(int i=l;i<=r;i++)
            for(int j=r-i+1;j<=n;j++)
                dp[now][j]=(dp[now][j]+dp[now^1][j-r+i-1])%mod;
    }
    for(int i=1;i<=n;i++)printf("%lld\n",dp[now][i]*fac[i]%mod*fac[n-i]%mod*inv[n]%mod);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 67648K, 提交时间: 2020-09-11 19:33:16

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,d;
int a[5050],f[5050],g[5050],C[5050][5050];
inline int qpow(int x,int k,int r=1){
	for(;k;k>>=1,x=1ll*x*x%mod) if(k&1) r=1ll*r*x%mod;
	return r;
}
int main(){
	cin>>n>>d;
	for(int i=1;i<=n;++i) cin>>a[i];
	sort(a+1,a+n+1); a[n+1]=(int)2e9+1; f[0]=1;
	for(int l=1,r=l;l<=n;l=++r){
		while(a[r]+d>=a[r+1]) ++r;
		memset(g,0,sizeof(g));
		for(int j=0;j<=n;++j){
			for(int k=0;k<=r-l+1;++k){
				(g[j+k]+=f[j])%=mod;
			}
		}
		memcpy(f,g,sizeof(f));
	}
	for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(int i=1;i<=n;++i) printf("%d\n",1ll*f[i]*qpow(C[n][i],mod-2)%mod);
	return 0;
}