§ 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}$,故有
等式两边同乘 $T$ ,可得
两式相减,可得
考虑只需要先求出 $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 代码
1 |
|