鞅与停时
计数题的小技巧，也许以后会更详细学一学，目前参考价值不高。
直接看题目。
例题：
一共有 \(n\times m\) 张卡，\(n\) 种，每种各 \(m\) 个。手中维持有 \(m\) 张，知道初始的时候每一种牌有 \(a_i\) 个，每次随机一张扔掉，并且在牌堆中随机抽一张，然后把扔掉的牌插入牌堆。问多少次之后能够让手牌只有一种卡。
多次给定 \(a\) 询问。
\(n\le 5000,q\le 200,m\le 10^5\)。
考虑比较简单的做法，这种期望题不妨考虑解方程的形式，设 \(f_i\) 表示 \(i\) 状态还有几步结束，注意到一个事实，我们只关注 \(i\) 的可重集，也就是说排序之后考虑，会发现 \(n\le 17\) 的时候状态数不到 \(300\)。有转移 \(f_u=\sum p_{u\to v}(1+f_v)\)，对着这个高斯消元即可。
对于 \(n=2\) 的时候，会发现可以通过前面一个状态推后面一个，这样可以做到快速计算。
更大一点就是正解了，这里需要引入一个科技
鞅与停时定理
非常非常粗浅的理解。
鞅
如果一个时间离散的随机过程 \(\{ X_0,X_1,X_2\dots\}\) 满足以下两个条件，则称之为鞅
- \(\forall t\in \mathbb{N},\mathbb{E}(|X_t|)<\infty\)，即 \(\mathbb{E}(|X_t|)\) 有限
- \(\forall t\in \mathbb{N},\forall X_0,X_1\dots,\mathbb{E}(X_{t+1}-X_t|X_0,X_1\dots X_t)=0\)
考虑用赌博的过来理解，可以把每一个 \(X\) 视为赌博某个时刻拥有的资金，每一次变换相当于进行了一次赌博。那么第一个限制就是资金期望有限，第二个限制就是，不管之前状态如何新的一局期望收益始终为 \(0\)。
注意到第二个结论可以推到出 \(\forall t\in\mathbb{N},\mathbb{E}(X_t)=\mathbb{E}(X_0)\)。
停时
随机过程可能有一个终止的时间，但是这个时间可能有多种可能，比如说在数轴上随机游走，走到某个点就停止，那么这个停止时间就是随机的。称这个随机变量为停时。
停时需要满足，通过 \(0-T\) 时刻的所有的信息可以判断 \(T\) 时刻是否停下。
鞅与停时定理
考虑鞅的停时，设 \(T\) 是鞅 \(\{ X_0,X_1,X_2\dots\}\) 的一个停时，以下三者之一成立的时候，有 \(\mathbb{E}(X_T)=\mathbb{E}(X_0)\)。
- \(T\) 几乎一定有界
- \(\forall t\in \mathbb{N},|X_{t+1}-X_t|\) 一致有界，\(\mathbb{E}(T)\) 有限
- \(\forall t\in \mathbb{N},X_t\) 一致有界，\(T\) 几乎一定有限
其中有一些高级的词语，几乎一定的意思为 \(\mathbb{P}(x)=1\)，有限的意思为 \(<\infty\)，有界的意思为 \(\exists l,r,l\le x\le r\)。
我目前也不太会证明，一般题目要求的都是 \(\mathbb{E}(T)\) 因此可以认为题目中这个定理始终成立。
势能函数
OI 中的最常见的应用。
构造函数 \(\varphi(X)\) 满足：
\[\forall t\in \mathbb{N},\mathbb{E}(\varphi(X_{t+1})-\varphi(X_t)|X_0,X_1\dots X_t)=-1 \]可以理解为一个刻画变化过程的函数。
这个时候就可以利用鞅与停时定理了，令 \(Y_i=\varphi(X_i)+i\)，不难发现 \(Y\) 是一个鞅。直接用定义法证明即可。
那么就会有优秀的性质 \(\mathbb{E}(Y_T)=\mathbb{E}(Y_0)\)
展开分析，利用期望的线性性。
\[\begin{aligned} \mathbb{E}(Y_T)&=\mathbb{E}(Y_0)\\ \mathbb{E}(\varphi(X_T)+T)&=\mathbb{E}(X_0)\\ \mathbb{E}(T)&=\mathbb{E}(X_0)-\mathbb{E}(\varphi(X_T)) \end{aligned} \]注意到 \(\varphi\) 是我们自己构造的，不妨令其为常数，那么最后得到的就是
\[\mathbb{E}(T)=\mathbb{E}(X_0)-\varphi(X_T) \]这就是最常见的应用了，用来计算停时的有用工具。
回到原题，之前提到，我们只关注现在每个种类个数的可重集，那么不妨令 \(f(a)\) 表示一个时候的势能，\(f(a)=\sum\limits_{i=1}^n \varphi(a_i)\) 其中 \(\varphi\) 就是一个构造的函数。
根据上面的过程，对于 \(\varphi\) 进行限制，即 \(\mathbb{E}(f(i+1)-f(i))=-1\)，考虑变化的过程，如果选择 \(i\to j\) 那么相当于 \(f\) 不会改变，也就不会对于 \(\mathbb{E}\) 有贡献。那么只需要关心有共贡献的部分，假设目前每一个有 \(a_i\) 个，令 \(d(i)=\varphi(i)-\varphi(i-1)\)式子写出来就是：
\[\begin{aligned} -1&=\sum_{i\neq j}\dfrac{a_i}{m}\times \dfrac{m-a_j}{(n-1)m}\times (\varphi(a_i-1)-\varphi(a_i)+\varphi(a_j+1)-\varphi(a_j))\\ &=\sum_{i\neq j}\dfrac{a_i}{m}\times \dfrac{m-a_j}{(n-1)m}\times (d(a_j+1)-d(a_i))\\ &=\sum_{i\neq j}\dfrac{a_i}{m}\times \dfrac{m-a_j}{(n-1)m}\times d(a_j+1)-\sum_{i\neq j}\dfrac{a_i}{m}\times \dfrac{m-a_j}{(n-1)m}\times d(a_i)\\ &=\sum_{j=1}^n\dfrac{m-a_j}{m}\times \dfrac{m-a_j}{(n-1)m}\times d(a_j+1)-\sum_{i=1}^n\dfrac{a_i}{m}\times \dfrac{(n-2)m+a_i}{(n-1)m}\times d(a_i) \end{aligned} \]推完式子别忘了，\(d\) 是我们自己构造的， 那么不妨设：
\[\dfrac{m-a_i}{m}\times \dfrac{m-a_i}{(n-1)m}\times d(a_i+1)-\dfrac{a_i}{m}\times \dfrac{(n-2)m+a_i}{(n-1)m}\times d(a_i)=-\dfrac{1}{n} \]这样可以线性构造出来 \(d\)，也就线性得到了 \(\varphi\)。
最后根据鞅与停时定理，得到答案就是 \(ans=f(a)-\varphi(m)\)。
标签：停时,不正经,dfrac,定理,varphi,times,sum,mathbb From： https://www.cnblogs.com/Jryno1-blog/p/18088272