「WC 2018」州区划分

Problem

Description

给定一个点数为 n 且带点权的简单图 G ,定义图 G 的一个划分方案为 \left\{V_{1},V_{2},...,V_{k}\right\}

一个划分方案是合法的当且仅当其满足如下条件:

  1. \forall i\in[1, k]:\left|V_{i}\right|>1
  2. V(G) 中的每个点属于且仅属于一个 V_{i}
  3. 对任意 i\in[1, k] ,在导出子图 G\left[V_{i}\right] 中不存在一条经过所有点至少一次的欧拉回路。

定义一个合法划分方案 \left\{V_{1},V_{2},...,V_{k}\right\} 的权值为:

\prod_{i=1}^{k}\left(\frac{\sum_{u\in V_{i}}w_{u}}{\sum_{j=1}^{i}\sum_{u\in V_{j}}w_{u}}\right)^{p}

其中 w_{i} 为第 i 个点的权值, p 为给定常数。

求所有合法划分方案的权值之和。

两个划分 \left\{V_{1},V_{2},...,V_{k}\right\},\left\{C_{1},C_{2},...,C_{s}\right\} 是不同的,当且仅当 k\ne s \exists i\in[1, k]:V_{i}\ne C_{i}

答案对 998244353 取模。

Constraints

1\le\left|V(G)\right|\le 21,0\le p\le 2,1\le w_{i}\le 100

Solution

Analysis

设导出子图 G[S] 的合法划分方案权值和为 f_{S} ,点集 S 内的点点权和为 w_{S} ,则有 DP 方程:

f_{S}=\frac{1}{w_{S}}\sum_{T\subseteq S}\left[\operatorname{vaild}(T)\right]w_{T}f_{S-T}

其中 \operatorname{vaild}(S) 取真值当且仅当在导出子图 G[S] 中不存在一条经过所有点至少一次的欧拉回路。

用子集卷积优化计算即可。

时间复杂度 O\left(n^{2}2^{n}\right)

Code

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<algorithm>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(21);
constexpr int U(1<<maxn);
constexpr int p(998244353);
constexpr int maxs(4410000);

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

int e[maxn],
bit[U],
pct[U],
ufs[maxn];

inline int anc(const int&u)
{return ufs[u]==u?u:(ufs[u]=anc(ufs[u]));}

inline bool vaild(const int&S){
static int deg[maxn];

int cntk=0;
for(int i,s=S;s;s-=(1<<i))
i=bit[s&-s],deg[i]=0,ufs[i]=i;

for(int i,s=S;s;s-=(1<<i))
for(int ce=e[i=bit[s&-s]]&S,v;ce;ce-=(1<<v)){
v=bit[ce&-ce];
++deg[i];++deg[v];
if(anc(v)!=anc(i))
ufs[ufs[v]]=ufs[i],++cntk;
}

if(cntk+1!=pct[S])
return true;
for(int s=S;s;s-=s&-s)
if(deg[bit[s&-s]]&1)
return true;
return false;
}

template<typename _Tp,class func_t>
inline void FWT(_Tp*const&f,const int&n,const func_t&func){
_Tp*const&td=f+n;
for(int l=1;l!=n;l+=l)
for(_Tp*i=f;i!=td;i+=l+l)
for(int j=0;j!=l;++j)
func(i[j],i[j+l]);
}

int w[U],
inv[maxs+1],
invs[U],
f[maxn+1][U],
g[maxn+1][U];

int main(){
const int n=io,u=1<<n,m=io,tp=io;
for(int i=m;i!=0;--i)
e[((int)io)-1]|=(1<<((int)io-1));
int sum=0;
for(int i=1;i!=u;i+=i)
sum+=(w[i]=io);

for(int i=0;i!=n;++i)
bit[1<<i]=i;
for(int i=1;i!=u;++i)
pct[i]=pct[i>>1]+(i&1);
const int mxinv=(tp==2?sum*sum:tp==1?sum:1)+1;
inv[1]=1;
for(int i=2;i!=mxinv;++i)
inv[i]=(i64)inv[p%i]*(p-p/i)%p;

if(tp){
for(int t=2;t!=u;t+=t){
const int tt=t;
for(int s=1;s!=tt;++s)
w[s+t]=w[s]+w[t];
}
if(tp==2)
for(int s=1;s!=u;++s)
w[s]*=w[s];
}else std::fill(w,w+u,1);
for(int s=0;s!=u;++s)
g[pct[s]][s]=vaild(s)?w[s]:0,
invs[s]=inv[w[s]];

const auto or_t=[](const auto&x,auto&y){y+=x;(p<=y)&&(y-=p);};
const auto ior_t=[](const auto&x,auto&y){y-=x;(y<0)&&(y+=p);};
const auto inc=[](auto&x,const auto&y){x+=y;(p<=x)&&(x-=p);};

f[0][0]=1;
for(int i=1;i<=n;++i){
FWT((int*const&)f[i-1],u,or_t);
FWT((int*const&)g[i],u,or_t);

int*const&cur=f[i];
std::copy(g[i],g[i]+u,f[i]);
for(int j=1;j!=i;++j){
const int *const&mf=f[i-j],*const&mg=g[j];
for(int s=0;s!=u;++s)
inc(cur[s],(i64)mf[s]*mg[s]%p);
}

FWT(cur,u,ior_t);
for(int s=0;s!=u;++s)
cur[s]=(pct[s]==i?(i64)cur[s]*invs[s]%p:0);
}

printf("%d",f[n][u-1]);

return 0;
}