题意：
给你一个集合 (S={1..n})。保证 (n) 是奇数，必须执行以下操作，直到集合中只有一个元素：
首先删除 (S) 的最小元素（操作 (1)），然后从 (S) 中随机删除另一个元素（操作 (2)）。对于每个 (i∈[1，n]) ，确定 (i) 留在 (S) 中的概率。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6825
分析：
首先，可以发现对于 (1leq i leq lfloor frac{n}{2}
floor)，其概率均为 (0)，因为这些数必然会在每次取集合最小数的操作中被取掉。
对于 (i>lfloor frac{n}{2}
floor)，其后面的 (n-i) 个数，必然是在操作 (2) 中被去掉，并且和某一个小的数配对。
其方案数为：
[left(
egin{matrix}
i-1\
n-i
end{matrix}
ight)
*(n-i)!
]
其中的 ((n-i)!) 是对 (i) 后面的 ((n-i)) 个数进行排列，与前面选出的数进行配对。
对于前面的剩余的 (i-1-(n-i)=2*i-n-1) 个数，两两进行配对选择，即每次选取 (2) 两个数，但由于每次配对后，每组的位置就确定了，因此要去除排列，
方案数为：
[frac{left(
egin{matrix}
2i-n-1\
2,2,2...2
end{matrix}
ight)}{(frac{2i-n-1}{2})!}
]
所以最终 (i) 保留下来的方案数为：
[egin{align}
cnt[i] & = left(egin{matrix}i-1\n-iend{matrix}
ight)*(n-i)!* frac{left(egin{matrix}2i-n-1\2,2,2...2end{matrix}
ight)}{(frac{2i-n-1}{2})!}\
& = frac{(i-1)!}{2^{frac{2i-n-1}{2}}}*frac{1}{(frac{2i-n-1}{2})! }
end{align}
]
令 (sum=sum_{i=1}^{n}{cnt[i]})，为总的方案数。那么，(i) 保留下来的概率为：(P_i=frac{cnt[i]}{sum})
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=5e6+5;
ll fac[N],inv[N],cnt[N],invf[N];
ll power(ll a,ll b)
{
ll res=1;
a%=mod;
while(b)
{
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void init()
{
fac[0]=1;
for(int i=1;i<N;i++)
fac[i]=fac[i-1]*i%mod;
invf[N-5]=power(fac[N-5],mod-2);
for(int i=N-6;i>=0;i--)
invf[i]=invf[i+1]*(i+1)%mod;
inv[0]=1;
inv[1]=1LL*499122177;
for(int i=2;i<N;i++)
inv[i]=inv[i-1]*inv[1]%mod;
}
int main()
{
int T,n;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n/2;i++) cnt[i]=0;
for(int i=n/2+1;i<=n;i++)
{
cnt[i]=fac[i-1]*inv[(2*i-n-1)/2]%mod*invf[(2*i-n-1)/2]%mod;
sum=(sum+cnt[i])%mod;
}
ll inv_sum=power(sum,mod-2);
for(int i=1;i<=n;i++)
printf("%lld%c",cnt[i]*inv_sum%mod,i==n?'
':' ');
}
return 0;
}