【NOIP模拟】T1 发电机（递推逆元+期望）

期望是有线性性质的

考虑每个点的概率

由于一个点的子树放了后 它就不能再放了

换句话说 这个点是子树中第一个通电的

也就是说这个点的通电概率是\(\frac{1}{size[i]}\)

题目中又说了每个点的编号大于儿子们 于是就不用dfs了 只需递推即可 把所有点的概率相加

那还要求出逆元 这里提供一种逆元的线性递推方式

#include<bits/stdc++.h> #define mod 998244353 #define N 10000005 #define ll long long using namespace std; ll n,fa[N],inv[N],size[N],ans; int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); cin>>n;for(int i=2;i<=n;i++) cin>>fa[i];inv[1]=1;for(ll i=2;i<=n;i++) inv[i]=mod-mod/i*inv[mod%i]%mod; //递推逆元 for(int i=n;i>=1;i--) size[fa[i]]+=(++size[i]), ans+=inv[size[i]];cout<<ans%mod;return 0; }

转载于:https://www.cnblogs.com/Patrickpwq/articles/9804849.html

总结

以上是生活随笔为你收集整理的【NOIP模拟】T1 发电机（递推逆元+期望）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。