杭电多校第五场 1012 Set1 题解

题目大意

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

解题思路

这题和Set2差不多，Set2代码可以求出这个题目的正解，但是会T。

然后这题就是找规律。

（不知道那些人怎么找出来的。。

显然，前$\large \frac{n}{2}$个数都是0。

可以用Set2的代码跑案例，得出规律。

当n等于7的时候，跑出来是$\large \frac{4}{2},\frac{5}{4}$。

分母加二，分子加一。

$\large dp[\frac{n+1}{2}]=\frac{1}{2^{\frac{n}{2}}} $。

$\large dp[i+1]=dp[i]\times \frac{\frac{n}{2}+i}{2i}\ (1\leq i<n-1)$。

$\large dp[n]=dp[n-1]$。

按照这个规律写代码即可。

完整代码

#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 <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 998244353;

ll qpow(ll a, ll 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;
	while (t--) {
		int n; cin >> n;
		if (n == 1) {
			cout << 1 << endl;
			continue;
		}
		for (int i = 1; i <= n / 2; i++)	cout << "0 ";
		ll ans = qpow(qpow(2, n / 2), mod - 2);
		cout << ans << ' ';
		for (int i = 1; i < n / 2; i++) {
			ans = ans * (n / 2 + i) % mod * qpow(2 * i, mod - 2) % mod;
			cout << ans << ' ';
		}
		cout << ans << endl;
	}
	return 0;
}