【2020年杭电暑假第五场】6825 Set1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6825

题意

You are given a set S={1..n}. It guarantees that n is odd. You have to do the following operations until there is only 1 element in the set:

Firstly, delete the smallest element of S. Then randomly delete another element from S.

For each i∈[1,n], determine the probability of i being left in the S.

It can be shown that the answers can be represented by PQ, where P and Q are coprime integers, and print the value of P×Q−1 mod 998244353.

Input The first line containing the only integer T(T∈[1,40]) denoting the number of test cases.

For each test case:

The first line contains a integer n .

It guarantees that: ∑n∈[1,5×106].

Output For each test case, you should output n integers, i-th of them means the probability of i being left in the S.

Sample Input 1 3

Sample Output 0 499122177 499122177

给出一个$n$,有$[1,n]$中$n$个数。 每次有如下操作:先删去最小的元素,再随机删掉一个元素。 求每个数留下来的概率期望。

思路

方法一:组合数学+数学推导

考虑元素$i$留下来的方案数,那么他前面有$i-1$个数,后面有$n-i$个数。 我们易得当$n-i\geq i-1$时,i才会被留下来,即$i\leq\frac{n}{2}$时都是$0$,往后才有值。所以我们可以直接输出前$\frac{n}{2}$个$0$。

然后在处理后面的数字。 我们设每次删除最小元素为操作一,随机删除元素为操作二。 即$i$后面的$n-i$个数一定是操作二删除的,所以第一步,我们让后面$n-i$个数与前面$i-1$中的$n-i$个一一对应删除就行。(在$i-1$中选$n-i$个数出来在给他排序) 设第$i$个数被留下来的方案数为$cnt[i]$,则 $$cnt[i] = C_{i-1}^{n-i}*A_{n-i}^{n-i} = \frac{(i-1)!}{(2i-n-1)!}$$

然后在考虑剩下的$(i-1)-(n-i)=(2i-n-1)$个数,根据前面,在其中选择两两删除。 $(2i-n-1)$两两选择有$$C_{2i-n-1}^2*C_{2i-n-3}^2…C_4^2*C_2^2$$ $$\frac{(2i-n-1)!}{2!*(2i-n-3)!}*\frac{(2i-n-3)!}{2!*(2i-n-5)!}*…*\frac{2!}{2!*0!}$$ $$\frac{(2i-n-1)!}{(2!)^{\frac{2i-n-1}{2}}}$$

到这里还没有结束,然后我想了好久,是我太捞了。 比如$[1,6]$,我们选择的时候会重复选择多次,比如 $(1,2)(3,4)(5,6)$ $(1,2)(5,6)(3,4)$ $(3,4)(1,2)(5,6)$ $(3,4)(5,6)(1,2)$ $(5,6)(1,2)(3,4)$ $(5,6)(3,4)(1,2)$ 这些都是上面包括的情况,因为选的先后次序不同,所以会出现重复的情况,一共出现相同的组合$(\frac{n}{2})!$,所以我们要在上面的基础上再除以$(\frac{2i-n-1}{2})!$ 那么剩下数$(2i-n-1)$中两两选择的方案数为 $$\frac{(2i-n-1)!}{(2!)^{\frac{2i-n-1}{2}}*(\frac{2i-n-1}{2})!}$$ 最后整合上述所有情况,第$i$个数被留下的总方案数为 $$cnt[i] = \frac{(i-1)!}{(2i-n-1)!}*\frac{(2i-n-1)!}{(2!)^{\frac{2i-n-1}{2}}*(\frac{2i-n-1}{2})!}$$ 化简得 $$cnt[i] = \frac{(i-1)!}{(2!)^{\frac{2i-n-1}{2}}*(\frac{2i-n-1}{2})!}$$

总方案数为$sum=\sum_{i=1}^ncnt[i]$ 第$i$个数被留下的概率期望为$p[[i]=\frac{cnt[i]}{sum}$ 时间复杂度为$O(n)$

事先预处理所有的阶乘和阶乘逆元。

方法二:dp

参考:https://www.cnblogs.com/luyouqi233/p/13434815.html dp方法我也不太会,哭了。

Code(3026MS)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const ll mod = 998244353;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

const int N = 5e6 + 5;

ll F[N];
ll invn[N];
ll invF[N];
ll cnt[N];

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

void Init()
{
F[0] = F[1] = invn[0] = invn[1] = invF[0] = invF[1] = 1;
for(int i = 2;i < N; i++){
F[i] = F[i - 1] * i % mod;
invn[i] = (mod - mod / i) * invn[mod % i] % mod;
invF[i] = invF[i - 1] * invn[i] % mod;
}
}

void solve() {

Init();

int T;
scanf("%d",&T);

ll inv2 = 499122177;

while(T--)
{
int n;
scanf("%d",&n);
if(n == 1) printf("1\n");
else{
printf("0");
for(int i = 2;i <= n / 2; i++)
printf(" 0");

ll ans = 0;

for(int i = n / 2 + 1;i <= n; i++) {
cnt[i] = F[i - 1] * invF[(2 * i - n - 1) / 2] % mod * quick_pow(inv2, (2 * i - n - 1) / 2) % mod;
ans = (ans + cnt[i]) % mod;
}

ll sum = quick_pow(ans, mod - 2);

for(int i = n / 2 + 1;i <= n; i++) {
printf("% lld",sum * cnt[i] % mod);
}

printf("\n");

}
}
}

signed main() {
ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}

本文作者:jujimeizuo
本文地址https://blog.jujimeizuo.cn/2020/08/05/hdu-6825/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!