「WC 2018」州区划分【状压 DP + FWT】

Time Limit: 10 Sec Memory Limit: 1024 MB

Description

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

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

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

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

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

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

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

答案对 998244353998244353 取模。

两个划分 {V1Vk}\{V_1 \cdots V_k\}{C1Cs}\{C_1 \cdots C_s\} 是不同的,当且仅当 ksk \neq s,或存在某个 1ik1 \leqslant i \leqslant k,使得 ViCiV_i \neq C_i

Input

输入第一行包含三个整数 n,m,pn, m, p,表示城市个数、城市之间的道路个数以及题目描述中的常数 pp

接下来 mm 行,每行两个整数 u,vu, v,描述一条无向的道路,保证无重边无自环;

输入第 m+2m+2 行有 nn 个正整数,第 ii 个正整数表示 wiw_i

Output

输出一行一个整数表示答案在模 998244353998244353 意义下的取值。

即设答案化为最简分式后的形式为 ab\dfrac a b,其中 aabb 互质。输出整数 xx 使得 bxa (mod 998244353)bx \equiv a \ (\text{mod} \ 998244353)0x<9982443530 \leqslant x < 998244353。可以证明这样的整数 xx 是唯一的。

Sample Input

1
2
3
4
3 2 1
1 2
2 3
1 1 1

Sample Output

1
1

Constraints

保证对于所有数据有:0n210 \leqslant n \leqslant 21, 0mn(n1)20 \leqslant m \leqslant \dfrac{n(n-1)}{2}, 0p20 \leqslant p \leqslant 2, 1wi1001 \leqslant w_i \leqslant 100

Solution

f(S)f(S) 表示划分集合 SS 中的城市的所有方案的满意度之和,那么可得:

f(S)=TSf(T)h(ST)(sum(ST)sum(S))pf(S) = \sum_{T \subseteq S}f(T)\cdot h(S \setminus T)\cdot \left(\frac{\text{sum}(S \setminus T)}{\text{sum}(S)}\right)^p

考虑 FWT\text{FWT},不难发现 TST \subseteq S 这个条件就是做一个或卷积。但是无法保证每个元素都有它无交集的元素进行卷积,所以需要给状态加一维。

f(i,S)f(i, S) 表示所有州的城市个数为 ii 且并集为 SS 的划分方案的满意度之和,令 AA 表示全集,即可进行或卷积:

 f(i,S)=j=1iS1=0AS2=0A[S1S2=S][S2=j]h(S2)f(ij,S1)(sum(S2)sum(S))p f(i,S)sum(S)p=j=1iS1=0AS2=0A[S1S2=S]([S2=j]h(S2)sum(S2)p)f(ij,S1)\begin{aligned} &\ f(i, S) \\ &= \sum_{j=1}^i \sum_{S_1=0}^A \sum_{S_2=0}^A \big[S_1 \cup S_2=S\big] \cdot \big[\lvert S_2 \rvert = j\big] \cdot h(S_2)\cdot f(i-j, S_1)\cdot\left(\frac{\text{sum}(S_2)}{\text{sum}(S)}\right)^p \\ \\ &\ f(i, S) \cdot \text{sum}(S)^p \\ &= \sum_{j=1}^i \sum_{S_1=0}^A \sum_{S_2=0}^A \big[S_1 \cup S_2 = S\big] \cdot \Big(\big[\lvert S_2 \rvert = j\big] \cdot h(S_2) \cdot \text{sum}(S_2)^p\Big) \cdot f(i-j, S_1) \end{aligned}

g(j,S2)=[S2=j]h(S2)sum(S2)pg(j, S_2) = \big[\lvert S_2 \rvert = j\big] \cdot h(S_2) \cdot \text{sum}(S_2)^p,那么上面的式子就变成了标准的或卷积形式了。

总复杂度为 O(2nn2)O(2^n \cdot n^2),注意常数带来的影响。

备注FWT\text{FWT} 的思想可参考 2015 国集论文《集合幂级数的性质与应用及其快速算法》by 吕凯风 (请参见本文末的 PDF)。

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
#include <bits/stdc++.h>
#pragma GCC optimize (3)
#define x first
#define y second
using namespace std;

typedef pair<int, int> P;
typedef long long ll;
const int maxn = 22, maxs = 2097152, mod = 998244353;
int n, m, p, w[maxn], fa[maxn], inv[maxs], cnt[maxn], f[maxn][maxs], g[maxn][maxs];
P e[250];

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline int qp(int x, int y) {
int ans = 1;
for (; y; x = (ll)x * x % mod, y >>= 1) {
if (y & 1) {
ans = (ll)ans * x % mod;
}
}
return ans;
}

inline void fwt(int *a, int type) {
for (int i = 1; i <= n; i++) {
for (int j = 0; j < (1 << n); j += (1 << i)) {
for (int k = 0; k < (1 << (i - 1)); k++) {
int p = a[j + k], q = a[(1 << (i - 1)) + j + k];
if (type > 0) {
a[j + k] = (p + q) % mod, a[(1 << (i - 1)) + j + k] = p;
} else {
a[j + k] = q, a[(1 << (i - 1)) + j + k] = (p - q + mod) % mod;
}
}
}
}
}

int main() {
scanf("%d %d %d", &n, &m, &p);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
e[i] = P(u - 1, v - 1);
}
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
for (int s = 1; s < (1 << n); s++) {
int c = 0, sum = 0;
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) {
sum += w[i], c++;
}
}
int id = c;
inv[s] = qp(sum, mod - 2);
for (int i = 0; i < n; i++) {
fa[i] = i, cnt[i] = 0;
}
for (int i = 1; i <= m; i++) {
if (((s >> e[i].x) & 1) && ((s >> e[i].y) & 1)) {
int u = find(e[i].x), v = find(e[i].y);
if (u != v) fa[v] = u, c--;
cnt[e[i].x]++, cnt[e[i].y]++;
}
}
bool ok = 0;
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) {
ok |= (cnt[i] & 1);
}
}
if (ok || c > 1) g[id][s] = qp(sum, p);
}
f[0][0] = 1, fwt(f[0], 1);
for (int i = 0; i <= n; i++) {
fwt(g[i], 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 0; k < (1 << n); k++) {
(f[i][k] += (ll)g[j][k] * f[i - j][k] % mod) %= mod;
}
}
fwt(f[i], -1);
for (int k = 0; k < (1 << n); k++) {
f[i][k] = (ll)f[i][k] * qp(inv[k], p) % mod;
}
if (i < n) fwt(f[i], 1);
}
printf("%d\n", f[n][(1 << n) - 1]);
return 0;
}

References