• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Random Access Iterator

admin

11月 28, 2021

Random Access Iterator

树型概率DP

dp[u]代表以当前点作为根得到正确结果的概率

将深度最深的几个点dp[u]很明显是1

然后很简单的转移

有k次,但我们要先看一次的情况,然后再推到k次,k次中只要有一次就可以正确,所以求出k次全失败的概率,用1去减即可

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn = 1e6+7;
const int mod = 1e9+7;
vector<int>G[maxn];
int d[maxn],maxx;
ll dp[maxn];
ll qpow(ll n,ll k){
    ll res=1;
    while(k){
        if(k&1) res=res*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return res;
}
void get_d(int u,int fa){
    d[u]=d[fa]+1;
    maxx=max(d[u],maxx);
    for(int v:G[u]){
        if(v==fa) continue;
        get_d(v,u);
    }
}
void dfs(int u,int fa){
    if(d[u]==maxx){
        dp[u]=1;
        return;
    }
    ll tmp=(ll)G[u].size();
    if(u!=1) tmp--;
    if(tmp==0) return;
    ll q=qpow(tmp,mod-2);
    for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u);
        dp[u]=(dp[u]+dp[v]*q%mod)%mod;
    }
    dp[u]=(1ll-dp[u]+mod)%mod;
    dp[u]=(1ll-qpow(dp[u],tmp)+mod)%mod;
}
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    get_d(1,0);
    dfs(1,0);
    printf("%lld
",dp[1]);
    return 0;
}

《Random Access Iterator》有2个想法
  1. Hey! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get my website
    to rank for some targeted keywords but I’m not seeing very good results.
    If you know of any please share. Thanks! I saw similar text here: GSA Verified List

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注