Matt Blog

CF1368E Ski Accidents

比较神的构造，被对手 10min 秒了。

看到 $\frac47$ 和 $out_i\le2$，然后就应该想到 $\frac47=\frac{2^2}{2^0+2^1+2^2}$，尝试将 $n$ 划分为 $3$ 个集合。感觉比较结论，所以直接说了。将 $n$ 划分成 $3$ 个无交且并为全集的集合 $A,B,C$，满足

$\forall a\in A,\{\forall u \rarr a,u\in C\}$

$\forall b\in B,\{\exist u \rarr b,u\in A\},\{\not\exist u\rarr b,u\in B\}$

$\forall c\in C,\{\exist u \rarr c,u\in B\}$

分类讨论一下，不难发现 $A,B,C$ 交且并为全集。由于 $\forall b\in B,\exist a \rarr b$，$|B|\le2|A|$，同理，$|B|\le2|C|$，即 $4|A|\ge2|B|\ge|C|$，$|C|\le\frac47n$。删除 $C$ 中的所有点后 $A$ 的入度都是 $0$，$B$ 的出度都是 $0$，故最多只有 $a\rarr b$ 的边，满足条件。

因为是 DAG，分集合时可以做拓扑排序。复杂度线性。

CF1278F Cards

*2600

设 $p=\frac 1 m,q=1-p$，则

$ans=\sum_{i=1}^n \binom n i i^k p^i q^{n-i}$

$n$ 非常大，又有 $i^k$，所以套路地考虑用斯特林数和下降幂表示幂。

$ans=\sum_{i=1}^n \binom n i i^k p^i q^{n-i} \\ =\sum_{i=1}^n \binom n i p^i q^{n-i} \sum_{j=1}^k {k \brace j} i^{\underline j} \\ =\sum_{i=1}^n \binom n i p^i q^{n-i} \sum_{j=1}^k {k \brace j} \binom i j j! \\ =\sum_{j=1}^k {k \brace j}j!\sum_{i=1}^n \binom n i \binom i j p^i q^{n-i}\\ =\sum_{j=1}^k {k \brace j}\binom{n}{j}j!\sum_{i=\color{red}j}^n\binom{n-j}{i-j}p^iq^{n-i}\\ =\sum_{j=1}^k {k \brace j}\binom{n}{j}j!\sum_{i=\color{red}0}^{\color{red}n-j}\binom{n-j}{i}p^{i+j}q^{n-i-j}\\ =\sum_{j=1}^k {k \brace j}\binom{n}{j}j!p^j\sum_{i=\color{red}0}^{\color{red}n-j}\binom{n-j}{i}p^{i}q^{n-i-j}\\ =\sum_{j=1}^k {k \brace j}\binom{n}{j}j!p^j(p+q)^{n-j}\\ =\sum_{j=1}^k {k \brace j}\binom{n}{j}j!p^j\\ =\sum_{j=1}^k {k \brace j}n^{\underline j}p^j$

预处理斯特林数后直接做，复杂度为 $O(k^2)$。