鞅与停时定理
呆猫不会数学，要证明也是直接抄别人的，不如直接放一篇（
主要写点，对鞅与停时定理的理解
定理与势能函数
对于一个随机过程\(\{X_0,X_1,...,X_t\}\)，其中\(X_t\)是终止状态，对于构造出的函数，设为\(\varphi(X_i)\)，有以下要求：
- \(E(\varphi(X_{i+1})-\varphi(X_i)|X_0,X_1,...,X_i)=-1\)，即随着时间，势能减少
- 要求末状态\(\varphi(X_t)\)唯一对应一个值，即\(\varphi(X_i)=\varphi(X_t)\)当且仅当\(i=t\)
构造序列\(Y_i=\varphi(X_i)+i\)，则\(E(Y_{n+1}|X_0,X_1,...,X_n)=Y_n\)，所以\(Y\)是\(X\)的鞅，那么就有
\[\begin{aligned} E(Y_t)&=E(Y_0)\\ E(\varphi(X_t))+E(t)&=E(\varphi(X_0)) \end{aligned} \]所以\(E(\varphi(X_0))-E(\varphi(X_t))\)就可得到答案
然后\(E(\varphi(X_{i+1})-\varphi(X_i)|X_0,X_1,...,X_i)=-1\)这里不一定是\(1\)，只要是常数就行，如果是其他的数的话只要改一下\(Y_i\)的定义即可
大体方向
大致就是，构造一个势能函数\(F(a_1,a_2,...,a_n)\)，其中\(a_i\)表示每个局面，要使得\(\sum_{\{b_i\}}\frac{E(F(b_1,b_2,...,b_n))}{p_{\{b_i\}}}=E(F(a_1,a_2,...,a_n))-1\)，其中\(\{b_i\}\)是\(\{a_i\}\)的后继状态，\(p_{\{b_i\}}\)是后继为\(\{b_i\}\)的概率，在题目中是等概率的，这里这样写是为了直观
由鞅与停时定理，可知答案为\(E(S)-E(T)\)
这里\(E(F(a_1,a_2,...,a_n))\)就是\(E(\varphi(X_n))\)，\(\sum_{\{b_i\}}\frac{E(F(b_1,b_2,...,b_n))}{p_{\{b_i\}}}\)就是\(E[\varphi(X_{n+1})]\)
其实反过来也行，就\(\sum_{\{b_i\}}\frac{E(F(b_1,b_2,...,b_n))}{p_{\{b_i\}}}=E(F(a_1,a_2,...,a_n))+1\)，答案为\(E(T)-E(S)\)
一般都是设\(F(a_1,a_2,...,a_n)=\sum_{i=1}^nf(a_i)\)，然后构造出\(f(x)\)
例题
CF1025G
显然我们现在的\(a_i\)可以表示为挂在第\(i\)个点下面的节点个数
按理来说，应该列式有\(\sum_{\{b_i\}} f(\{b_i\})-f(\{a_i\})=-1\)，\(luogu\)上好像有这么分析的，但是更多数都是直接去找了两个\(a_i\)和\(a_j\)，设为\(a\)和\(b\)，然后直接列式：
\[\begin{aligned} f(a)+f(b)-1&=\frac{f(a+1)+bf(0)}2+\frac{f(b+1)+af(0)}2\\ &=\frac{f(a+1)+f(b+1)+(a+b)f(0)}2 \end{aligned} \]发现这样实际是要求了任意一组\(a\)，\(b\)的后继差是\(1\)，比原本的要求更严格，是可能没有解的
然后因为势能函数是能我们自己设定的，设\(f(0)=0\)，则得到：
\[f(a)+f(b)-1=\frac{f(a+1)+f(b+1)}2 \]因为\(f(a)\)和\(f(b)\)是对称的，所以得到\(f(a)-\frac12=\frac{f(a+1)}2\)，化一下式子得到\(f(a)-1=\frac{f(a+1)-1}2\)
那么可知\(f(n)=1-2^n\)
CF850F
按照套路，设出\(f(a_i)\)，那么初始就是\(\sum_i f(a_i)\)
设\(sum=\sum_if(a_i)\)，\(s=\sum_ia_i\)，列式：
\[\begin{aligned} -1+sum&=\frac1{s(s-1)}(\sum_{i\neq j}a_ia_j(sum-f(a_i)-f(a_j)+f(a_i+1)+f(a_j-1))+\sum_ia_i(a_i-1)sum)\\ -1&=\frac1{s(s-1)}\sum_{i\neq j}a_ia_j(-f(a_i)-f(a_j)+f(a_i+1)+f(a_j-1))\\ -1&=\frac1{s(s-1)}\sum_ia_i(f(a_i+1)+f(a_i-1)-2f(a_i)) \end{aligned} \]设\(g(x)=f(x+1)+f(x-1)-2f(x)\)，因为\(g(x)\)都对称，所以有：
\[\begin{aligned} -1&=\frac1{s(s-1)}\sum_ia_ig(a_i)\\ &\Rightarrow g(x)=\frac{1-s}{s-x} \end{aligned} \]那么也就有
\[f(x+1)+f(x-1)-2f(x)=\frac{1-s}{s-x} \]设\(h(x)=f(x)-f(x-1)\)，则有
\[h(x+1)-h(x)=\frac{1-s}{s-x} \]想要得到\(f(x)\)，只需对右边那个两次前缀和即可
然后因为\(s\)可能会很大，所以要手推一个式子来算，\(f(a_i)\)倒是都可以递推出来
关于赋初值，看到有几种：
- \(f(0)=f(1)=0\)
- \(f(0)=0\)，\(h(0)=m-1\) \(\righarrow\) \(f(s)=0\)
- \(f(0)=0\)，\(h(1)=-\frac{m-1}m\)
容易发现，几乎可以给\(h(1)/h(0)\)代入任何值，只要满足我们上面说的两点限制即可，具体代什么值看怎么方便，可以保留\(f(0)\)，\(h(0)/h(1)\)到式子中，最后看代什么值好算即可
学长的文章里的这道题就用的这种方式 https://www.cnblogs.com/Illusory-dimes/p/15832042.html#
参考资料（鸣谢）
https://www.cnblogs.com/houzhiyuan/p/17991053
https://www.cnblogs.com/Illusory-dimes/p/15832042.html#
https://www.cnblogs.com/C202044zxy/p/16340757.html
https://www.luogu.com.cn/article/0d1a9nbm
https://www.cnblogs.com/zltzlt-blog/p/18035649
标签：停时,...,frac,定理,varphi,ia,aligned,sum From： https://www.cnblogs.com/LuoyuSitfitw/p/18473413