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