牛客练习赛60D 火柴排队（dp）

根据数据范围我们可以猜出是n^2的算法，其实可以看的出就是dp统计合法方案，但是本身这个序列不满足条件，因此要进行排序后再进行dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,pll> plll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
const ll mod=998244353;
ll n,d;
ll a[N];
ll f[5050][5050][2];
ll F[N];
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void init(int n){
    F[0]=1;
    for (int i=1;i<=n;i++){
        F[i] = (1ll * F[i-1] * i) % mod;
    }
}
ll C(int n,int k){
    ll x = F[n];
    ll y = (F[k] * F[n-k]) % mod;
    return (x*qmi(y,mod-2)) % mod;
}
bool cmp(ll x,ll y){
    return x>y;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>d;
    int i;
    init(5050);
    for(i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n,cmp);
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++){
            f[i][j][0]+=f[i-1][j][0]+f[i-1][j][1];
            f[i][j][0]%=mod;
            f[i][j][1]+=f[i-1][j-1][1];
            if(a[i]+d <= a[i-1] || i==1)
                f[i][j][1]+=f[i-1][j-1][0];
            f[i][j][1]%=mod;
        }
    for (int i=1;i<=n; ++ i) {
        cout<<((f[n][i][1] + f[n][i][0]) % mod * qmi(C(n, i), mod-2))%mod<<endl;
    }
    return 0;
}