Address 【BZOJ|[UOJ#348][WC2018]州区划分（状压dp+FMT）】洛谷P4221
BZOJ5153
UOJ#348
LOJ#2340
Solution 有一个显然的 dp 方案：
f [ S ] f[S] f[S] 表示选出的城市集合为S S S 的满意度之和。
s u m [ S ] sum[S] sum[S] 表示城市集合S S S 的人口之和。
g [ S ] g[S] g[S] 表示：
[ 子 图 S 不 存 在 欧 拉 回 路 ] × s u m [ S ] p [子图S不存在欧拉回路]\times sum[S]^p [子图S不存在欧拉回路]×sum[S]p
转移显然：
f [ S ] = 1 s u m [ S ] p ∑ T ? S f [ T ] g [ S ? T ] f[S]=\frac1{sum[S]^p}\sum_{T\subsetneq S}f[T]g[S-T] f[S]=sum[S]p1?T?S∑?f[T]g[S?T]
复杂度O ( 3 n ) O(3^n) O(3n) ，难以通过n = 21 n=21 n=21 的数据。
考虑到这是子集卷积的形式，不妨把f f f 按照S S S 集合大小分类：
f [ i ] [ S ] f[i][S] f[i][S] 表示：
{ f [ S ] ∣ S ∣ = i 0 ELSE \begin{cases}f[S]& |S|=i\\0& \text{ELSE}\end{cases} {f[S]0?∣S∣=iELSE?
那从小到大枚举i i i ，再枚举一个0 ≤ j < i 0\le j< i 0≤j 如果已经求得了f [ 0... i ? 1 ] f[0...i-1] f[0...i?1] 的快速莫比乌斯变换f [ 0 ] ′ , f [ 1 ] ′ , . . . , f [ i ? 1 ] ′ f[0]' ,f[1]' ,...,f[i-1]' f[0]′,f[1]′,...,f[i?1]′ ，
以及g g g 的 FMTg ′ g' g′ ,
那么就可以直接计算f [ i ] ′ [ S ] + = f [ j ] ′ [ S ] × g [ i ? j ] ′ [ S ] f[i]' [S]+=f[j]' [S]\times g[i-j]' [S] f[i]′[S]+=f[j]′[S]×g[i?j]′[S] 。
反演回去之后将每个f [ i ] [ S ] f[i][S] f[i][S] 除以s u m [ S ] p sum[S]^p sum[S]p 。
注意需要将∣ S ∣ ≠ i |S|\ne i ∣S∣??=i 的f [ i ] [ S ] f[i][S] f[i][S] 清零。
复杂度O ( 2 n × n 2 ) O(2^n\times n^2) O(2n×n2) 。
Code

#include #include #include #include #include #define For(i, a, b) for (i = a; i <= b; i++) #define Rof(i, a, b) for (i = a; i >= b; i--) #define Subset(k, i) for (k = i; k; k = (k - 1) & i) using namespace std; inline int read() { int res = 0; bool bo = 0; char c; while (((c = getchar()) < '0' || c > '9') && c != '-'); if (c == '-') bo = 1; else res = c - 48; while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + (c - 48); return bo ? ~res + 1 : res; }const int N = 25, C = (1 << 21) + 5, MOD = 998244353; int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % MOD; a = 1ll * a * a % MOD; b >>= 1; } return res; }int n, m, p, Cm, w[N], cnt[N], f[N][C], sum[C], inv[C], ans, eul[N][C], sze[C], fa[N]; bool gr[N][N], cir[C]; void FWT(int n, int *a, int op) { int i, j; For (i, 1, n) For (j, 0, (1 << n) - 1) if (!((j >> i - 1) & 1)) a[j | (1 << i - 1)] = (a[j | (1 << i - 1)] + (op == 1 ? a[j] : MOD - a[j])) % MOD; }int fd(int x) { if (fa[x] != x) fa[x] = fd(fa[x]); return fa[x]; }void mg(int x, int y) { int ix = fd(x), iy = fd(y); if (ix != iy) fa[iy] = ix; }int main() { int i, j, S, x, y; n = read(); m = read(); p = read(); Cm = (1 << n) - 1; For (i, 1, m) x = read(), y = read(), gr[x][y] = gr[y][x] = 1; For (i, 1, n) w[i] = read(); For (S, 1, Cm) { For (i, 1, n) cnt[i] = 0, fa[i] = i; int xp = 0; For (i, 1, n) if ((S >> i - 1) & 1) { sum[S] += w[i]; sze[S]++; xp = i; For (j, i + 1, n) if (((S >> j - 1) & 1) && gr[i][j]) cnt[i]++, cnt[j]++, mg(i, j); } sum[S] = qpow(sum[S], p); inv[S] = qpow(sum[S], MOD - 2); For (i, 1, n) if (((S >> i - 1) & 1) && fd(i) != fd(xp)) {cir[S] = 1; continue; } For (i, 1, n) if (cnt[i] & 1) {cir[S] = 1; continue; } } For (i, 0, Cm) eul[sze[i]][i] = cir[i] * sum[i]; For (i, 0, n) FWT(n, eul[i], 1); f[0][0] = 1; FWT(n, f[0], 1); For (i, 1, n) { For (j, 0, i - 1) For (S, 0, Cm) f[i][S] = (f[i][S] + 1ll * f[j][S] * eul[i - j][S] % MOD) % MOD; FWT(n, f[i], -1); For (S, 0, Cm) if (sze[S] == i) f[i][S] = 1ll * f[i][S] * inv[S] % MOD; else f[i][S] = 0; FWT(n, f[i], 1); } FWT(n, f[n], -1); cout << f[n][Cm] << endl; return 0; }