HDUOJ 6825 Set1

HDUOJ 6825 Set1

题目链接

Problem Description

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,5e6].

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

题解写得有问题，我修改了一下：

问题：给定一个的集合S，每次删除当前集合中最小的元素，再随机删掉1个元素，直到 $|s|=1$，求每个元素最后被留下来的概率。

• 考虑元素 $i$ 被留下来的方案数，前面有 $i?1$ 个元素，后面有 $n?i$ 个元素。
• 当前仅当 $n?i\le i?1$的时候， $i$ 才可能被留下。
• 每次删除最小的元素为操作 1，随机删掉一个元素为操作 2
• 大于元素 $i$ 的个元素一定是被操作 2 给删除的
  $i$ 被留下来的情况，一定是后面所有的元素( $n?i$ 个)，全部被前面 $i?1$ 个元素中的某个 $1$ 对 $1$ 的选择(使用操作 2)
• • 那么对后个元素，它们被选择的方案数是 $C_{i?1}^{n?i}?(n?i)!=A_{i?1}^{n?i}$
• 然后剩下的个元素 $(i?1)?(n?i)=2?i?n?1$ 两两删除。
• • 那么被留下来的方案数为 $\frac{(2?i?n?1)!}{(\frac{2?i?n?1}{2})!?2^{\frac{2?i?n?1}{2}}}$

答案就是两者相乘，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll N=5e6+5;
int t;
ll n,F[N+1],I[N+1],cnt[N+1];
ll power(ll a,ll b){
    return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
void init(){
    F[0]=1;for(ll i=1;i<=N;i++) F[i]=F[i-1]*i%mod;I[N]=power(F[N],mod-2);for(ll i=N;i--;){
    I[i]=I[i+1]*(i+1)%mod;}
}ll C(ll n,ll k){
    return F[n]*I[n-k]%mod*I[k]%mod;
}int main(){
    init();scanf("%d",&t);while(t--){
    scanf("%lld",&n);ll sum=0;for(ll i=1;i<=n;i++){
    if(2*i-n-1<0) cnt[i]=C(i-1,n-i)*F[n-i]%mod;else cnt[i]=C(i-1,n-i)*F[n-i]%mod*F[2*i-n-1]%mod*power(power(2,mod-2),(2*i-n-1)/2)%mod*I[(2*i-n-1)/2]%mod;sum=(sum+cnt[i])%mod;}for(ll i=1;i<=n;i++){
    if(i>1) printf(" ");printf("%lld",cnt[i]*power(sum,mod-2)%mod);}printf("\n");}return 0;
}