州区划分 WC2018

[WC2018] 州区划分

题目链接： [WC2018] 州区划分 。

题目描述：

小 S 现在拥有 nn 座城市，第 ii 座城市的人口为 wiw_i，城市与城市之间可能有双向道路相连。

现在小 S 要将这 nn 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。

假设小 S 将这些城市划分成了 kk 个州，设 ViV_i 是第 ii 个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 00），则称这个州是不合法的。

定义第 ii 个州的满意度为：第 ii 个州的人口在前 ii 个州的人口中所占比例的 pp 次幂，即：

(∑x∈Viwx∑j=1i∑x∈Vjwx)p\left(\dfrac{\sum _ {x \in V _ i} w _ x}{\sum _ {j = 1} ^ i \sum _ {x \in V _ j} w _ x}\right) ^ p

定义一个划分的满意度为所有州的满意度的乘积。

求所有合法的划分方案的满意度之和。

答案对 998244353998244353 取模。
两个划分 {V1,V2,⋯ ,Vk}\{V_1, V _ 2, \cdots, V_k\} 和 {C1,C2,⋯ ,Cs}\{C_1, C _ 2, \cdots, C_s\} 是不同的，当且仅当 k≠sk \neq s，或存在某个 1≤i≤k1 \leq i \leq k，使得 Vi≠CiV_i \neq C_i。

要求复杂度 O(2nn2)\mathcal{O}(2^nn^2) 。

定义 hSh_S 表示 SS 内部所有点的 ww 和， fS=0/1f_S=0/1 表示点集 SS 合法 / 不合法。 gSg_S 表示点集 SS 的答案。

则显然有：

gS=∑T⊆S(hThS)pfTgS/Tg_S=\sum_{T\subseteq S}(\frac{h_T}{h_S})^pf_Tg_{S/T}

一个半在线集合幂级数子集卷积就能轻松解决。

主要问题就是判断一个集合是否合法。

注意到他的判断条件很像一个欧拉回路的判断条件。那么我们不妨令 valival_i 表示 ii 的出边的二进制状态，那么对于一个点集 SS ，只要 ⊕i∈S(vali∩S)=0\oplus_{i\in S}(val_i \cap S)=0 ，那么就有欧拉回路存在。但是这里还有一个必须在同一个城市的条件，所以我们必须判断图是否联通。此时我们可以直接 bfs\text{bfs} 而非并查集。只要从随意一个点出发能到达所有点，就必然满足图联通。

解决了。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=22,M=1<<21,P=998244353,NN=510;
int n,m,p,u[NN],v[NN],w[NN];
int s[M],is[M],f[N][M],val[N],g[N][M];
int bt(int i){return __builtin_popcount(i);}
int kpow(int a,int b){
	int t=1;
	while(b){
		if(b&1)t=1ll*t*a%P;
		a=1ll*a*a%P;
		b>>=1;
	}
	return t;
}
void FWT(int *f,int t,int n){
	for(int i=2;i<=(1<<n);i<<=1)
		for(int j=0;j<(1<<n);j+=i)
			for(int k=j;k<j+(i>>1);k++)
				(f[k+(i>>1)]+=(t==1?f[k]:P-f[k]))%=P;
}
int q[N],head,tail,book[N],cnt;
bool check(int i){
	for(int j=1;j<=n;j++)book[j]=0;
	head=tail=0;cnt=bt(i);
	int t=__builtin_ctz(i)+1;
	q[tail++]=t;
	book[t]=1;
	while(head<tail){
		int x=q[head++];cnt--;
		for(int j=1;j<=n;j++)
			if(!book[j]&&((i>>j-1)&1)&&((val[x]>>j-1)&1))
				q[tail++]=j,book[j]=1;
	}
	return cnt==0;
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=m;i++)scanf("%d%d",u+i,v+i);
	for(int i=1;i<=m;i++)val[u[i]]^=(1<<v[i]-1),val[v[i]]^=(1<<u[i]-1);
	for(int i=1;i<=n;i++)scanf("%d",w+i);
	for(int i=1;i<(1<<n);i++){
		int deg2=0;
		for(int j=1;j<=n;j++){
			if((i>>j-1)&1^1)continue;
			s[i]+=w[j];
			deg2^=(val[j]&i);
		}
		s[i]=kpow(s[i],p);
		int bl=check(i);
		if(deg2||!bl)
			f[bt(i)][i]=s[i];
		is[i]=kpow(s[i],P-2);
	}
    for(int i=0;i<=n;i++)FWT(f[i],1,n);
	g[0][0]=1;FWT(g[0],1,n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++)
			for(int p=0;p<(1<<n);p++)
				(g[i][p]+=1ll*f[i-j][p]*g[j][p]%P)%=P;
        FWT(g[i],-1,n);
        for(int j=0;j<(1<<n);j++)
            g[i][j]=1ll*g[i][j]*is[j]%P;
        FWT(g[i],1,n);
	}
    FWT(g[n],-1,n);
	printf("%d",g[n][(1<<n)-1]);
	return 0;
}