Min-Max容斥真好用

题意：给一棵不超过1818个节点的树，50005000次询问，每次问从根随机游走走遍一个集合的期望步数

---

Solution:

考虑Min-Max容斥

有Max(S)=∑T⊆S(−1)|T|+1Min(T)

其中S,T是一个集合，Max(S)表示S中最大元素，Min(S)同理

我们设集合S表示走到每个点的期望时间

显然走遍一个集合的期望时间就是Max(S)

且第一次走到某集合的期望时间是Min(S)

Max(S)不容易计算，我们转而求解Min(S)

令fi表示从点i随机游走第一次走到集合SS的期望步数

这个显然可以高斯消元，不过复杂度略大

由于转移是在树上，可以直接在树上O(n)消元

我们令fi=ki f fa[i]+bi

当ii在集合S中的时候ki=bi=0否则进行转移

转移的时候把当前点孩子的k和b算出然后代到当前点的方程中算出当前点的k和b

这样可以在O(2n⋅n∗算逆元复杂度)的时间复杂度内算出所有的Min(S)

 

然后直接容斥算Max(S),复杂度是5000∗2n的

我们可以提前预处理每个Max(S)每次枚举子集转移，时间复杂度是3^n的

据说都能过

不过其实这部分可以优化到2n∗n的

我们直接根据popcount(S)的奇偶性来判断是否给Min(S)乘上−1

然后直接高维前缀和即可

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define mod 998244353#define ll long longusing namespace std;struct ret{ int k,b; ret operator +(const ret s)const{ return {(k+s.k)%mod,(b+s.b)%mod}; } ret operator *(const int s)const{ return {(ll)k*s%mod,1ll*b*s%mod}; }}f[19][1<<18];const int N=50;int i,j,k,m,n,x,z,cnt,root,Q;int g[N],l[N],c[N],a[N],d[N],inv[N],Min[1<<18];void add(int x,int y){ a[++k]=y; if (!g[x]) g[x]=k;else c[l[x]]=k; l[x]=k; }int pow(int x,int y){ int ans=1; for (int i=y;i;i>>=1,x=(ll)x*x%mod) if (i&1) ans=(ll)x*ans%mod;; return (ans+mod)%mod;}ret dfs(int x,int pre,int s){ if (s>>x-1&1) return{ 0,0}; ret now={ 0,0}; for (int i=g[x];i;i=c[i]) if (a[i]!=pre) now=now+dfs(a[i],x,s)*inv[d[x]]; const int Inv=pow(1-now.k,mod-2); return {(ll)Inv*inv[d[x]]%mod,1ll*Inv*(now.b+1)%mod};} int main(){ scanf("%d",&n); scanf("%d%d",&Q,&root); inv[0]=inv[1]=1; for (int i=2;i<=18;i++) inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod; for (int i=1;i
            
             >i&1) (Min[j]+=Min[j^(1<