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;
}