【题解】LOJ 2340 「WC2018」州区划分

请注意,本文编写于 97 天前,最后修改于 96 天前,其中某些信息可能已经过时。

Problem

鉴于题面比较复杂,所以...

传送门

Thought

首先取出一个子图 $S$ ,需要计算该图是否合法,

考虑设 $f(S)$ 为当前已经确定的集合为 $S$ 的总满意度乘积和

设 $val(S)=\sum_{x\in S}w_s$

那么易得

$$ f(S)=\sum_{S'\subseteq S}f(S-S')*(\frac{val(S')}{val(S)})^p[S'\text{合法}]\\ f(S)=\frac{1}{val(S)^p}\sum_{S'\in S}f(S-S')*val(S')^p[S'\text{合法}] $$

令 $g(S)=val(S)^p[S\text{合法}]$,可以在 $O(n+m)$ 的时间内处理出 $g(S)$ ,处理 $g$ 的总复杂度为 $2^n(n+m)$

$$ f(S)=\frac{1}{val(S)^p}\sum_{S'\in S}f(S-S')g(S') $$

这就是个子集卷积的形式了
然后按照 $|S|$ 从小到大算就好了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 22;
const int mod = 998244353;
int n, m, p;
int S;

int w[N];
int u[N * N], v[N * N];

int deg[N];
int fa[N], siz[N];
bool vis[N];

int f[22][1 << 21];
int g[22][1 << 21];
int val[1 << 21];
int num[1 << 21];

void init() {
    n = read(); m = read(); p = read();
    S = 1 << n;
    for(int i = 1; i <= m; ++ i) {
        u[i] = read();
        v[i] = read();
    }
    for(int i = 1; i <= n; ++ i)
        w[i] = read();
}

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

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

bool merge(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return 0;
    if(siz[a] > siz[b]) swap(a, b);
    
    fa[a] = b;
    siz[b] += siz[a];
    siz[a] = 0;
    return 1;
}

int M(int x) {
    while(x < 0) x += mod;
    while(x >= mod) x -= mod;
    return x;
}

void FWT_OR(int *a, int n, int f) {
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; ++ k) {
                int x = i + j + k;
                a[x] += f * a[j + k];
                while(a[x] < 0) a[x] += mod;
                while(a[x] >= mod) a[x] -= mod;
            }
}

void FWT_OR_HAND(int *a, int n, int pos, int key) {
    for(int i = 0; i < n; ++ i)
        if((i | pos) == i)
            a[i] = M(a[i] + key);
}

void cal(int s) {
    int SET = 0, peo = 0;
    for(int i = 1; i <= n; ++ i) {
        fa[i] = i;
        siz[i] = 1;
        vis[i] = deg[i] = 0;
    }
    
    for(int i = 1; i <= n; ++ i)
        if((1 << (i - 1)) & s) {
            vis[i] = 1;
            num[s] += 1;
            SET += 1;
            val[s] += w[i];
        }
    
    for(int i = 1; i <= m; ++ i)
        if(vis[u[i]] && vis[v[i]]) {
            ++ deg[u[i]];
            ++ deg[v[i]];
            SET -= merge(u[i], v[i]);
        }
    
    int flag = 1;
    if(SET != 1) flag = 0;
    for(int i = 1; i <= n && flag; ++ i)
        if(deg[i] % 2)
            flag = 0;
    
    val[s] = qpow(val[s], p);

    g[num[s]][s] += (flag ^ 1) * val[s] % mod;
    if(g[num[s]][s] >= mod) g[num[s]][s] -= mod;

    val[s] = qpow(val[s] , mod - 2);
}

int main() {
    init();
    for(int i = 1; i < S; ++ i)
        cal(i);
    for(int i = 0; i <= n; ++ i)
        FWT_OR(g[i], S, 1);
    FWT_OR_HAND(f[0], S, 0, 1);
    for(int i = 1; i <= n; ++ i) {
        for(int j = 0; j < i; ++ j)
            for(int k = 0; k < S; ++ k) {
                f[i][k] += 1ll * f[j][k] * g[i - j][k] % mod;
                if(f[i][k] >= mod) f[i][k] -= mod;
            }
        
        FWT_OR(f[i], S, - 1);
        for(int k = 0; k < S; ++ k)
            f[i][k] = 1ll * f[i][k] * val[k] % mod;
        FWT_OR(f[i], S, 1);
    }
    FWT_OR(f[n], S, - 1);
    printf("%d\n", f[n][S - 1]);
    return 0;
}
Comments

添加新评论