T1

不会，感觉像之前那道 bitset优化的大暴力

现在做完T2了还是不会，只会 $O(nm)$ 的

咱总不能正解真是这个复杂度吧

真是我捶死出题人

nm1e9 正好1e9

这是能跑的吗？

欸🤓👆，是不是可以这样子

我先一遍大 $n^2$ 求出所有两个数能合成出来的数，额外记录一个时间戳表示他最早在什么时候出现

然后接下来直接log查询就好了

unorder会T

pbds改变生活！

希望能过

T2

矩阵乘法？

设状态分别为

|上一个数为无用数，上一个为 S，上两个为 SO |上一个数为无用数，上一个为 S，上两个为 SO |同|无所谓下一个是什么

​ 已存在0个SOS 已存在1个SOS

矩阵快速幂即可

总共10个状态

upd:8:18做完了:underage:

希望能过

T3

显然是可以用线段树维护的

设 $f_{i}$ 表示有 $i$ 人选了一血气球的方案数

然后就可以线段树维护了

时间复杂度：$O(qc^2logn)$

考虑优化合并

卷卷卷卷卷积？逗我呢

拿个80pts跑人了

草了，好像只有50分

想想t1去了

T4

朴素dp

先找到重心，考虑重心的第二定义，即：每个子树的大小都不超过大小之和的一半

即

$\forall i \in son_u,siz_i\le\left \lceil \frac{\sum_{v\in son_u}siz_v}{2} \right \rceil$

当只有一个重心时，以其为根建树，设 $f_{i,j}$ 表示以 $i$ 为根的子树大小为 $j$ 的方案数即可

？不是？

这代码写的跟个垃圾场一样，我都不报希望了都

这tm能过大样例？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

赛后总结

本来第三题能做的，最后没时间了，以后考试还得是专注为好

时间越多机会越多

还有多尝试反向的角度，哪怕打心底认为不可以

t4也是，本来调代码的时候已经不抱希望了

相信奇迹吧，好运双倍给下一次

T3正解

正着做不是很好做，考虑设 $f_i$ 表示有 $i$ 人选择了一血气球的方案数

我们发现答案其实就是 $\prod_{i}(a_i+b_i)-\sum_{i=0}^{c-1}f_i$

我们发现这个dp是可撤销的，比如说我们设 $f_i(k)$ 表示删去 $k$ 这个人后的方案数

那么有

$f_0(k)=\frac{f_0}{(a_k+b_k)}$

$f_i(k)=f_i - b_kf_i(k)-a_kf_{i-1}(k)$

也就是

$f_i(k)=\frac{f_i - a_kf_{i-1}(k)}{1+b_k}$

$newf_i-a_kf_{i-1}=b_kf_i$