概率期望计数DP

• [] CF235B Let’s Play Osu! 同时维护期望和平方的期望，比较简单，但是要注意的坑点就是期望的平方不等于平方的期望
• [] CF398B Painting The Wall 还是记录还剩x行y列的时候的期望，然后考虑4种情况递推回去，千万注意不要写漏了。此题较不错
• [] CF839C Journey 水
• [] CF559C 做法比较巧妙的一道题，如果不考虑限制的话,那么方案数就是$C_{m+n-2}^{n-1}$，但是现在我们来考虑限制，假设$dp[i]$表示把每个不合法点按x排序以后，走到第x个点且不走不合法点的方案总数那么$dp[i]=C_{x_i+y_i-2}^{x_i-1}-\sum C_{xi-xj+y_i-y_j}^{x_i-x_j}$然后把终点看做n+1号不合法点做就好了。此题较不错
• [] CH5E26 SCOI2008着色方案 其实是一道题，记还剩12345个涂色机会的油漆种类的方案数，然后记忆化搜索。此题较不错
• [] CH3803 其实和上面差不多，还是记录剩1234张牌的牌的种类数，然后DP，对于大小王，分类讨论，取最小，最后加上概率就好了。此题较不错
• [] CH3801 概率期望题 对于与和或 记last[i]为数字i上一次出现的位置，对于长度为1的区间概率是$\frac{1}{n^2}$其他区间是$\frac{2}{n^2}$然后讨论上一位的位置，计算贡献，对于异或的处理比较麻烦，是转化为有奇数偶数个1的区间来算的，见题解