目录
问题概述
原题参考：D.Good Trip
大致意思就是一个老师带着n个孩子，其中有m对是朋友，每对朋友之间有一个友谊值，不是朋友的则是0，这个老师要出去玩k次，每次可以带上两个小朋友(为什么不能一起带，这是偏爱！！！)，如果这两个小朋友是朋友关系的话，那么他们的友谊值会加1，如果不是的话，就不变，要求给出k次游玩带出去的小朋友的友谊值的期望值，已经证明该值可以表示为p/q，要求的是输出p/qmod1e9+7
Input:
4
100 0 24
2 1 10
1 2 1
3 1 2
2 1 1
5 2 4
1 2 25
3 2 24
Output:
0
55
777777784
40000020
思路想法
诶，写的时候想法就是完全错误的，就想着将这k次期望做成一个整体，但是写来写去公式又不对，忘了一件事和差期望无条件打开，如果将这k次的期望分开来算，之后加起来也是一样的，同样的，每次的期望又可以分为两个部分，一是孩子的友谊值的期望，一是友谊值变化的期望，分成两个部分就很好做了
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
int n, m, k;
//快速幂求逆元操作
ll qpw(ll a, ll b, ll p) {
ll res = 1;
a %= p;
while(b) {
if(b&1) res *= a, res %= p;
b >>= 1;
a *= a, a %= p;
}
return res;
}
void solve() {
cin >> n >> m >> k;
ll b, s = 0;
b = qpw(n*(n-1)%mod, mod-2, mod);
int x, y, z;
//记录友谊值总和
for(int i=1; i<=m; i++) cin >> x >> y >> z, s += z, s %= mod;
ll ans = 0;
for(int i=1; i<=k; i++) {
//每次的友谊值期望就是抽到m对朋友的概率乘以友谊值总和
ans += 2 * b % mod * s % mod, ans %= mod;
s += 2 * m * b % mod, s %= mod;
}
cout << ans << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
问题反思
为什么想写这道题呢(请看该分类的名称)，其实是期望这玩意我总是算不对，做题的时候又喜欢钻牛角尖，所以写写加加印象，记住期望的和差无条件打开，二是nnd写这个的时候又爆了一次数据，记录一下，最开始的n是int的，之后交了一发cf提示爆数据了，我还在想哪里能爆，结果就是计算逆元的那个中间过程又爆掉了！！！气死我了，又是计算过程爆数据