[BZOJ 5091][Lydsy0711月赛]摘苹果

danihao123 posted @ 2018年3月23日 16:32 in 题解 with tags BZOJ 概率与期望 , 526 阅读
转载请注明出处:http://danihao123.is-programmer.com/

秒,秒啊.jpg

首先根据期望线性性,每个点的期望可以分开算。不妨设\(f_{i, j}\)表示\(j\)在某个第\(i\)步被走到的概率。那么每个点\(j\)的期望访问次数就是\(\sum_{i = 0}^k f_{i, j}\)。

然后考虑去求那个\(f_{i, j}\)。显然\(f_{0, j} = \frac{d_j}{2m}\)。但是考虑\(f_{1, j}\)的转移方程:

\[f_{1, j} = \sum \frac{f_{0, u}}{d_u}\]

然后展开之后发现每个\(\frac{f_{0, u}}{d_u}\)都是\(\frac{1}{2m}\),于是乎\(f_{1, j} = \frac{d_j}{2m}\)。

如此一来,对于任意\(i\),都有\(d_{i, j} = \frac{d_j}{2m}\),然后就很好做了……

代码:

/**************************************************************
    Problem: 5091
    User: danihao123
    Language: C++
    Result: Accepted
    Time:532 ms
    Memory:2384 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1);
  ans = (ans * ans) % ha;
  if(1LL & b) ans = (ans * a) % ha;
  return ans;
}
ll inv(ll v) {
  return pow_mod(v, ha - 2LL);
}
 
const int maxn = 100005;
ll a[maxn], d[maxn];
int main() {
  int n, m, k; scanf("%d%d%d", &n, &m, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &a[i]);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    d[u] ++; d[v] ++;
  }
  ll ans = 0;
  ll inv_2m = inv(2 * m);
  for(int i = 1; i <= n; i ++) {
    ans += (((d[i] * inv_2m) % ha) * a[i]) % ha;
    if(ans >= ha) ans -= ha;
  }
  ans = (ans * (ll(k))) % ha;
  printf("%lld\n", ans);
  return 0;
}
UK Board Model Paper 说:
Aug 30, 2022 04:09:34 PM

Students Download Uttarakhand 10th Model Paper 2023 at Official Website Only, UBSE Announce its 10th Results in Month of Jun, High School Students across Uttarakhand Board are advised to Visit this Board page on Regular basis to get their Uttarakhand 10th Practical Exam Question Paper 2023. UK Board Model Paper so if you are also among those students who have Registered them self as a Regular or Private Student are Suggested to Download these Uttarakhand Board 10th Sample Paper 2023 must Prepare all Subjects. Model Papers are very helpfull Material that is Provided by the official education Board.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter