題目鏈接

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\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1025G Company Acquisitions (概率期望)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。