Codeforces 1025G Company Acquisitions (概率期望)

题目链接

https://codeforces.com/contest/1025/problem/G

题解

什么神仙题……
结论：定义一个有 (k) 个儿子的点的势能为 (2^k-1)，一个状态的势能等于所有点的势能总和，答案等于终止状态的势能（(2^{n-1}-1)）减去初始状态的势能（(sum^n_{i=1}2^{sonn_i}-1)）。
证明：考虑每次操作后一个状态的期望势能变化：假设两个自由状态的点儿子个数分别为 (x,y)，则期望势能变化为 (frac{(2^{x+1}-1)+(2^{y+1}-1)}{2}-(2^x-1+2^y-1)=1). 因此每次操作期望势能变化为 (1)；设从 (0) 到 (x) 的期望操作次数为 (f(x))，则对于所有的实数 (x)，(f(x)) 的关系可以描述为线性方程组，该方程组有唯一解，且 (f(x)=x) 是该方程组的一组解（带入验证），故 (f(x)=x).
即总共期望操作次数为末势能减初势能。直接计算即可。
时间复杂度 (O(n)).

代码

#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_dolor
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 500;
const int P = 1e9+7;
int cnt[mxN+3];
int n;

llong quickpow(llong x,llong y)
{
	llong cur = x,ret = 1ll;
	for(int i=0; y; i++)
	{
		if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}
		cur = cur*cur%P;
	}
	return ret;
}

int main()
{
	n = read();
	for(int i=1; i<=n; i++) {int x = read(); if(x!=-1) {cnt[x]++;}}
	llong ans = quickpow(2ll,n-1)-1;
	for(int i=1; i<=n; i++) {ans = (ans-quickpow(2ll,cnt[i])+1+P)%P;}
	printf("%I64d
",ans);
	return 0;
}