1031总结

T1

考虑概率=合法方案数/所有方案数
所有方案数\(n^n\)
合法方案数:\(f_n = f_{n-1} + (n-1) f_{n-2}\)
打表就可以发现这个规律
然后就没了

T2

考虑分治,每次预处理mid向左向右的背包
然后每次处理跨中点的询问
\(O((NM+Q)\log N+QM)\)

T3

满分做法:
考虑错位排列的方案数定义
\[ \text{subfactorial}_n = n! \sum _{k=0}^n \frac{(-1)^k}{k!}\]
概率就是除掉n!
显然\(\displaystyle \sum _{k=0}^n \frac{(-1)^k}{k!} \) 收敛于 \( \dfrac{1}{e}\)
树链剖分维护(大到一定值(大概25左右)就不用修改了),均摊线段树

0