Atcoder abc295
https://atcoder.jp/contests/abc295/tasks
E - Kth Number
给长n数组a, $a[i]\in[0,M]$
对于每个$a[i]=0$,等概率修改$a[i]\in[1,M]$
所有修改完后, sort a
问 exp(A[k]) mod 998244353
N 2000
M 2000
4s
1024mb
我的思路
$ans = \sum_{v=1\to m} v\cdot p(v)$
其中$p(v)$表示 $v$是排序后第$k$小的概率
有$z$个0,其中$z_1$个改为$< v$,$z_2$个改为$=v$,剩下$z-z_1-z_2$个改为$> v$
$p(v) \cdot z^m = \sum_{z_1,z_2} \binom{z}{z_1}\binom{z-z_1}{z_2} (v-1)^{z_1}1^{z_2}(m-v)^{z-z_1-z_2}$, 其中 $z_1 + count(<v) < k$且$z_1+z_2+count(\le v) \ge k$
看上去是$O(m n^2)$的