「UR #17」滑稽树前做游戏

「UR #17」滑稽树前做游戏

五月 06, 2020 · OI 题解

给定一个 $n$ 个点 $m$ 条边的无向图，其中每个点的点权是 $[0;1]$ 范围内生成的连续型随机变量，求：

的期望，答案对 $998244353$ 取模。

$n \leq 25$。（实际上可以跑 $n \leq 30$。。。

题解

考虑如何计算 $Pr[\lambda \leq x]$，设 $g(s,y,t)$ 表示对于点集 $s$，点权最大值 $\leq y$，答案 $\leq t$ 的概率。考虑其状态转义：

  • 如果生成的所有数都 $\leq \frac t 2$，则贡献为 $(\frac t 2)^{|s|}$
  • 对于其他情况，考虑最大值点 $i$，并递归。

其中 $s_i$ 表示从 $s$ 中删除 $i$ 以及所有和 $i$ 相邻的点得到的点集。

如果我们直接暴力状压维护二元多项式转移显然麻烦的一比，而且常数还贼他妈大，考虑理性一点的方式。

首先，如果当前的状态是若干独立的联通块，可以直接把每个联通块的答案相乘，这可以大大减小状态数。

另外，我们可以注意到，对于二元多项式的每一项 $y^i t^j$，都满足 $i+j$ 是定值，即二元多项式 $g(s)$ 每项的幂次和都是 $|s|$。由二项式定理的系数可以方便得到。

最后，我们需要注意 $g(s,y,t)$ 的取值范围 $\tfrac t 2 \leq y \leq \min(1, t)$，所以答案是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
const int N=30,mod=998244353,inv2=(mod+1)>>1;
int n,m,tim,G[N],vis[N];
struct z {
  int x;
  z(int x=0):x(x){}
  friend inline z operator*(z a,z b){return (long long)a.x*b.x%mod;}
  friend inline z operator-(z a,z b){return (a.x-=b.x)<0?a.x+mod:a.x;}
  friend inline z operator+(z a,z b){return (a.x+=b.x)>=mod?a.x-mod:a.x;}
}ans,inp[N],inv[N],C[N][N];
std::unordered_map<int,std::vector<z>> map;
inline std::vector<z> operator*(const std::vector<z> &a,const std::vector<z> &b){
  std::vector<z> c(a.size()+b.size()-1);
  for(int i=0;i<a.size();i++)
    for(int j=0;j<b.size();j++)
      c[i+j]=c[i+j]+a[i]*b[j];
  return c;
}
inline std::vector<z> integral(std::vector<z> f){
  std::vector<z> g(f.size()+1);
  for(int i=1;i<=f.size();i++)g[i]=f[i-1]*inv[i];
  return g;
}
inline z evaluation(std::vector<z> a,int l,int r){
  a=integral(a); z p,s; int i;
  for(p=1,i=0;i<a.size();i++)s=s+a[i]*p,p=p*r;
  for(p=1,i=0;i<a.size();i++)s=s-a[i]*p,p=p*l;
  return s;
}
void initfac(int n){
  inp[0]=inv[0]=inv[1]=1;
  for(int i=2;i<n;i++)inv[i]=(mod-mod/i)*inv[mod%i];
  for(int i=1;i<n;i++)inp[i]=inp[i-1]*inv2;
  for(int i=0;i<n;i++){
    C[i][0]=1;
    for(int j=1;j<=i;j++)C[i][j]=C[i-1][j]+C[i-1][j-1];
  }
}
int dfs(int u,int s){
  int res=1<<u; vis[u]=tim;
  for(int v=0;v<n;v++)if(((s>>v)&1)&&((G[u]>>v)&1)&&vis[v]!=tim)res|=dfs(v,s);
  return res;
}
void update(std::vector<z> &s,std::vector<z> a,int k){
  std::vector<z> b(k+1);
  for(int i=0;i<=k;i++)b[i]=C[k][i]*(i&1?mod-1:1);
  a=integral(a*b);
  for(int i=0;i<a.size();i++)s[i]=s[i]+a[i],s[0]=s[0]-inp[i]*a[i];
}
std::vector<z> solve(int s){
  if(map.count(s))return map[s];
  int l=__builtin_popcount(s); std::vector<z> res; std::vector<int> set;
  for(int t,i=0;i<n;i++)if((s>>i)&1)++tim,t=dfs(i,s),set.push_back(t),s^=t;
  for(int x:set)s|=x;
  if(set.size()>1){res={1}; for(auto t:set)res=res*solve(t);}
  else{
    res.resize(l+1),res[0]=inp[l];
    for(int i=0;i<n;i++)if((s>>i)&1){
      int t=s^(s&(G[i]|(1<<i)));
      update(res,solve(t),__builtin_popcount(s&G[i]));
    }
  }
  return map[s]=res;
}
int main(){
  std::cin>>n>>m,initfac(N),map[0]={1};
  for(int u,v,i=0;i<m;i++)std::cin>>u>>v,--u,--v,G[u]|=1<<v,G[v]|=1<<u;
  std::vector<z> s=solve((1<<n)-1),a(n+1);
  for(int i=0;i<s.size();i++)a[n]=a[n]+s[i];
  std::reverse(s.begin(),s.end());
  std::cout<<(2-evaluation(s,1,2)-evaluation(a,0,1)).x<<std::endl;
}