HDU6747 Rotate 期望_综合

题目描述

我们有一个圈，从内到外一共被分成了 n 个环，中间是空的。

我们把从外到内第 i 层环平分成 a[i] 份，其中 a[i] 是偶数，我们把这 a[i] 份黑白染色，第奇数个染成黑色，第偶数个染成白色。

现在我们旋转每一层，每一层都会等概率随机到一个中止位置。

问黑色的联通块数目的期望。两块黑色的区域有交点即算联通。层之间的旋转是相互独立的。

$1\leq n \leq 10,1 \leq a_{i} \leq 1000,1 \leq T \leq 10$

分析

$联通块的数量=所有的层的黑块数目-每层之间的黑边$
黑块的数目和为 $\sum\limits_{i=1}^{n} \frac{a_{i}}{2}$ 考虑每层黑边的期望数目
对于任意两层的任意两个黑块，他们相交的概率是 $\frac{1}{a_{i}} + \frac{1}{a_{i+1}}$ ，乘上他们的块数，就是期望的相交个数。
$Ans = \sum\limits_{i=1}^{n} \frac{a_{i}}{2} - \sum\limits_{i=1}^{n-1} (\frac{1}{a_{i}} + \frac{1}{a_{i+1}})\frac{a_{i}}{2}\frac{a_{i+1}}{2}=\frac{a[1] + a[n]}{4}$

代码

#include <bits/stdc++.h>#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define PB push_back
#define CL clear
#define int long long
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pii;
const int N = 1e5+10;
const int D = 21;
const int inf = 1e9;
const int mod = 1e9+7;
inline int rd() {char ch = getchar(); int p = 0; int f = 1;while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}return p*f;
}int a[N];int qpow(int x,int k,int mo) {int s = 1;while(k) {if(k&1) s=s*x%mo;x=x*x%mo; k>>=1;}return s;
}signed main() {int t = rd();while(t--) {int n = rd();for(int i=1;i<=n;i++) a[i] = rd();printf("%lld\n",qpow(4ll,mod-2,mod) * (a[1] + a[n]) % mod ); }return 0;
}