HDU2020多校round5 1012题解
Set1
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
You are given a set ={1..n}. It guarantees that n is odd. You have to do the following operations until there is only element in the set:
Firstly, delete the smallest element of . Then randomly delete another element from .
For each , determine the probability of being left in the .
It can be shown that the answers can be represented by , where and are coprime integers, and print the value of mod .
Input
The first line containing the only integer denoting the number of test cases.
For each test case:
The first line contains a integer .
It guarantees that: .
Output
For each test case, you should output integers, of them means the probability of being left in the .
Sample Input
1
3
Sample Output
0 499122177 499122177
题目大意
给定一个包含(为奇数)的集合,进行若干轮删除操作,每次先删掉集合中最新小的元素,再等概率地随机删除一个元素,直到只余下一个元素,求最终留在的概率。
思路分析
Step 1
先来看一个弱化版的问题,从中删去个数,每次删数随机,问最终留下来的概率。
很容易得出,每个删数序列(指删除数的顺序,比如:序列{1,3,4}就是先删除1,然后删除3,最后删除4的意思)的概率都是确定的,因为每次删除都是从以外的数中挑一个删除,若当前剩余个数选中的概率是,整个序列出现的概率就是,而这样的序列一共有种,所以留下的概率。
在这道简化的题目中,我们首先分析出了每种不同的删数序列出现概率相同这一性质,这说明可以通过求合法的序列个数*单个序列出现的概率得到留下的概率。对于本题,也有相同的结论。
本题中每一轮删数相当于一次固定删除+一次随机删除,将一轮删除看成删除一个数对,可以证明每个删除数对序列出现的概率是,求得方案数就可以得到最终概率。
Step 2
首先考虑概率为0的情况,可以证明,当时,一定不可能留下来。因为对于每一个右侧的数,一定不可能通过删除最小元素的方式从中移除(若通过此方式移除则i必定会先被移除),所以只能通过随机删除的方式移除,需要轮移除,而最迟在第轮的第一次操作中被删除,由于,所以必定不可能留下来。
继续考虑概率不为的情况,如上述所说,右侧的数只能由随机操作删除,因此不妨把每一轮删数看成是依次删除一个数对里的两个,问题的一部分就被转化成了从前个数中挑出个数,与后个数组成个有序数对的方案数,选出个数共有种方案,对应的有序数对共有种方案,这部分就解决了。
但是前还有剩下个数,接下来考虑这部分的解决方案。因为后面的数都被上述方案配对删除了,所以这部分数就得两两配对删除(剩下的一定是偶数个),令,配对的方案一共有种,这部分也就解决了。
然后需要考虑的是两部分如何拼到一起,由于两部分之间是互相没有干扰的,最终的总方案数就是两者的乘积,。
乘以Step 1中得到的概率,对于给定的,对应的答案为,可以分别预处理出分子分母的值,时间复杂度为。
最后附上代码
#include<bits/stdc++.h> #define reg register using namespace std; using ll=long long; const int MOD=998244353; const int MAXN=5e6+1; int T,n; ll inv2[MAXN]= {1},inv[MAXN]= {1,1},p[MAXN]= {1,1},p1[MAXN]= {1,1}; //inv2存储偶数阶乘2*4*6...的逆元,inv存储阶乘的逆元,p存储阶乘,p1存储奇数阶乘1*3*5... inline void exgcd(const int &a,const int &b,ll &x,ll &y) { if(!b) { x=1,y=0; return ; } exgcd(b,a%b,y,x); y-=a/b*x; } inline ll getInv(const int &a) { reg ll x,y; exgcd(a,MOD,x,y); return x<0 ? x+MOD:x; } inline void init() { reg ll tmp; for(reg int i=2; i<MAXN; ++i) { tmp=getInv(i); if(~i&1) inv2[i]=tmp*inv2[i-2]%MOD; else p1[i]=p1[i-2]*i%MOD; inv[i]=tmp*inv[i-1]%MOD; p[i]=p[i-1]*i%MOD; } } int main() { ios::sync_with_stdio(0); init(); for(cin>>T; T; --T) { cin>>n; for(reg int i=1; i<=n; ++i) { if(n-i>i-1) cout<<"0 "; else { reg ll ans=inv2[n-1]*p[i-1]%MOD*inv[2*i-n-1]%MOD; if(2*i-n-1>=2) ans=ans*p1[2*i-n-2]%MOD; //注意特判边界 cout<<ans<<(i==n ? '\n':' '); } } } return 0; }