【模拟7.14】B. 熟练剖分(tree) (概率DP)

一道概率神题，考试时没读清题考完看了学长的玄学题解看了好几个小时

首先f[i][j]表示在点 i 为根的子树中,向下最长轻链长度小于等于 j 的概率。

首先递归下去并求出子树大小，然后枚举重儿子，枚举该点最长轻链长度，再次枚举儿子节点并逐个

假设当前枚举的重儿子是to1，枚举到儿子节点to2，x最长轻链长度为k，设gs为v（to2）之前考虑的儿子中最长轻链长度为k的概率如果v（to1）=v（to2）即v（to2）为重儿子，则设fs为以v（to2）为根的子树最长轻链长度为k的概率:

h[k]=(fs*g[k]%mod+gs*f[to2][k]%mod-gs*fs+mod)%mod;

如果v（to2）是轻儿子，则设fs为以v（to2）为根的子树最长轻链长度为k-1的概率，

h[k]=(fs*g[k]%mod+gs*f[to2][k-1]%mod-gs*fs+mod)%mod;

只是x与to2相连的这条边为轻链所以有减1，值得提醒的一点是这里的f[x][k]并不是最终的f[x][k]，只是考虑到当前几个儿子时的值，一个儿子一个儿子地向里加。考虑到f数组直接改的话会错，所以用h数组保存，最后加到g数组中清空h，当to1为重儿子这个情况考虑玩后将g数组加到f中去，清空g。当前节点x求完后，此时的f数组并不是前缀和，所以需要再次转化。

最后求答案时再次将前缀和转化为单个的值

至于此题为啥求概率却用一堆整数想乘是因为题目要求

我们发现每一层的1/chu[x]即为分母，所以可以直接乘逆元，而这样的相加不会影响结果

所以最后i*f[x][i]就是期望。

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<string>

  5 #include<algorithm>

  6 #include<vector>

  7 #include<cmath>

  8 #include<stack>

  9 #include<queue>

 10 #define MAXN 3101

 11 #define ll long long

 12 using namespace std;

 13 const ll mod=1e9+7;

 14 struct node{ll to,n;}e[MAXN];

 15 ll head[MAXN],tot;

 16 void add(ll u,ll v){e[++tot].to=v;e[tot].n=head[u];head[u]=tot;}

 17 ll size[MAXN];

 18 ll f[MAXN][MAXN],g[MAXN],h[MAXN];

 19 ll n;ll chu[MAXN];

 20 ll pow(ll x,ll y)

 21 {

 22     ll ans=1;

 23     while(y)

 24     {

 25        if(y&1)ans=(ans*x)%mod;

 26        x=(x*x)%mod;

 27        y>>=1;

 28     }

 29     return ans%mod;

 30 }

 31 void DFS(ll x)

 32 {

 33    size[x]=1;

 34    for(ll i=head[x];i;i=e[i].n)

 35    {

 36        ll to=e[i].to;

 37        DFS(to);

 38        size[x]+=size[to];

 39    }

 40    ll ppow=pow(chu[x],mod-2ll)%mod;

 41    for(ll i=head[x];i;i=e[i].n)

 42    {

 43        for(ll i=0;i<=size[x]+1;++i)g[i]=1;

 44        for(ll j=head[x];j;j=e[j].n)

 45        {

 46            ll fs,gs;

 47            ll to1=e[i].to;ll to2=e[j].to;

 48            for(ll k=0;k<=size[to2]+1;++k)

 49            {

 50                if(to1==to2){

 51                    if(!k)fs=f[to2][k];else fs=f[to2][k]-f[to2][k-1];

 52                    if(!k)gs=g[k];     else gs=g[k]-g[k-1];

 53                    h[k]=(fs*g[k]%mod+gs*f[to2][k]%mod-gs*fs+mod)%mod;

 54          //          printf("h[%lld]=%lld\n",k,h[k]);

 55                }

 56                else if(k){

 57                    if(!k)fs=f[to2][k-1];else fs=f[to2][k-1]-f[to2][k-2];

 58                    if(!k)gs=g[k];       else gs=g[k]-g[k-1];

 59                    h[k]=(fs*g[k]%mod+gs*f[to2][k-1]%mod-gs*fs+mod)%mod;

 60                }

 61            }

 62            g[0]=h[0];h[0]=0;

 63            for(ll k=1;k<=size[to2]+1;++k)

 64            {

 65                g[k]=(g[k-1]+h[k])%mod;h[k]=0;

 66            }

 67        }

 68        for(ll j=size[x]+1;j>=1;--j)

 69        {

 70            g[j]=(g[j]-g[j-1]+mod)%mod;//printf("g[%lld]=%lld\n",j,g[j]);

 71        }

 72        for(ll j=0;j<=size[x]+1;++j)

 73        {

 74            f[x][j]=(f[x][j]+g[j]*ppow%mod)%mod;

 75        //  printf("f[%lld][%lld]=%lld\n",x,j,f[x][j]);

 76        }

 77        // printf("p=%lld\n",pow(chu[x],mod-2ll));

 78    }

 79    if(head[x]==0)f[x][0]=1;

 80    for(ll i=1;i<=size[x]+1;++i)

 81    {

 82         f[x][i]=(f[x][i]+f[x][i-1]+mod)%mod;

 83        // printf("f[%lld][%lld]=%lld\n",x,i,f[x][i]);

 84    }

 85 }

 86 ll ru[MAXN];ll si=1;

 87 int main()

 88 {

 89      scanf("%lld",&n);

 90      for(ll i=1;i<=n;++i){

 91         scanf("%lld",&chu[i]);

 92         for(ll j=1;j<=chu[i];++j){

 93             ll y;

 94             scanf("%lld",&y);

 95             add(i,y);ru[y]++;

 96         }

 97      }

 98      ll root=0;

 99      for(ll i=1;i<=n;++i){

100         if(ru[i]==0)

101          root=i;

102      }

103      DFS(root);

104      ll ans=0;

105      for(ll i=1;i<=size[root]+1;++i)

106      {

107          ans=(ans+i*(f[root][i]-f[root][i-1]%mod)+mod)%mod;

108      }

109      printf("%lld\n",(ans+mod)%mod);

110 }

巴特西

【模拟7.14】B. 熟练剖分(tree) (概率DP)

最新文章

热门文章