loj2542「PKUWC2018」随机游走

朱雀 2021-03-28 13:45 419阅读 0赞

#### 题目描述 ####

给定一棵 n*n* 个结点的树，你从点 x*x* 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 Q*Q* 次询问，每次询问给定一个集合 S*S*，求如果从 x*x* 出发一直随机游走，直到点集 S*S* 中所有点都至少经过一次的话，期望游走几步。

特别地，点 x*x*（即起点）视为一开始就被经过了一次。

答案对 998244353998244353 取模。

#### 输入格式 ####

第一行三个正整数 n,Q,x*n*,*Q*,*x*。

接下来 n-1*n*−1 行，每行两个正整数 (u,v)(*u*,*v*) 描述一条树边。

接下来 Q*Q* 行，每行第一个数 k*k* 表示集合大小，接下来 k*k* 个互不相同的数表示集合 S*S*。

#### 输出格式 ####

输出 Q*Q* 行，每行一个非负整数表示答案。

#### 数据范围与提示 ####

对于 20\\%20% 的数据，有 1\\leq n,Q\\leq 51≤*n*,*Q*≤5。

另有 10\\%10% 的数据，满足给定的树是一条链。

另有 10\\%10% 的数据，满足对于所有询问有 k=1*k*=1。

另有 30\\%30% 的数据，满足 1\\leq n\\leq 10 ,Q=11≤*n*≤10,*Q*=1。

对于 100\\%100% 的数据，有 1\\leq n\\leq 181≤*n*≤18，1\\leq Q\\leq 50001≤*Q*≤5000，1\\leq k\\leq n1≤*k*≤*n*。

*  # 题解： #
    
     *  单点询问可以用高斯消元；
     *  这个做法直接扩展到集合的话可以求出到$S$中任意一个点的期望步数；
     *  如果对于一种状态，记录$S$中每个点被走到的步数$t$；
     *  那么$S$中每个点都走到就是$t$的最大值，而刚刚求出来的是$t$的最小值；
     *  套用最值反演：$max\{S\} = \\sum\_\{T \\subseteq S ,T \\neq \\emptyset \}  (-1)^\{|T|-1\} min\{T\}$；
     *  现在只需要快速求出到$S$中任意一个点的期望步数，设$f\_\{u\}$为$u$到$S$的期望步数：
     *  可以得到：  
        
     *  $f\_\{u\} = \\frac\{1\}\{d\_\{u\}\}  \\sum\_\{v\} f\_\{v\} + 1 $
     *  这里$v$表示和$u$相邻的点；
     *  由于是一颗树，单独考虑父亲；
     *  $f\_\{u\} = \\frac\{1\}\{d\_\{u\}\} f\_\{fa\} + \\frac\{1\}\{d\_\{u\}\} \\sum\_\{v\}f\_\{v\} + 1$ ①
     *  这里$v$表示$u$的儿子节点；
     *  假设已经处理好了$u$的儿子，为了能够递推，将式子写成：
     *  $f\_\{u\} = A\_\{u\}f\_\{fa\} + B\_\{u\}$ ②
     *  那么$A\_\{v\}$和$B\_\{v\}$是已经处理好的，对①中的$v$用②，再对比化简的①和②：
     *  $$f\_\{u\} = \\frac\{1\}\{d\_\{u\} - \\sum\_\{v\}A\_\{v\} \} f\_\{fa\} + \\frac\{d\_\{u\} + \\sum\_\{v\}B\_\{v\} \}\{d\_\{u\} - \\sum\_\{v\} A\_\{v\}\}$$
     *  这样就可以$O(n)$递推$AB$
     *  用$fmt$处理反演部分的话，复杂度就是：$O(n2^n \\ + \\ q )$;

#include<bits/stdc++.h>
         #define mod 998244353
         using namespace std;
         const int N=20,M=100010;
         int n,q,s,S,num[1<<18],f[1<<18],o=1,hd[N],A[N],B[N],d[N],inv[M];
         struct Edge{
             int v,nt;}E[N<<1];
         void adde(int u,int v){
             E[o]=(Edge){v,hd[u]};hd[u]=o++;
             E[o]=(Edge){u,hd[v]};hd[v]=o++; 
         }
         inline int Inv(int x){
             return x<1e5?inv[x]:1ll*(mod-mod/x)*Inv(mod%x)%mod;}
         void dfs(int u,int fa){
             if(S&1<<(u-1)){A[u]=B[u]=0;return;}
             int s1=0,s2=0;
             for(int i=hd[u];i;i=E[i].nt){
                 int v=E[i].v;
                 if(v==fa)continue;
                 dfs(v,u);
                 s1=(s1+A[v])%mod,s2=(s2+B[v])%mod;
             }
             A[u]=Inv((d[u]-s1+mod)%mod);
             B[u]=1ll*A[u]*(s2+d[u])%mod;
         }
         int main(){
             #ifndef ONLINE_JUDGE
             freopen("loj2542.in","r",stdin);
             freopen("loj2542.out","w",stdout);
             #endif
             scanf("%d%d%d",&n,&q,&s);
             inv[1]=1;
             for(int i=2;i<=1e5;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
             for(int i=1,u,v;i<n;++i){
                 scanf("%d%d",&u,&v);
                 adde(u,v);
                 d[u]++,d[v]++;
             }
             for(int i=1;i<1<<n;++i){
                 S=i;dfs(s,0);
                 num[i]=num[i>>1]+(i&1);
                 f[i]=(num[i]&1)?B[s]:(mod-B[s])%mod;
             }
             for(int i=0;i<n;++i)
             for(int j=1<<i;j<1<<n;++j){
                 if(j>>i&1)f[j]=(f[j]+f[j^(1<<i)])%mod;
             }
             for(int i=1,k;i<=q;++i){
                 scanf("%d",&k);
                 S=0;for(int j=1,x;j<=k;++j)scanf("%d",&x),S^=1<<(x-1);
                 printf("%d\n",f[S]);
             }
             return 0;
         }