§ 1 题意

记 $[n]=\lbrace 1,2,3,\cdots,n \rbrace$，对于集合 $S$ 定义 $\min S=\min\limits_{x\in S}x,\ \ F(S)=T^{\min S}$。

给出 $n,\ m,\ T$，求 $E(F(S)\ |\ S\subseteq [n],\ |S|=k)$ 的值，答案对 $M=998244353$ 取模。

$1\leq k\leq n\lt M,\ \ 1\leq k\leq 10^7,\ \ 1\leq T\lt M$。

§ 2 分析

令 $A_k=\sum\limits_{S\subseteq [n],\ |S|=k}F(S)$，则所求的答案等于 $\frac{A_k}{\binom{n}{k}}$。

考虑从组合意义入手求解 $A_k$，我们从 $1\sim n$ 枚举 $\min S$ 的最小值。

若当前最小值为 $i$，则可从比 $i$ 大的 $n-i$ 个数中取剩余 $k-1$ 个，贡献为 $T^i·\binom{n-i}{k-1}$，故有

$\begin{align} A_k=\sum\limits_{i=1}^nT^i·\binom{n-i}{k-1} \end{align}$

等式两边同乘 $T$ ，可得

$\begin{align} TA_k&=\sum\limits_{i=1}^nT^{i+1}·\binom{n-i}{k-1} \\ &=\sum\limits_{i=2}^{n+1}T^i·\binom{n-i+1}{k-1} \end{align}$

两式相减，可得

$\begin{align} (T-1)\,A_k&=\sum\limits_{i=2}^nT^i·\left[\binom{n-i+1}{k-1}-\binom{n-i}{k-1}\right]-T·\binom{n-1}{k-1} \\ &=\sum\limits_{i=2}^nT^i·\binom{n-i}{k-2}-T·\binom{n-1}{k-1} \\ &=\sum\limits_{i=1}^nT^i·\binom{n-i}{k-2}-T·\left[\binom{n-1}{k-2}+\binom{n-1}{k-1}\right] \\ &=A_{k-1}-T·\binom{n}{k-1} \end{align}$

考虑只需要先求出 $T-1$ 的逆元以及 $i=0\sim k-1$ 的 $\binom{n}{i}$ 即可 $O(n)$ 递推出 $A_k$。

其中后者只需要先 $O(n)$ 递推出 $0\sim k-1$ 的逆元，然后即可从 $\binom{n}{0}$ 开始递推得到。

注意 $T=1$ 的情况一定不要忘记特判！这种情况下上式左边会变成 $0·A_k$ 而无法计算，直接输出 $1$ 即可。

总时间复杂度为 $O(n)$。

§ 3 代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M = 998244353;

inline void getint(int &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

int n, k, T, inv[10000002], Cn[10000002], A[10000002], Inv;

inline ll fastpow(ll bas, ll ex){
	register ll res = 1; bas %= M;
	while(ex){
		if(ex & 1) res = res * bas % M;
		bas = bas * bas % M, ex >>= 1;
	}
	return res;
}

int main(){
	getint(n), getint(k), getint(T); if(T == 1) return puts("1"), 0;
	inv[1] = 1, Cn[0] = 1, Inv = fastpow(T - 1, M - 2), A[1] = T * (fastpow(T, n) - 1LL + M) % M * Inv % M;
	for(register int i = 2; i <= k; i++) inv[i] = (M - M / i) * (ll)inv[M % i] % M;
	for(register int i = 1; i <= k; i++) Cn[i] = Cn[i - 1] * (n - i + 1LL) % M * (ll)inv[i] % M;
	for(register int i = 2; i <= k; i++) A[i] = ((A[i - 1] - T * (ll)Cn[i - 1]) % M + M) * Inv % M;
	return printf("%d", A[k] * fastpow(Cn[k], M - 2) % M), 0;
}