简要题意
有两个长度为 n 的序列 v,r，定义 U=\{1,2,3,\cdots,n\}。
对于一个集合 S\subseteq U，定义其的权值 E(S) 为：
E(S)=\max\left(\min_{k\in S} v_k, \min_{k\in S} r_k\right)
你需要对于 k\in[1,n]，求出所有大小为 k 的 S 的权值平均值。答案对 998,244,353 取模。
## 思路
首先我们发现设 $f(k)$ 表示大小为 $k$ 的 $S$ 的权值总和，则要求的就是 ${\binom{n}{k}}^{-1}f(k)$。将 $f(k)$ 的式子写下来：
$$
f(k)=\sum_{S\subseteq U,|S|=k}E(S)=\sum_{S\subseteq U,|S|=k}\sum_{i=0}^{+\infty}[E(S)=i]i
$$
通过经典 trick（好像是期望里的？），继续变形：
$$
f(k)=\sum_{S\subseteq U,|S|=k}\sum_{i=0}^{+\infty}[E(S)=i]i=\sum_{S\subseteq U,|S|=k}\sum_{i=1}^{+\infty}[E(S)\geq i]
$$
考察这个式子：
$$
\sum_{S\subseteq U,|S|=k}\sum_{i=1}^{+\infty}[E(S)\geq i]
$$
不妨探究 $E(S)\geq i$ 的等价条件。不难发现只要满足下列两个条件任意之一就可以得到 $E(S)\geq i$，反之亦然：
$$
\begin{aligned}
&\min_{k\in S} v_k\geq i\\
&\min_{k\in S} r_k\geq i
\end{aligned}
$$
然后我们只需要对这两个序列计数即可。
我们计算出 $v$ 中大于等于 $i$ 的元素数量 $A_i$，$r$ 中大于等于 $i$ 的元素数量 $B_i$，$v_i,r_i$ 均大于等于 $i$（即 $\min(v_j,r_j)\geq i$）的元素数量 $C_i$。
则答案就是：
$$
\sum_{i=1}^{+\infty} \binom{A_i}{k}+\binom{B_i}{k}-\binom{C_i}{k}
$$
计算 $A,B,C$ 的话，观察到值域 $10^6$ 并不大，直接开三个桶再做三遍后缀和即可。
现在我们可以做到 $O(n^2+V)$ 难以通过本题。其中 $V$ 为值域。
定义：
$$
f_a(k)=\sum_{i=1}^{+\infty} \binom{a_i}{k}=\sum_{i=1}^{+\infty} \frac{a_i!}{k!(a_i-k)!}=\frac{1}{k!}\sum_{i=1}^{+\infty}\frac{a_i!}{(a_i-k)!}
$$
记 $t_a(i)=\sum_j[a_j=i]$，则有：
$$
f_a(k)=\frac{1}{k!}\sum_{i=1}^{+\infty}\frac{a_i!}{(a_i-k)!}=\frac{1}{k!}\sum_{i=0}^{n} \frac{i!\cdot t_a(i)}{(i-k)!}
$$
定义 $g(i)=(n-i)!$，代入原式得：
$$
f_a(k)=\frac{1}{k!}\sum_{i=0}^{n} \frac{i!\cdot t_a(i)}{(i-k)!}=\frac{1}{k!}\sum_{i=0}^{n} \frac{i!\cdot t_a(i)}{g(n+k-i)}
$$
用 NTT 优化即可。
时间复杂度 $O(n\log n+V)$。
## 代码
[Submission Link](https://codeforces.com/contest/2038/submission/292404816)。
核心代码：
```cpp
const int N = 2e5 + 5, M = 1e6 + 5, FFT_N = 1e6 + 5;
int n, a[N], b[N], c[N], A[M], B[M], C[M];
int fact[N], inv[N];
constexpr int mod = 998244353, g = 3, ginv = 332748118;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }
int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }
int fastpow(int x, int y){
int ret = 1;
for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
return ret;
}
void init(int n){
fact[0] = inv[0] = fact[1] = inv[1] = 1;
for(int i=2;i<=n;i++){
fact[i] = Mul(fact[i - 1], i);
inv[i] = Mul(inv[mod % i], mod - mod / i);
}
for(int i=1;i<=n;i++) inv[i] = Mul(inv[i - 1], inv[i]);
}
int res_a[N], res_b[N], res_c[N], cnt[N], m;
void solve(int* a, int* res){
for(int i=0;i<=n;i++) cnt[i] = 0;
for(int i=1;i<=m;i++) cnt[a[i]]++;
Poly poly1(n + 1), poly2(n + 1);
for(int i=0;i<=n;i++) poly1[i] = Mul(fact[i], cnt[i]);
for(int i=0;i<=n;i++) poly2[i] = inv[n - i];
Poly res_poly = poly1 * poly2;
for(int i=1;i<=n;i++) res[i] = res_poly[i + n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i], c[i] = min(a[i], b[i]);
m = max(*max_element(a + 1, a + n + 1), *max_element(b + 1, b + n + 1));
for(int i=1;i<=n;i++) A[a[i]]++, B[b[i]]++, C[c[i]]++;
for(int i=m;~i;i--) A[i] += A[i + 1], B[i] += B[i + 1], C[i] += C[i + 1];
init(n);
solve(A, res_a), solve(B, res_b), solve(C, res_c);
for(int k=1;k<=n;k++){
int ans = Sub(Add(res_a[k], res_b[k]), res_c[k]);
ans = Mul(ans, inv[k]);
cout << Mul(ans, fastpow(binom(n, k), mod - 2)) << ' ';
}
return 0;
}
```