description
有 (n) 个人，一开始每个人都未被领导。
每次修改领导情况：等概率随机选择一个未被领导的人 (x)，再等概率随机选择另一个未被领导的人 (y)，令 (x) 被 (y) 领导，并且所有原来被 (x) 领导的人的状态变为未被领导。直到只剩下一个人未被领导（即其他所有人都被这个人领导）为止。
问修改领导情况的期望次数。
solution
利用鞅的停时定理的做法。借鉴了借鉴了借鉴他人博客的博客的博客。
如果你已经对这套理论十分熟悉了，可以跳过前面的吹逼直接进入正题。
由于我的数学水平有限，所以无法保证以下口胡的东西是对的。
鞅？那是什么？
抱歉，那我先溜了。
考虑鞅的定义：
对于离散时间的随机过程（可以理解成一组随机变量）(X_0, X_1,dots) ，如果它满足以下条件，则该随机过程是鞅：
[egin{cases} mathbb E(|X_t|) < infin\ mathbb E(X_{t + 1} - X_t | X_0,dots X_t) = 0 end{cases} ]大多数情况下第一条是显然成立的，重点在于第二条。
关于第二条：(mathbb E(X_{t + 1} - X_t | X_0,dots X_t) = 0 Rightarrow mathbb E(X_{t+1})=mathbb E(X_t))，但反之不一定成立（随机变量之间可能并不独立）。
可以理解成，不管 (X_0,X_1dots,X_t) 的观测的结果如何，都有 (mathbb E(X_{t+1})= X_t)（这里的 (X_t) 是已经观测得到的定值）。
那么鞅的时停「The world！时よ止まれ！」
那么鞅的停时定理可以描述为：
那么问题来了，什么是停时呢？
停时是一个随机变量 ( au)：如果观测 (X_0,X_1dots, X_N) 就可以确定 ( au = N)，则 ( au) 是一个停时。
举个图随机游走问题的例子：第一次到达终点的时刻显然是停时；而最后一次到达终点的时刻，由于通过观测 (X_0, X_1 dots, X_N) 你并不知道这一次是否为最后一次，所以它不是停时。
事实上，对于某确定的时刻 (t)，显然有 (mathbb E(X_t) = mathbb E(X_0))。然而停时本身是随机变量，且不一定与 (X_i) 独立，所以停时定理并非显然的。
停时定理有三个条件，满足其中之一即可使用。不过由于我一个都没看懂就不贴了。
如何利用这一工具？首先我们先假设以下情景满足停时定理的条件的。
如果有一组随机变量 (Y_0,Y_1,dots)，我们想要求解 (mathbb E( au))（注意停时本身是随机变量）。
考虑构造另一组随机变量 (X_0,X_1,dots) 使得它满足 (X_t = Y_t + t)。
如果 (Y) 满足 (mathbb E(Y_{t + 1} - Y_t | Y_0,dots Y_t) = -1)，则 (X) 是鞅，因此有 (mathbb E(X_{ au}) = mathbb E(X_0))，即 (mathbb E( au) = mathbb E(Y_0) - mathbb E(Y_{ au}))（由期望的线性性）。
但是怎么可能直接给你一组随机变量求停时啊。
考虑图随机游走问题，定义停时为第一次到 ( au) 的时刻，假设起点为 (S)，终点为 (T)。
我们定义随机事件 (A_t) 表示第 (t) 步到达的点，再对于每个点定义一个势能函数 (phi(x))，则 (Y_t = phi(A_t)) 是一组随机变量。
考虑 (Y_t) 的停时，可以定义成第一次出现 (phi(T)) 的时刻。
可以发现 (A_t) 只和 (A_{t-1}) 有关，即 (mathbb E(Y_t |A_0dots A_{t-1}) = mathbb E(Y_t | A_{t-1}))。
如果有 (mathbb E(Y_{t+1} - Y_t | A_t) = -1)，则根据上文有 (mathbb E( au) = mathbb E(Y_0)-mathbb E(Y_{ au}))。
特别地，(A_0 = S, A_{ au} = T)，所以 (mathbb E( au) = phi(S)-phi(T))。
为了保证 (phi) 的存在，我们把 (T) 向外的边改成自环。这样总存在一个平凡的 (phi(x) = mathbb E( au_x))。
同时为了保证 (Y) 的停时与 (A) 的停时一一对应，需要保证 (forall x ot=T,phi(x) ot=phi(T))。
考察条件 (mathbb E(Y_{t+1} - Y_t | A_t) = -1)，它即 (phi(A_t) = sum_x p_{A_t,x} imes phi(x) + 1)（(A_t) 是已经观测得到的定点）。
其实就是 (phi(x) = sum_y p_{x,y} imes phi(y) + 1 Rightarrow phi(x) = phi(T) + mathbb E( au))，草我为什么突然间感觉这就是废话。
回到本题。首先这个题本质即图随机游走问题。
定义状态为可重集 ({a_1, a_2, dots, a_k})，表示现在有 (a_1, a_2, dots a_k) 个人分别被 (k) 个人领导。
考虑对于构造 (phi({a_1, a_2, dots, a_k}))，为了与暴力区别我们令 (phi({a_1, a_2, dots, a_k})=sum_{i=1}^{k}f(a_i))，有：
由于是恒等式，我们只需要知道任意一种合法的 (f) 即可。
因此构造 (f_0 = 0, f_{n+1}=2 imes f_n-1) 即可，即 (f_n = 1-2^n)。
简单验证一下 (phi({n-1})) 的唯一性：它是所有 (phi) 中的最大值。
然后这道题终点没有出边，所以直接做即可。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 500;
const int P = int(1E9) + 7;
inline int add(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int sub(int x, int y) {x -= y; return x < 0 ? x + P : x;}
inline int mul(int x, int y) {return (int)(1LL * x * y % P);}
int mpow(int b, int p) {
int r; for(r = 1; p; p >>= 1, b = mul(b, b))
if( p & 1 ) r = mul(r, b);
return r;
}
int c[N + 5], a[N + 5], n;
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
if( a[i] != -1 ) c[a[i]]++;
}
int phi0 = 0;
for(int i=1;i<=n;i++)
phi0 = add(phi0, sub(1, mpow(2, c[i])));
int phiT = sub(1, mpow(2, n - 1));
printf("%d
", sub(phi0, phiT));
}
details
想了大半天感觉这不用鞅的停时定理也能感性解释？
懂了，我没学过概率论，告辞。
类似的题还有 codeforeces - 1349D。不过关于这一套理论其实还有很多坑我没有弄懂，比如最关键的适用条件，感觉还模模糊糊地不太明白。