集合 解題報告

組合數學,二項式定理

集合

對于集合\(S\)，記\(\min S\)表示\(S\)中最小的元素，并定義\(F(S)=A^{\min S}\)，設\([n]\)表示集合\(\{1,2,\dots,n\}\)

請求出\(E(F(S)|S\subseteq[n],|S|=k)\)，對\(M =998244353\)取模

\(1\le k\le n<M,1\le k\le 10^7,1\le A <M,1\le T\le 5\)

考場上并不會推...

考慮欽定最小值，那麼答案為

\[\frac{\sum_{i=1}^nA^i\binom{n-i}{k-1}}{\binom{n}{k}}

\]

顯然這個複雜度需要搞到\(O(k)\)

設

\[f(k)=\sum_{i=1}^nA^i\binom{n-i}{k-1}

如果\(A_i=1\)，那麼答案為\(1\)

否則

\[\frac{A^i-1}{A-1}=\sum_{j=0}^{i-1}A^j

那麼

\[\begin{aligned}

f(k)&=\sum_{i=1}^nA^i\binom{n-i}{k-1}\\

&=\sum_{i=1}^n\binom{n-i}{k-1}((\sum_{j=1}^{n-1}A^j)(A-1)+1)\\

&=(A-1)\sum_{j=0}^{n-1}A^j\sum_{i=j+1}^n\binom{n-i}{k-1}+\sum_{i=1}^n\binom{n-i}{k-1}\\

&=(A-1)\sum_{j=0}^{n-1}A^j\binom{n-j}{k}+\binom{n}{k}\\

&=(A-1)\sum_{i=1}^{n-1}A_j\binom{n-j}{k}+A\binom{n}{k}\\

&=(A-1)f(k+1)+A\binom{n}{k}\\

&=\sum_{i=k}^nA(A-1)^{i-k}\binom{n}{i}\\

&=A(A-1)^{-k}\sum_{i=k}^n(A-1)^i\binom{n}{i}\\

&=A(A-1)^{-k}(A^n-\sum_{i=0}^{k-1}(A-1)^i\binom{n}{i})

\end{aligned}

#include <cstdio>
#include <cctype>
const int N=1e7+1;
const int mod=998244353;
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int fac[N],inv[N];
int main()
{
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	fac[0]=1;for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
	inv[N-1]=qp(fac[N-1],mod-2);
	for(int i=N-2;~i;i--) inv[i]=mul(inv[i+1],i+1);
	int T;read(T);
	while(T--)
	{
		int n,k,a,ans=0;
		read(n),read(k),read(a);
		if(a==1) {puts("1");continue;}
		for(int f1=1,f2=1,i=0;i<k;i++)
		{
			ans=add(ans,mul(f1,mul(f2,inv[i])));
			f1=mul(f1,a-1);
			f2=mul(f2,n-i);
		}
		ans=add(qp(a,n),mod-ans);
		int d=inv[k];
		for(int i=n;i>n-k;i--) d=mul(d,i);
		ans=mul(ans,qp(d,mod-2));
		printf("%lld\n",mul(a,mul(qp(qp(a-1,k),mod-2),ans)));
	}
	return 0;
}