题解 P4221 【[WC2018]州区划分】

lahlah · 2019-09-30 10:30:42 · 题解

luogu P4221 [WC2018]州区划分

题意

题意比较复杂，大致就是说

给出n个点，m条边

把n个点分成若干组，使每组里面不存在欧拉回路

每种方案的满意度为所有州的满意度的乘积

求所有方案的满意度的和

大概就是这样

题解

首先要知道怎么判断欧拉回路

当一组的所有点的度数都为偶数时存在欧拉回路（因为要起点和终点相同）

如果图不联通也是合法的

然后就可以用子集DP解决 15’ 的问题

code:

#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
struct edge{
    int v, nxt;
}e[10005];
int p[25], eid;
void init(){
    memset(p, -1, sizeof p);
    eid = 0;
}
void insert(int u, int v){
    e[eid].v = v;
    e[eid].nxt = p[u];
    p[u] = eid ++;
}
ll qpow(ll x, int y){
    ll ret = 1;
    for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
int fa[25];
int get(int x){
    return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
    x = get(x), y = get(y);
    fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005];
ll f[(1 << 23)];
int main(){
    init();
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for(int S = 0; S < (1 << n); S ++){

        int bb = 0;
        for(int i = 1; i <= n; i ++){
            if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
            du[i] = 0, fa[i] = i;
        }

        for(int i = 1; i <= m; i ++){//枚举边，看这条边是否在S这一组里
            if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
                if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
                du[U[i]] ++;
                du[V[i]] ++;//统计度数
            }
        }

        if(bb != 1) ok[S] = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i ++) 
            cnt += (du[i] & 1);
        if(cnt) ok[S] = 1;//处理出当前点是否合法

    }
    f[0] = 1;
    for(int S = 0; S < (1 << n); S ++){//子集DP
        for(int S0 = S; S0; S0 = (S0 - 1) & S) if(ok[S0]){
            f[S] += f[S ^ S0] * qpow(he[S0] % mod * qpow(he[S], mod - 2) % mod, q) % mod;//子集DP
            f[S] %= mod;
        }
    }
    printf("%lld", f[(1 << n) - 1]);
    return 0;
}

恭喜你获得了15’的好成绩！！！！

看看子集DP的式子

可以转换为

如果不考虑交集为空的情况那很明显可以FWT

考虑多加一位表示集合中 1 的个数

然后惊喜的发现就相当于是把f[j]和g[i-j]卷在一起 然后就可以FWT 了 非常容易理解

code:

#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
void fwt(ll *a, int len, int opt){//板子
    for(int i = 2; i <= len; i <<= 1)
        for(int p = i >> 1, j = 0; j + i <= len; j += i)
            for(int k = j; k < j + p; k ++)
                a[p + k] =(a[p + k] + opt * a[k] + mod) % mod;
}
ll qpow(ll x, int y){
    ll ret = 1;
    for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
int fa[25];
int get(int x){
    return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
    x = get(x), y = get(y);
    fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005], bitcount[1 << 23];
ll f[23][1 << 22], g[23][1 << 22], inv[1 << 22];
int main(){
    scanf("%d%d%d", &n, &m, &q);
    int len = 1 << n;
    for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for(int S = 0; S < len; S ++){

        int bb = 0;
        for(int i = 1; i <= n; i ++){
            if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
            du[i] = 0, fa[i] = i;
        }
        bitcount[S] = bb;//bitcount(S)表示S中1的个数

        for(int i = 1; i <= m; i ++){
            if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
                if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
                du[U[i]] ++;
                du[V[i]] ++;
            }
        }

        if(bb != 1) ok[S] = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i ++) 
            cnt += (du[i] & 1);
        if(cnt) ok[S] = 1;

        if(ok[S]) g[bitcount[S]][S] = qpow(he[S], q);//g是用来转移的，表示S划分成一组的满意度（分子）
        inv[S] = qpow(qpow(he[S], mod - 2), q);//分母 —— 逆元
    }
    for(int i = 0; i <= n; i ++) fwt(g[i], 1 << n, 1);
    f[0][0] = 1; fwt(f[0], 1 << n, 1);//FWT
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= i - 1; j ++)
            for(int k = 0; k < len; k ++)
                f[i][k] += f[j][k] * g[i - j][k] % mod, f[i][k] %= mod;//卷起来
        fwt(f[i], 1 << n, -1);//IFWT

        for(int j = 0; j < len; j ++) f[i][j] = bitcount[j] == i? f[i][j] * inv[j] % mod:0;//求满意度
        if(i != n) fwt(f[i], 1 << n, 1);
    }
    printf("%lld", f[n][len - 1]);
    return 0;
}

这题在WC算是简单题了吧

好像有点小卡常QWQ