CVBB ACM Team

题意和题解:过水已隐藏

题意:三维计算几何，计算射线和球的交点以及反射后的射线方向。

题解:解一元二次方程+模拟即可。

题意:长度为$n$的$01$串，每一位有$p_i$的概率是$1$否则是$0$，求存在一个长度为$k$的连续$1$的子串的概率。$(k \le n \le 100 \, 000)$

题解:考虑反面，不存在一个长度为$k$的连续$1$的子串等价于用数个$0$将原串分为数个长度为$0$到$k-1$的连续$1$子串。我们设$f_{i,j}$为考虑到第$i$位时，这一位是一个长度为$j$的连续$1$子串的结尾的概率，其中$0 \le j < k$。直接求是$O(n^2)$的，观察递推式，有$$ f_{i,j} = \begin{cases} f_{i-1,j}, &j=0 \\ f_{i-1,j} \times p, &j>0 \\ \end{cases} $$