Description：

对于集合 $S$ ，定义 $F(S)=A^{\min S}$ ，求 $E(F(S)|S\subseteq N\cap[1,n],|S|=k)$ 。

$1\leqslant n< MOD=998244353,1\leqslant k\leqslant 10^7$

Solution：

首先枚举最小值后面显然选 $k-1$ 个得到答案的式子为： $$ \frac{\sum_iA^i\binom{n-i}{k-1}}{\binom nk} $$ 考试的时候一直想在 $n$ 那一维递推，但是结束之后得知可以用 $k$ 递推。

只考虑 $\sum_iA^i\binom{n-i}{k-1}$ ，下面那个可以 $O(k)$ 暴力算，设 $f(k)=\sum_iA^i\binom{n-i}{k-1}$ ，由于 $\sum_{i=0}^{n-1}A_i=\frac{A^n-1}{A-1}(A\ne 0)$ ： $$ \begin{align} f(k)&=\sum_{i=1}^{n-k+1}A^i\binom{n-i}{k-1}\\ &=\sum_{i=1}^{n-k+1}(\sum_{j=0}^{i-1}A^j\times (A-1)+1)\times \binom{n-i}{k-1}\\ &=\sum_{i=1}^{n-k+1}\sum_{j=1}^{i-1}A^j\times (A-1)\times \binom{n-i}{k-1}+\sum_{i=1}^{n-k+1}A\binom{n-i}{k-1}\\ &=\sum_{j=1}^{n-k}A^j\times (A-1)\times \sum_{i=j+1}^{n-k+1}\binom{n-i}{k-1}+\sum_{i=1}^{n-k+1}A\binom{n-i}{k-1}\\ &=\sum_{j=1}^{n-k}A^j\times (A-1)\times \sum_{i=k-1}^{n-j-1}\binom i{k-1}+\sum_{i=k-1}^{n-1}A\binom i{k-1}\\ &=\sum_{j=1}^{n-k}A^j\times (A-1)\times \sum_{i=k-1}^{n-j-1}\binom i{k-1}+A\sum_{i=k-1}^{n-1}\binom i{k-1}\\ &=\sum_{i=1}^{n-k}A^j\times (A-1)\times \binom {n-i}k+A\binom nk\\ &=f(k+1)\times (A-1)+A\binom nk \end{align} $$ 那么我们一直展开下去，直到 $f(n)=A$ ： $$ f(k)=A\sum_{i=k}^n\binom ni\times (A-1)^{i-k}=A(A-1)^{-k}\sum_{i=k}^n\binom ni\times (A-1)^i $$ 后面那部分是一个只有一部分的二项式定理： $$ f(k)=A(A-1)^{-k}(A^n-\sum_{i=0}^{k-1}\binom ni\times(A-1)^i) $$ 于是就可以 $O(k)$ 求了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

#pragma GCC optimize(2)

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

#define MAXK 10000010

#define K 10000000

int n,k,A;

int fac[MAXK],nfac[MAXK],inv[MAXK];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % P;

		a = 1ll * a * a % P;

		b = b >> 1;

	}

	return res;

}

void work()

{

	scanf("%d%d%d",&n,&k,&A);

	if(A == 1){cout << 1 << endl;return;}

	nfac[0] = 1;for(int i = 1,cur = n;i <= k;++i,--cur)nfac[i] = 1ll * nfac[i - 1] * cur % P;

	int ans = power(A,n);

	int pows = 1;

	for(int i = 0;i <= k - 1;++i)ans = (ans - 1ll * nfac[i] * inv[i] % P * pows % P + P) % P,pows = 1ll * pows * (A - 1) % P;

	ans = 1ll * ans * A % P * power(power(A - 1,P - 2),k) % P * power(nfac[k],P - 2) % P * fac[k] % P;

	cout << ans << endl;

	return;

}

int main()

{

	freopen("set.in","r",stdin);

	freopen("set.out","w",stdout);

	fac[0] = 1;for(int i = 1;i <= K;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	inv[K] = power(fac[K],P - 2);for(int i = K - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	int testcases = rd();

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}