[EZOI][1217NOI模拟赛]set(组合数学)

§ 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}