题面

传送门

一句话题意：

给定$n\leq 1e9,k\leq 1e7,T\leq 1e9$

设全集$U=\lbrace 1,2,3,...n\rbrace $，求$(min_{x\in S}\lbrace S\rbrace (S\subseteq U, \lvert S \rvert =k))^T$的期望

重要思想

注意，在遇到包含

思路

首先，通过枚举$S$集合最小值选取哪个数，可以得到：

$Ans(k)=\sum_{i=1}^n \binom{n-i}{k-1} T^i$

然后，通过枚举$S$集合最小值至少是多少，并且每次累加比上一次还大的可能性，可以得到：

$Ans(k)=T\binom{n}{k}+\sum_{i=1}^{n-1} \binom{n-i}{k}T^i(T-1)$

发现这个式子的后面一部分可以表示成第一个式子：

$Ans(k)=T\binom{n}{k}+(T-1)Ans(k+1)$

从$Ans(n)$开始往下累加一下，可以得到：

$Ans(k)=T(\sum_{i=0}^{{n-k}\binom{n}{k+i}(T-1)}i)=T(\sum_{i=k}^{n\binom{n}{k}(T-1)}{i-k}$

这个式子要$O(n-k)$的时间，做不了，考虑怎么把它变成能算的$O(k)$

考虑二项式定理：$\sum_{i=0}^n (T-1)^{i\binom{n}{i}=(T-1+1)}n=T^n$

所以$Ans(k)=\frac{T}{(T-1)^k}(Tn-\sum_{i=0}^{k-1} (T-1)^i\binom{n}{i})$

就可以直接算了

最后不要忘了除以$\binom{n}{k}$，求得是期望

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#define MOD 998244353

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

inline int qpow(int a,int b){

	int re=1;

	while(b){

		if(b&1) re=1ll*re*a%MOD;

		a=1ll*a*a%MOD;b>>=1;

	}

	return re;

}

int n,k,A;int f[10000010],finv[10000010];

void init(){

	int i,len=10000000;

	f[0]=f[1]=finv[0]=finv[1]=1;

	for(i=2;i<=len;i++) f[i]=1ll*f[i-1]*i%MOD;

	finv[len]=qpow(f[len],MOD-2);

	for(i=len;i>2;i--) finv[i-1]=1ll*finv[i]*i%MOD;

	for(i=1;i<=k;i++) f[i]=1ll*f[i-1]*(n-i+1)%MOD;

}

int C(int x,int y){

	return 1ll*f[y]*finv[y]%MOD;

}

int main(){

	n=read();k=read();A=read();

	if(A==1){puts("1");return 0;}

	init();int i,ans=1ll*A*qpow(qpow(A-1,k),MOD-2)%MOD,tot=qpow(A,n),p=1;

	for(i=0;i<k;i++){

		tot=(1ll*tot-1ll*p*C(n,i)%MOD+MOD)%MOD;

		p=1ll*p*(A-1)%MOD;

	}

	printf("%lld\n",1ll*ans*tot%MOD*qpow(C(n,k),MOD-2)%MOD);

}

[NOI.AC省选模拟赛3.23] 集合 [数学]的相关教程结束。