【题目链接】
【思路要点】
- BZOJ
- UOJ
【附：子集卷积介绍】
- 定义\(sum_S\)表示集合\(S\)包含的城市人口总数的\(p\)次方。
- 定义\(g_S\)，当\(S\)是一个合法的州区，\(g_S=sum_S\)，否则\(g_S=0\)。
- 定义\(f_S\)表示\(S\)所有可行的州区划分的方案的满意度之和。
- 那么\(f_S=\sum_{T\subseteq S,T\ne\emptyset}\frac{g_T*f_{S-T}}{sum_S}\)。
- 直接通过枚举子集实现该动态规划可以得到一个\(O(3^N)\)的做法。
- 注意到该方程实际上是一个子集卷积的形式，用FWT实现该动态规划，复杂度降至\(O(N^2*2^N)\)。
【【OJ】BZOJ|【BZOJ5153】【UOJ348】【WC2018】州区划分】【代码】
- 前置技能：子集或卷积。
- 我们知道，子集或卷积实现了快速求解\(f_S=\sum_{A\cap B=S}g_A*h_B\)。
- 考虑如何快速求解\(f_S=\sum_{A\cap B=S,A\cup B=\emptyset}g_A*h_B\)。
- 上式等价于\(f_S=\sum_{A\cap B=S,|A|+|B|=|S|}g_A*h_B\)。
- 考虑多记录一维状态，记\(f'_{i,S}\)，当\(i=|S|\)，\(f'_{i,S}=f_S\)，否则\(f'_{i,S}=0\)。
- 类似地，定义\(g'_{i,S}\)和\(h'_{i,S}\)。
- 则有\(f'_{i,S}=\sum_{A\cap B=S,j+k=i}g'_{j,A}*h'_{k,B}\)。
- 对于\(f'_{i,*}\)，枚举\(j\)，用子集或卷积计算该\(j\)的贡献，然后扫描数组，剔除\(f_{i,S}\)中\(i\ne |S|\)的情况。
- 时间复杂度\(O(N^2*2^N)\)。
#includeusing namespace std; const int MAXN = 25; const int MAXM = 505; const int MAXS = 1 << 21; const int P = 998244353; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template void writeln(T x) { write(x); puts(""); } int power(int x, int y) { if (y == 0) return 1; int tmp = power(x, y / 2); if (y % 2 == 0) return 1ll * tmp * tmp % P; else return 1ll * tmp * tmp % P * x % P; } int n, m, p, u; int d[MAXN], b[MAXN]; int x[MAXM], y[MAXM]; int bit[MAXN], val[MAXN]; int sum[MAXS], bcnt[MAXS]; int f[MAXN][MAXS], g[MAXN][MAXS]; int F(int x) { if (x == b[x]) return x; else return b[x] = F(b[x]); } void FWT(int *a, int N) { for (int len = 2; len <= N; len <<= 1) for (int s = 0; s < N; s += len) for (int i = s, j = s + len / 2; j < s + len; i++, j++) a[j] = (a[i] + a[j]) % P; } void UFWT(int *a, int N) { for (int len = 2; len <= N; len <<= 1) for (int s = 0; s < N; s += len) for (int i = s, j = s + len / 2; j < s + len; i++, j++) a[j] = (a[j] - a[i] + P) % P; } int main() { read(n), read(m), read(p); for (int i = 1; i <= m; i++) read(x[i]), read(y[i]); for (int i = 1; i <= n; i++) read(val[i]), bit[i] = 1 << (i - 1); u = 1 << n; for (int s = 0; s < u; s++) { for (int i = 1; i <= n; i++) if (s & bit[i]) sum[s] += val[i], bcnt[s]++; sum[s] = power(sum[s], p); for (int i = 1; i <= n; i++) d[i] = 0, b[i] = i; for (int i = 1; i <= m; i++) if ((s & bit[x[i]]) && (s & bit[y[i]])) { d[x[i]]++, d[y[i]]++; b[F(x[i])] = F(y[i]); } int home = -1; for (int i = 1; i <= n; i++) { if (d[i] & 1) g[bcnt[s]][s] = sum[s]; if (bit[i] & s) { int tmp = F(i); if (home == -1) home = tmp; else if (tmp != home) g[bcnt[s]][s] = sum[s]; } } sum[s] = power(sum[s], P - 2); } for (int i = 0; i <= n; i++) FWT(g[i], u); f[0][0] = 1; FWT(f[0], u); for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) for (int s = 0; s < u; s++) f[i][s] = (f[i][s] + 1ll * f[j][s] * g[i - j][s]) % P; UFWT(f[i], u); for (int s = 0; s < u; s++) if (bcnt[s] != i) f[i][s] = 0; else f[i][s] = 1ll * f[i][s] * sum[s] % P; FWT(f[i], u); } UFWT(f[n], u); printf("%d\n", f[n][u - 1]); return 0; }
