牛客7329D - 火柴排队

• 链接：https://ac.nowcoder.com/acm/contest/7329/D
• 知识点：概率、古典概型、组合计数、分组背包DP
• 难度：紫

题意

• 给出一个长度为 $nn$ 的序列，序列中的数字两两不同。
• 现在随机从中选择 $kk$ 个元素，将它们的数值 $+d+d$。
• 设原序列为 $a_{i}a\_i$，新序列为 $a_i^{\mathrm{\prime }}a\_i\text{'}$，求 并且 的概率。
• 需要对于每个 $k\in [1,n]k\backslash in\; [1,n]$ 求出它对应的答案。

思路

• 什么情况下满足 并且 ？
  • 仅 $a_j+da\_j+d$
  • $a_{i}a\_i$ 和 $a_{j}a\_j$ 都 $+d+d$
  • 仅$a_i+da\_i+d$，但是 $a_j-a_i\ge da\_j-a\_i\backslash geq\; d$
• 我们发现，如果将这些元素升序排序，再按照相邻两元素差值 $\le d\backslash leq\; d$ 合成数条链，
• 那么上面提到的前两种情况就是 在同一条链中取最大的连续的几个元素。
• 第三种情况就是 取的这两个元素不在同一条链中。
• 也就是对于每一条链，要么不取，要么取最大的几个。这是满足条件的情况。$ans=\frac{\mathrm{满}\mathrm{足}\mathrm{条}\mathrm{件}\mathrm{的}\mathrm{情}\mathrm{况}\mathrm{数}}{\mathrm{总}\mathrm{情}\mathrm{况}\mathrm{数}}ans=\backslash frac\{满足条件的情况数\}\{总情况数\}$
• 可以用分组背包计算随机取 $ii$ 个元素的满足条件的情况数。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define int long long
const int N		= 1e6+10;
const int MOD	= 998244353;
using namespace std;

int arr[N];
int rt[N],sz[N];
int dp[2][N];
int n,D;

long long bin[N];

void Init()
{
	bin[0]=1; 
	bin[1]=1;
	for(int i=2;i<N;i++)
		bin[i]=i*bin[i-1]%MOD;
	for (int i=1; i<N; i++)
	{
		rt[i] = i;
		sz[i] = 1;
	}
}

long long POW(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1)
		{
			res*=a, res%=MOD;
		}
		b>>=1;
		a*=a, a%=MOD;
	}
	return res;
}

int Div(int a,int b)
{
	return a * POW(b, MOD-2) % MOD;
}


long long C(long long n, long long m)
{
	return (bin[n]%MOD)*(POW(bin[m]*bin[n-m]%MOD,MOD-2))%MOD;
}

int Find(int x)
{
	if(rt[x]==x)return x;
	else return rt[x] = Find(rt[x]);
}

void Merge(int u,int v)
{
	u = Find(u);
	v = Find(v);
	rt[u] = rt[v];
	sz[v] += sz[u];
}

void Solve()
{
	sort(arr+1, arr+1+n);
	for (int i=2; i<=n; i++)
	{
		if(arr[i] - arr[i-1] <= D)
		{
			Merge(i, i-1);
		}
	}
	
	int cur = 1;
	dp[cur][0] = 1;
	for (int i=1; i<=n; i++)
	{
		if(Find(i)!=i)continue;
		
		cur ^= 1;
		memset(dp[cur], 0, n*sizeof(int));
		
		for (int j=n; j>=0; j--)
		{
			for (int k=0; k<=sz[i] && j>=k; k++)
			{
				dp[cur][j] += dp[cur^1][ j-k ], dp[cur][j]%=MOD;
			}
		}
	}
	
	for (int i=1; i<=n; i++)
	{
		printf("%lld\n",Div(dp[cur][i], C(n,i)));
	}
	
}

signed main()
{
	Init();
	
	scanf("%lld %lld",&n,&D);
	for (int i=1; i<=n; i++)
	{
		scanf("%lld",&arr[i]);
	}
	Solve();
	
	return 0;
}