OI - Company Acquisitions(Codeforces)

然而势能函数觉得自己不止可以分析时间复杂度……

---

# 题面

> Codeforces 1025G

点击展开/折叠题面

有 $n$ 个公司，每个公司要么是独立的，要么附属于一个独立的公司。

每天会发生一个事件：随机选择两个不同的独立的公司 $A,B$，$A$ 有一半的概率吞并 $B$，$B$ 也有一半的概率吞并 $A$。若一个公司 $P$ 吞并了另一个公司 $Q$（在此之前 $P,Q$ 是独立的），则 $Q$ 成为 $P$ 的附属公司，而原来所有附属于 $Q$ 的公司变为独立的。

给出初始时公司的附属情况，求期望经过多少天，只剩下一个独立公司。

---

# 解析

定义状态 $S$ 为一个可重集合，集合内包含了每个独立公司的附属公司的数量。显然这种状态是可以进行转移的，设发生一次事件后转移到的状态为 $T$，即从 $S$ 中选择两个数 $s_p,s_q$：

若 $p$ 吞并 $q$，则 $S$ 中删除 $s_q$，$s_p$ 增加 $1$，并且新加入 $s_q$ 个 “$0$”；$q$ 吞并 $p$ 类似。

目标状态为 $S=\{n-1\}$。

我们发现这个状态数量庞大，因此需要用一种函数来统一这些状态。

定义 $S$ 的势能函数为 $f(S)$：

$$f(S)=\sum_{s_i\in S}(2^{s_i}-1)$$

考虑发生一次事件后，$S$ 的势能函数期望改变量，即考虑任意一对独立公司发生吞并事件（假设两公司的附属公司数量分别为 $p,q$）：

• 若 $p$ 吞并 $q$，则 $\Delta f(x)=(2^{p+1}-1)-(2^p-1)-(2^q-1)$
• 若 $q$ 吞并 $p$，则 $\Delta f(x)=(2^{q+1}-1)-(2^p-1)-(2^q-1)$

因为两种结果的概率均为 $\frac12$，所以期望改变值整理可得

$$\begin{aligned} \Delta f(x)&=\frac12[(2^{p+1}-1)+(2^{q+1}-1)]-(2^p-1)-(2^q-1)\\ &=1 \end{aligned}$$

也就是说无论哪两个公司发生合并事件，$f(S)$ 的改变值都为 $1$……所以两个状态的势能函数相差多少，期望天数就是多少。

设起始状态为 $S_1$，结束状态为 $S_2$，则期望为 $f(S_2)-f(S_1)$。

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

void Read(int &x){
	x=0;int c=getchar(),b=1;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	x*=b;
}

#define cs const int &
const int MOD=1e9+7,N=505;
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return int(1ll*a*b%MOD);}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

int n;
int cnt[N];

int main(){
	Read(n);
	for(int i=1,tmp;i<=n;i++){
		Read(tmp);
		if(~tmp) cnt[tmp]++;
	}
	int now=0;
	for(int i=1;i<=n;i++)
		if(cnt[i])
			now=Add(now,Sub(Pow(2,cnt[i]),1));
	printf("%d\n",Sub(Sub(Pow(2,n-1),1),now));
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &写意的风景被冲刷\\ &工笔的线条\ 勾不出未来\\ &繁世岑静后\ 洗铅华\\ &万物归一恰似\ 水墨画\ ”\\ ——&\text{《忆墨》By 洛天依/乐正绫} \end{split}$$

> Linked 忆墨-网易云