【数论】Codeforces1025G Company Acquisitions_综合

题意：

有n个节点，每个节点有两种状态：选中和未选中。

每个选中的点后面都跟着若干个（可能是0个）未选中的点。

每个未选中的点都一定跟在某个选中的点后面。

每次操作随机选择两个被选中的点，随机将其中一个变成未选中，且跟在另一个后面，同时将跟在他后面的节点全部改为选中。

求这样操作下去，直到最后只剩一个选中的点的期望步数。

分析：

非常有趣的一道数论题：
设一个点后面跟着k个被选中的点，设其的势能函数为： $2^k-1$
这样一来，目标状态的势能函数值就是 $2^{n-1}-1$

这样定义势能函数的优点是：
对每一次操作，计算它的势能函数期望变化量，惊人地发现：
设第一个点后有 $x$ 个节点，另一个后有 $y$ 个节点
$\Delta=\frac 1 2\times((2^{p+1}-1)-(2^p-1)-(2^q-1))+\frac 1 2\times ((2^{q+1}-1)-(2^p-1)-(2^q-1))=1$

也就是说，势能函数的期望变化量为1，那么整个的期望步数就是目标状态的势能函数，减去当前状态的势能函数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 510
#define MOD 1000000007
using namespace std;
int bit[MAXN];
int u,cnt[MAXN],n;
int main(){SF("%d",&n);bit[0]=1;for(int i=1;i<=n;i++)bit[i]=(bit[i-1]<<1)%MOD;for(int i=1;i<=n;i++){SF("%d",&u);if(u!=-1)cnt[u]++;}int ans=bit[n-1]-1;for(int i=1;i<=n;i++){ans=(ans-(bit[cnt[i]]-1))%MOD;}PF("%d",(ans+MOD)%MOD);}