对于从三个方向转移的期望DP式子移项方法
对于从三个方向转移的期望dp式子移项方法
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753059
，其中 ，求
考虑差分，
注意到 ，因此可以把 消掉
然后就可以推出 的递推式，然后反求 即可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-09
差分构造法推广：arc166_d
差分构造法推广：arc166_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133694378 https://atcoder.jp/contests/arc166/tasks/arc166_d 首先肯定是这样子放： 考虑相邻之间的差，本质就是橙色区间减蓝色区间数量 区间数量越少显然越优，所以我们要么保留橙区间，要么保留紫区间，然后两两匹配 12345678910111213141516171819202122232425262728293031323...
2023-10-18
杨辉三角按列求和
杨辉三角按列求和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133906909 假设求杨辉三角这一列 我们考虑这个格子： 然后对其不断展开 综上： ∑i=0n(ik)=(n+1k+1)\sum_{i=0}^n\binom i k=\binom {n+1}{k+1} i=0∑n(ki)=(k+1n+1) ∑i=lr(ik)=(r+1k+1)−(lk+1)\sum_{i=l}^r\binom i k=\binom{r+1}{k+1}-\binom...
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-08
【HDU 7015 Another String】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15663221.html 题目链接 题目 Define the distance between two strings of the same length as the numbers of the positions where the characters differ in these two strings. If two strings of the same length has a distance of no more tha...
2023-10-10
期望+拆贡献+充斥：CF1349D
期望+拆贡献+充斥：CF1349D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187 第一步：找性质 每个人的期望步数只与总数量 mmm ，总人数 nnn ，自己数量 aia_iai 有关 第二步：转化（难点） 拆贡献：拆成每个人win的期望步数，然后求 ∑E(i)\sum E(i)∑E(i) 容斥：肯定不能直接算。于是考虑算直到第 iii 个人拿完才结束的的期望步数 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， ...
2024-10-07
1006C简单题（计数式子的组合意义 + DP式子联立）
1006C简单题（计数式子的组合意义 + dp式子联立） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338 http://cplusoj.com/d/senior/p/SS241006C 对于这个式子，我们可以从它的组合意义入手。 假设我们有 n+1n+1n+1 个白球要染色，中间有一个绿球，绿球左边有 aaa 个红球，右边有 bbb 球。染完后绿球左边每个白球有 xxx 的贡献，右边每个白球有 yyy 的贡献。 但接下来怎么做呢？这列出来...