2020 Multi-University Training Contest 5 hdu6825 Set1(组合数学+概率)

题目

每次给定一个n，保证n为奇数，

表示在包含{1,2,...,n}的集合S中，每次删除当前集合中最小的元素，再随机删掉1个元素，

直到|S|=1，求每个元素最后被留下来的概率，答案对998244353取模。

T(T<=40)组样例，保证sumn<=5e6

思路来源

官方题解

题解

赛中被学弟找规律搞过去了论手玩样例的重要性

对于i来说，比其大的n-i个数只能通过随机得到，

则其需要n-i个最小元素与之配对，只能从前i-1个里挑，有i-1>=n-i

考虑最终的删除序列，

则相当于在i-1个的删除序列中向后插空n-i个，n-i个有顺序，

考虑剩下的(i-1-(n-i))个数，注意到2*i-n-1为偶数，

每次取两个凑一对，直至取完，方案数是，

将式子展开化简得，，

但注意到这实际指定了这对的顺序，

实际上，由于最小的约束，(1,2)(3,4)与(3,4)(1,2)是一种方案，必先取(1,2)，

故将顺序除掉

即有

总方案，概率

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10,mod=998244353;
int t,n,fac[N],finv[N],ans[N],pw[N],two;
int modpow(int x,int n,int mod){
    int res=1;
    for(;n;n>>=1,x=1ll*x*x%mod){
        if(n&1)res=1ll*res*x%mod;
    }
    return res;
}
int C(int n,int m){
    if(n-m<0 || n<0 || m<0)return 0;
    return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
    pw[0]=fac[0]=finv[0]=1;
    two=modpow(2,mod-2,mod);
    for(int i=1;i<N;++i){
        fac[i]=1ll*fac[i-1]*i%mod;
        pw[i]=1ll*pw[i-1]*two%mod;
    }
    finv[N-1]=modpow(fac[N-1],mod-2,mod);
    for(int i=N-2;i>=1;--i){
        finv[i]=1ll*finv[i+1]*(i+1)%mod;
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int sum=0;
        for(int i=1;i<=n;++i){
            if(i-1<n-i){
                ans[i]=0;
                continue;
            }
            int left=2*i-n-1,half=left/2;
            ans[i]=1ll*C(i-1,n-i)*fac[n-i]%mod*fac[left]%mod*pw[half]%mod*finv[half]%mod;
            sum=(sum+ans[i])%mod;
        }
        sum=modpow(sum,mod-2,mod);
        for(int i=1;i<=n;++i){
            printf("%d%c",1ll*ans[i]*sum%mod," \n"[i==n]);
        }
    }
    return 0;
}