牛客火柴排队(dp)

传送门

题目描述

输入描述:

一行两个整数 n,d

接下来一行 n 个整数

输出描述:

输出 n 行每行一个整数，第 i 行的整数表示 k=i 时的答案

输入

5 2
3 4 7 9 8

输出

199648871
898419918
898419918
199648871
1

说明

思路：

题目大意是给一段序列的1.....n项增加d时，序列的排序状态不变的概率。

我们先将序列排完序，由规模和每一项与前一项有关考虑dp，dp[i][j][0/1]代表序列截止到i项时使j项增加d排序不变的方案数，第三维0/1标志当前第i项增加或者不增加。

初始化dp[0][0[0]等于1

思考状态转移方程，如果第a[i]项不增加d的话，则方案数等于上一项增加d和不增加d的总取数为j相加，但这里需要判定上一项增加d不能影响到当前项的排序情况。

dp[i][j][0]等于dp[i-1][j][0]+dp[i-1][j][1]*(a[i-1]+d<=a[i]);

如果第a[i]项增加d的话，不需要考虑下一项，则方案数等于上一项总取数为j两种情形的方案相加

dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j][1];

得到满足的方案数后，我们需要知道对n项取i项增加d一共产生的方案数,即组合数作为分母。

这里公式=n!/(n-i)!*i!; 由费马小定理 $a^{φ (m)} \equiv 1 (\mod m)$

$a^{φ (m)} \equiv 1 (\mod m)$

那么输出的i项的结果即是(dp[n][i][0]+dp[n][i][1])*组合数的逆元。

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int mod=998244353;
typedef long long ll;
ll f[N],inv[N],fv[N];
ll dp[N][N][2];
int a[N];
int n,d;
ll qsm(ll a,ll b){
    ll ans=1ll;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(){///阶乘和阶乘逆元
    f[0]=1ll;
    for(int i=1;i<=5000;i++){
        f[i]=(1ll*i*f[i-1])%mod;
    }
    fv[5000]=qsm(f[5000],mod-2)%mod;
    fv[0]=1ll;
    for(int i=4999;i>=1;i--){///可通过最后一项递推所有逆元
        fv[i]=(fv[i+1]*(i+1)*1ll)%mod;
    }
}
ll c(int n,int m){///求组合数C n取m
    return f[n]*fv[n-m]%mod*fv[m]%mod;
}
int main(){
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    init();
    dp[0][0][0]=1ll;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
           dp[i][j][0]=dp[i-1][j][1]*(a[i-1]+d<=a[i])+dp[i-1][j][0];
           if(j){
                dp[i][j][1]=dp[i-1][j-1][0]+dp[i-1][j-1][1];
           }
           dp[i][j][0]%=mod,dp[i][j][1]%=mod;
        }
    }
    for(int i=1;i<=n;i++){
        ll s=(dp[n][i][0]+dp[n][i][1])%mod;
        cout<<(qsm(c(n,i),mod-2)*s)%mod<<endl;
    }
    return 0;
}