SSerxhs和Serval的退役纪念赛

SSerxhs和Serval的退役纪念赛

幼儿园篮球题

有n个球,其中m个是红色的,其余的是蓝色的
从中随机选出k个,若选出了x个红球则得分为 $x^L$ ,求期望得分模998244353。
共T组数据,每组数据的L是相同的
T≤200,L≤2×10^5,m,k≤n≤2×10^7

请先思考后再展开

纯粹推柿子题
$$
\begin{aligned}
ans &=\sum_{i=0}^{mx} C_{n-m}^{k-i}C_m^i i^L,次幂转斯特林 \\
&=\sum_{j=1}^k S2(L,j)j! ( \sum_{i=j}^k C_m^i C_i^j C_{n-m}^{k-i} ) \\
&=\sum_{j=1}^k S2(L,j)j! ( \sum_{i=j}^k C_m^j C_{m-j}^{i-j} C_{n-m}^{k-i} ) \\
&=\sum_{j=1}^k S2(L,j)j! C_m^j ( \sum_{pp=i-j=0}^{k-j} C_{m-j}^{pp} C_{n-m}^{(k-j)-pp} ),范德蒙德卷积 \\
&=\sum_{j=1}^k S2(L,j)j! C_m^j C_{n-j}^{k-j} \\
\end{aligned}
$$

注意到循环的上界其实是 min(L,k,m),求整行斯特林数即可
时间复杂度为 $O(LlogL+Ls)$

幼儿园唱歌题

题意:给出一个2e5的串,2e5次询问是串S[l1,r1]的前缀且是串S[l2,r2]的后缀的最长回文串长度

请先思考后再展开

对正串反串建广义pam,然后找到lca的len即可

幼儿园跳舞题

给出一个n个点的dag,q次询问不经过点k下x到y距离
范围允许n^3、nq做法

请先思考后再展开

前置知识:floyd的原理
这题的关键是想清楚dag到底有什么用
观察数据范围应该是个3方的算法,可能是floyd,也可能是其他加点外循环再加点特技;同时还应当注意nq是可行的,可能是预处理
先考虑第一种,如果是个普通的图,你可能曾经像我一样想过处理f和g分别表示使用了前缀、后缀的点
但随后考虑到路径上不一定是单调的,所以就被否决了
但dag可以帮助我们搞出一个单调的东西————拓扑序
于是就是 $O(n^3+nq)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/de05.html
转载请注明出处,谢谢!