Cptraser/ 三月 11, 2019/ 2019.3/ 0 comments

题面传送门
min(S)S中最先到达点的期望,max(S)S中走完的期望;

容易想到DP,对于点集为S的询问,设f_i为从i走到S中任意一点的期望;

    \[f_i=\frac{1}{deg_i} * \sum_{(i,j)\in E}f_j+1\]

deg_ii点的度数;

这玩意有后效性,需要解方程,即高斯消元;

但可以根据树的性质来优化:

这个式子实际上与儿子与父亲有关,可改写为

    \[f_i=\frac{1}{deg_i} * (\sum_{j\in Son_i}f_j+f_{fa_i})+1\]

从叶往根上推,对于叶子节点,Son_i=\empty,则式子为

    \[f_i=f_{fa_i}+1\]

那么从下往上第二层的式子为

    \[f_i=\frac{1}{deg_i} * [(deg_i-1) * f_i+deg_i-1+f_{fa_i}]+1\]

移项得

    \[\frac{1}{deg_i}f_i=f_{fa_i}+2-\frac{1}{deg_i}\ f_i=deg_i * f_{fa_i}+2 * deg_i-1\]

于是发现f_i可以表示成a_i * f_{fa_i}+b_i的形式;

    \[f_i=\frac{1}{deg_i} * (\sum_{j\in Son_i}a_j * f_i+\sum_{j\in Son_i}b_j+f_{fa_i})+1\]

解得

    \[<span class="ql-right-eqno"> (1) </span><span class="ql-left-eqno">   </span><img src="https://cptraser.cf/wp-content/ql-cache/quicklatex.com-edb1e320331950d65716d1ea56212e94_l3.png" height="29" width="220" class="ql-img-displayed-equation quicklatex-auto-format" alt="\begin{equation*} \left{ \begin{array}{rcl} a_i=\frac{1}{deg_i-\sum a_j}\ b_i=\frac{\sum b_j+1}{deg_i-\sum a_j}\ \end{array} \right. \end{equation*}" title="Rendered by QuickLaTeX.com"/>\]

又因为f_{Rt}没有父亲,则f_{Rt}=b_{Rt},那么令Rt=xmin(S)就等于b_x

然后min-max容斥即可.

#include <cstdio>
using namespace std;

const int Mod=998244353,Maxn=20;

int A[Maxn],B[Maxn],G[1<<Maxn];
int N,Q,Rt,t,deg[Maxn],F[Maxn],Cot[1<<Maxn|5];
int x,y,head[Maxn],nxt[Maxn<<1],to[Maxn<<1],Cnt;
#define Add(x,y) (nxt[++Cnt]=head[x],to[Cnt]=y,head[x]=Cnt)

int Ksm(int x,int y){int res=1;for(;y;y>>=1,x=1ll*x*x%Mod)if(y&1)res=1ll*res*x%Mod;return res;}

void dfs(int x,int fa,int S){
    A[x]=B[x]=1;long long tot=0,res=0;
    if(S&(1<<(x-1)))return (void)(A[x]=B[x]=0);
    for(int i=head[x];i;i=nxt[i])if(fa^to[i])
        dfs(to[i],x,S),(tot+=A[to[i]])%=Mod,(res+=B[to[i]])%=Mod;
    A[x]=Ksm(deg[x]-tot,Mod-2);
    B[x]=1ll*(res+deg[x])*Ksm(deg[x]-tot,Mod-2)%Mod;
}

void Work(int x){
    dfs(Rt,0,x),G[x]=B[Rt];
}

int main()
{
    scanf("%d%d%d",&N,&Q,&Rt);
    for(int i=1;i<N;i++)scanf("%d%d",&x,&y),Add(x,y),Add(y,x),deg[x]++,deg[y]++;
    for(int i=0;i<(1<<N);i++)Work(i);
    for(int i=1;i<(1<<N);i++)Cot[i]=Cot[i>>1]+(i&1);
    for(;Q;Q--){int tot=0;long long Ans=0;
        scanf("%d",&t);for(int i=1;i<=t;i++)scanf("%d",&x),tot+=1<<(x-1);
        for(int i=tot;i>0;i=tot&(i-1))
            (Ans+=1ll*(Cot[i]&1?1:-1)*G[i]+Mod)%=Mod;
        printf("%lld\n",Ans);
    }
}
Share this Post

Leave a Comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*