LOJ#2340. 「WC2018」州区划分

题目地址：[嘤嘤嘤](https://loj.ac/problem/2340)

听说是$FMT$裸题然而学了$FMT$还是不会啊$QAQ$。

首先有一个比较显然的$dp$。

$$f_S=\sum_{V\subset {S}}\frac{\sum_{i\in V}w_i}{\sum_{i\in S}w_i}f_{S-V}$$
这个就已经可以$O(3^n)$了。
但是这样就过了就出不进$WC$了呀~

发现这是一个子集卷积。
然而我们只会子集并/交/异或卷积啊，怎么办呢????

$Orz$了题解，神做法。我们把所有的$f_S$按位数分类分为几个数组。
其中$f_S$只在$g[x][S]$中不为$0$，$x$为$S$的位数。
每一次我们把$g[i],g[j]$卷积起来，把新数组$S$位数不为$i+j$的抹掉就行了。
这样里面是卷积，外面也相当于一个卷积，但是我们$FMT$可以只做$n$遍，总复杂度$O(n^22^n)$。

```
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int mod = 998244353;
const int N = 22;
const int maxn = 1 << 21;
int n, m, dp[N][maxn], f[N][maxn], g[maxn], isum[maxn], bc[maxn];
int u[505], v[505], d[N], No_euler[N], w[N], p, stmax;

void Add(int &x, const int &c) {
	x += c; if(x >= mod) x -= mod;
}

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

int lpow(int a, int b) {
	if(!b) return 1;
	if(b == 1) return a;
	return 1ll * a * a % mod;
}

namespace DSU {
	int fa[N];
	void init(int n) {
		for(register int i = 1; i <= n; ++i)
			fa[i] = i;
	}
	int find(int x) {
		return fa[x] == x ? x : (fa[x] = find(fa[x]));
	}
	void combine(int x, int y) {
		fa[find(x)] = find(y);
	}
}

int GetG(int x) {
	int ans = 0, EU = 1;
	DSU::init(n), memset(d, 0, sizeof(d));
	for(register int i = 1; i <= m; ++i)
		if(((1 << u[i] - 1) & x) && (1 << v[i] - 1) & x)
			++d[u[i]], ++d[v[i]], DSU::combine(u[i], v[i]);
	int lst = 0;
	for(register int i = 1; i <= n; ++i)
		if((1 << i - 1) & x) {
			if(!lst) lst = DSU::find(i);
			else if(lst != DSU::find(i)) EU = 0;
			if((d[i] & 1)) EU = 0;
			Add(ans, w[i]);
		}
	isum[x] = lpow(fpow(ans, mod - 2), p);
	if(EU) return 0;
	return lpow(ans, p);
}

inline void CT(int &x, const int &c, const int &t) {
	if(t) {x += c; if(x >= mod) x -= mod;}
	else {x -= c; if(x < 0) x += mod;}
}

void FWT_OR(int * A, int n, int t) {
	for(register int i = 2; i <= 1 << n; i <<= 1)
		for(register int p = i >> 1, j = 0; j < 1 << n; j += i)
			for(register int k = 0; k < p; ++k)
				CT(A[p + j + k], A[j + k], t);
}

void work(int x) {
	for(register int i = 1; i <= x; ++i)
		for(register int j = 0; j < 1 << n; ++j)
			Add(dp[x][j], 1ll * dp[x - i][j] * f[i][j] % mod);
	FWT_OR(dp[x], n, 0);
	for(register int i = 0; i < 1 << n; ++i) 
		if(bc[i] != x) dp[x][i] = 0;
		else dp[x][i] = 1ll * dp[x][i] * isum[i] % mod;
}

int main() {
	scanf("%d%d%d", &n, &m, &p);
	for(register int i = 1; i <= m; ++i) 
		scanf("%d%d", &u[i], &v[i]);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	stmax = 1 << n;
	for(register int i = 1; i < stmax; ++i) {
		g[i] = GetG(i), bc[i] = bc[i >> 1] + (i & 1);
		f[bc[i]][i] = g[i];
	}
	for(register int i = 1; i <= n; ++i)
		FWT_OR(f[i], n, 1);
	dp[0][0] = 1, FWT_OR(dp[0], n, 1);
	for(register int i = 1; i < n; ++i) {
		work(i), FWT_OR(dp[i], n, 1);
	}
	work(n);
	printf("%d", dp[n][stmax - 1]);
	return 0;
} 
```

Rockdu's Blog

导航

最近发表

大佬们的友链