对于从三个方向转移的期望DP式子移项方法
对于从三个方向转移的期望dp式子移项方法
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753059
，其中 ，求
考虑差分，
注意到 ，因此可以把 消掉
然后就可以推出 的递推式，然后反求 即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-12-03
【CF1110E Magic Stones】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640116.html 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones// Contest: Luogu// U...
2023-09-24
交错序列——差分：GZOI2023D2T3
交错序列——差分：GZOI2023D2T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058 单点修改，全局查询交错序列最大值（ max(∑i(−1)ibi)\max(\sum_i (-1)^ib_i)max(∑i(−1)ibi) ）， bbb 为 aaa 的子序列 正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分 考虑 ai−aja_i-a_jai−aj ，本质就是 [j+1,i][j+1,i][j+1,i] ...
2023-09-11
Kruskal重构树+AC自动机+树状数组：Gym - 104542F
Kruskal重构树+AC自动机+树状数组：Gym - 104542F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179 https://vjudge.net/contest/579844#problem/F 看到连边和没有强制在线，考虑Kruskal重构树 看到判断子串，考虑AC自动机+线段树 然后要非常大胆地把两个结合起来。 然后就是大码量了。 具体总结一下流程： 先建出Kruskal重构树 对Kruskal重构树处理...
2021-12-21
【USACO2021 Convoluted Intervals 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716558.html 题目 The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of NNN intervals (1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅105), where the iiith interval star...
2026-07-19
《具体数学》2 Sum Study Note (2)
《具体数学》2 Sum Study Note (2) Repertoire method If we want to calculate : ∑i=1ni2\sum_{i=1}^n i^2∑i=1ni2, we can construct a recursion : {R0=αRn=Rn−1+β+γn+δn2\begin{cases} R_0 = \alpha \\ R_n = R_{n-1} + \beta + \gamma n + \delta n^2 \end{cases} {R0=αRn=Rn−1+β+γn+δn2 And it must satisfy : Rn=A(...
2021-11-14
【洛谷P6835 [Cnoi2020]线形生物】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552685.html 题目链接 明显是道期望dp，设 fi=Ei→i+1f_i=E_{i\rightarrow i+1}fi=Ei→i+1。表示从第 iii 层到第 i+1i+1i+1 层的期望步数。 所以 Ex→y=∑i=xyfiE_{x\rightarrow y}=\sum_{i=x}^yfiEx→y=∑i=xyfi，即从第 xxx 层走到第 yyy 层的总期望步数。 现在推 fxf_xfx, 设 dxd_xdx 为 xxx ...