组合数学 + 概率论 - Set1 - HDU 6825_综合

组合数学 + 概率论 - Set1 - HDU 6825

题意：

$给定一个集合S=\lbrace 1,2,...,n\rbrace，每次删除当前集合中的最小元素，同时再随机删除一个元素，直到|S|=1，求每个元素最后被留下来的概率。$

$n是奇数，答案对998244353取模。$

输入：

$T(1\le T \le 40)组测试数据，$

$每组包括一个正整数n。$

$保证\sum n \le 5×10^6$

输出：

$n个正整数，表示答案。$

Sample Input

1
3

Sample Output

0 499122177 499122177

分析：

$考虑第i个元素被留下来，前有i-1个元素，后有n-i个元素。$

$当且仅当n-i \le i-1时，i才可能被留下。$

$记每次删除最小的元素为操作1，随即删除一个元素为操作2。$

$第i个元素后面的元素必是被操作2删除的。$

$而i被留下的情况：$

$①、一定是i后面的n-i个元素与前i-1个元素中的n-i个元素一一对应被删除，$

$②、接着从前(i-1)-(n-i)=2i-n-1个元素中，两两选择删除，直至剩下第i个元素。$

$对于情形①，我们先要从前i-1个元素选择n-i个元素一一配对，总的不同选法数量为C_{i-1}^{n-i}，$

$由于配对是有顺序的，对于每一种选法，都对应(n-i)!种不同的方案，故①的方案总数为C_{i-1}^{n-i}×(n-i)!。$

$对于情形②，此时i为最后一个元素，现从前2i-n-1个元素中两两配对删除，$

$故②的方案总数为$

$C_{2i-n-1}^2×C_{2i-n-3}^2×...×C_{2}^2=\frac{(2i-n-1)!}{(2i-n-1-2)!·2!}×\frac{(2i-n-3)!}{(2i-n-3-2)!·2!}×...×1=\frac{(2i-n-1)!}{2!^{\frac{2i-n-1}{2}}}$

注意： $选择这\frac{2i-n-1}{2}对，顺序是固定的。例如(1,3)和(2,4)，必然是先删除(1,3)再删除(2,4)，$

$\qquad\ \ 这个顺序是固定的，因此最后我们还要考虑这\frac{2i-n-1}{2}对排列顺序的影响，故将上式再除(\frac{2i-n-1}{2})!。$

$综上，元素i被留下来的方案总数为：$

$cnt[i]=C_{i-1}^{n-i}×(n-i)!×\frac{(2i-n-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}$

注意： $情况②仅在(i-1)\ge(n-i)时才会被计算，避免数组越界。$

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>#define ll long longusing namespace std;const int N=5e6, mod=998244353;int T, n;
int fac[N+10], inv[N+10], inv_fac2[N+10];
int cnt[N+10];int quick_pow(int a,int b, int mod)
{int res=1;while(b){if(b&1) res=(ll)res*a%mod;a=(ll)a*a%mod;b>>=1;}return res;
}void Init()
{fac[0]=1;for(int i=1;i<=N;i++) fac[i]=(ll)fac[i-1]*i%mod;inv[N]=quick_pow(fac[N],mod-2,mod);for(int i=N-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;inv_fac2[0]=1;inv_fac2[1]=quick_pow(2,mod-2,mod);for(int i=2;i<=N;i++) inv_fac2[i]=(ll)inv_fac2[i-1]*inv_fac2[1]%mod;
}int C(int n,int m)
{if(n<m) return 0;return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}int main()
{Init();cin>>T;while(T--){scanf("%d",&n);int sum=0;for(int i=1;i<=n/2;i++) cnt[i]=0;for(int i=n/2+1;i<=n;i++) {cnt[i]=(ll)C(i-1,n-i)*fac[n-i]%mod;if(i-1>n-i) cnt[i]=(ll)cnt[i]*fac[2*i-n-1]%mod*inv[(2*i-n-1)/2]%mod*inv_fac2[(2*i-n-1)/2]%mod;sum=(sum+cnt[i])%mod;}sum=quick_pow(sum,mod-2,mod);for(int i=1;i<=n;i++) {printf("%d",(ll)cnt[i]*sum%mod);if(i!=n) printf(" ");}puts("");}return 0;
}