杭电多校第五场 1008 Set2 题解

题目大意

有一个大小为n的集合，${1,…,n}$，你需要每次删除其中最小的那个元素，以及另外随机删除k个元素，求每个元素的剩下来的概率。

解题思路

本来应该是先写Set1的，但是Set2的dp思路可以适合Set1，就先写Set2了。

看了官方的题解，看了半天看不懂，太长了。

百度到了一个大佬的博客，代码很简单。

但是这个思路很难理解，太难想了。

设$ans[i]$为倒数第i个数的存活概率。

首先求出剩余多少个数，$last=n%(k+1)$。

把剩下的个数的存活概率初始化为1。

然后将过程倒过来，每次加一个人，然后如果这个人不是必须要被删除的，就可以更新状态。

如果这个数及右边的数被$(k+1)$取余后剩余1，则说明这个数是会被作为最小的那个数删除的。

如果不是必须删除的，则从大到小更新状态。

如果删除的是第i个数之后的数，则对$ans[i]$无影响，继承$ans[i]$。

如果删除的是第i个数之前的数，则相当于是让i向前移动了一位，继承$ans[i-1]$。

在继承的时候乘上概率即可。

需要初始化inv数组。

这个dp让我自己想，估计一辈子想不出来。。

看题解就看了好久。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;

const int mod = 998244353, maxn = 5050;
ll inv[maxn], ans[maxn];

ll qpow(ll a, int b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a % mod) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for (ll i = 1; i <= 5000; i++) inv[i] = qpow(i, mod - 2);
	while (t--) {
		int n, k;
		cin >> n >> k;
		int last = n % (k + 1);
		for (int i = 1; i <= last; i++)	ans[i] = 1;
		for (int i = last + 1; i <= n; i++) {
			ans[i] = 0;
			if ((n - i + 1) % (k + 1) == 1)	continue;
			for (int j = i; j >= 1; j--) {
				ans[j] = (ans[j] * (i - j)%mod * inv[i]%mod + ans[j - 1] * (j - 1)%mod * inv[i]%mod) % mod;
			}
		}
		for (int i = n; i >= 1; i--)	printf("%lld%c", ans[i], i == 1 ? '\n' : ' ');
	}
}