「LOJ 2340」「WC2018」州区划分

LOJ #2340

题意

有 $n$ 座城市，第 $i$ 座城市的人口是 $w_i$，有一些无向边。

现在城市被划分为了若干个州，每个州至少包含一个城市，每个城市恰好在一个州内。

设 $V_i$ 是第 $i$ 个州的城市集合。

定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 $0$），则称这个州是不合法的。

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

$$\left(\frac{\sum_{x\in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x}\right)^p$$

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

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

答案对 $998244353$ 取模。

$n\le 21,0\le p\le 2$

时限 $10s$

---

做法

首先可以 $\mathcal O(2^nn^2)$ 地处理出一个州是否合法

考虑 $dp$，令 $f_S$ 表示集合 $S$ 的所有合法划分的满意度之和，$sum_S$ 表示集合 $S$ 中所有城市的人口之和。

若一个州合法，令$g_S=sum_S$，否则 $g_S=0$

显然有

$$f_S=\sum_{T\subseteq S,T\ne\varnothing}f_{S\backslash T}\left(\frac{g_T}{sum_S}\right)^p$$

直接枚举是 $\mathcal O(3^n)$ 的，可以获得 $50$ 分的好成绩

现场没看懂题意，要是写出来就卡线Au了

转换成

$$f_S*sum_S^p=\sum_{T\subseteq S,T\ne\varnothing}f_{S\backslash T}*g_T^p$$

这个东西很像子集卷积

考虑增加一维集合大小，$f’{i,S}=[|S|=i]f_S$，$g’{i,S}$同理

$dp$ 的时候第一维是从小转移到大的，于是对每一个 $g’_j$ 和当前的 $f’_i$ 做FWT，暴力枚举一个 $j$，用 $g’_j$ 和 $f’i$ 去更新 $f’{i+j}$

注意这里都用FWT之后的数组运算，但是除了 $f’_{|S|,S}$ 都是不合法的信息，需要IFWT回来后清除，再FWT回去

复杂度 $\mathcal O(2^nn^2)$

所以这里 $p$ 放那么小没什么用

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

const int N = 23, M = 220, S = 1<<21, P = 998244353;
int n, m, num, p, w[N], fa[N], d[N], h[N], pre[M], e[M], s[S], cnt[S], W[N][S], f[N][S];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
inline int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
inline bool check(int x){
	for(int i=0; i<n; ++i) fa[i]=i, d[i]=0;
	for(int i=0; i<n; ++i) if(x>>i&1) for(int j=h[i]; j; j=pre[j]) if(x>>e[j]&1)
		fa[find(i)]=find(e[j]), ++d[i], ++d[e[j]];
	int cnt=0;
	for(int i=0; i<n; ++i) if(x>>i&1){
		cnt+=find(i)==i;
		if(d[i]&1) return 0;
	}
	if(cnt>1) return 0;
	return 1;
}
inline void FWT(int *f, int g){
	for(int i=1; i<1<<n; i<<=1) for(int j=0; j<1<<n; j+=i<<1)
		for(int k=j; k<j+i; ++k){
			int x=f[k], y=f[k+i];
			f[k]=(x+y)%P, f[k+i]=(x-y+P)%P;
		}
	if(g==-1) for(int i=0, I=Pow(1<<n); i<1<<n; ++i) f[i]=(ll)f[i]*I%P;
}
int main() {
	scanf("%d%d%d", &n, &m, &p);
	for(int i=0, x, y; i<m; ++i) scanf("%d%d", &x, &y), add(x-1, y-1);
	for(int i=0; i<n; ++i) scanf("%d", w+i);
	for(int i=1; i<1<<n; ++i){
		cnt[i]=cnt[i^(i&-i)]+1;
		for(int j=0; j<n; ++j) if(i>>j&1) s[i]+=w[j];
		if(p==0) s[i]=1;
		if(p==2) s[i]=s[i]*s[i];
	}
	s[0]=1;
	for(int i=1; i<1<<n; ++i) W[cnt[i]][i]=s[i]*!check(i), s[i]=Pow(s[i]);
	for(int i=1; i<=n; ++i) FWT(W[i], 1);
	f[0][0]=1;
	for(int i=0; i<=n; ++i){
		if(i) FWT(f[i], -1);
		for(int j=0; j<1<<n; ++j)
			if(cnt[j]==i) f[i][j]=(ll)f[i][j]*s[j]%P; else f[i][j]=0;
		if(i!=n) FWT(f[i], 1);
		for(int j=1; i+j<=n; ++j) for(int k=0; k<1<<n; ++k)
			f[i+j][k]=(f[i+j][k]+(ll)f[i][k]*W[j][k])%P;
	}
	return printf("%d", f[n][(1<<n)-1]), 0;
}