链接
https://ac.nowcoder.com/acm/contest/7329/D
题意
长度为 $n$ 序列 $a$ 中找出 $k$ 个数加 $d$，使新序列中如果 $a’_i>a’_j$，那么原序列也 $a_i>a_j$ 的概率。
对于每个 $1\le k\le n$，你都要输出其对应的答案，答案模 $998244353$。
思路
等价于一个单调上升的序列选 $k$ 个数加 $d$ 后仍单调上升的概率。
记 $dp[i][j][0/1]$ 为前 $i$ 个数选了 $j$ 个数加上 $d$ 且当前数是否选择，满足题意的方案数：
边界：$dp[1][0][0]=dp[1][1][1]=1$
状态转移方程：
$\begin{cases}
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]*(a[i-1]+d>a[i])\
dp[i][j][1]=dp[i-1][j-1][0]+dp[i-1][j-1][1]
\end{cases}$
$j$ 从 $0$ 开始。
$\frac{dp[n][k][0]+dp[n][k][1]}{\binom{n}{k}}$ 就是答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=5005;
const LL MOD=998244353;
int n,d,a[N];
LL fac[N],invf[N],dp[2][N][2];
LL fpow(LL a,LL b) {
LL ret=1;
while(b) {
if(b&1) ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int main() {
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
dp[1][1][1]=dp[1][0][0]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=i;j++) {
dp[i&1][j][0]=(dp[(i-1)&1][j][0]+dp[(i-1)&1][j][1]*(a[i-1]+d<=a[i]))%MOD;
if(j>=1) dp[i&1][j][1]=(dp[(i-1)&1][j-1][0]+dp[(i-1)&1][j-1][1])%MOD;
}
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
invf[n]=fpow(fac[n],MOD-2);
for(int i=n-1;i>=1;i--) invf[i]=invf[i+1]*(i+1)%MOD;
for(int i=1;i<=n;i++) printf("%lld\n",(dp[n&1][i][0]+dp[n&1][i][1])%MOD*fac[i]%MOD*fac[n-i]%MOD*invf[n]%MOD);
return 0;
}
|