luogu4221 [WC2018]州区划分

题目描述

小 S 现在拥有 $n$ 座城市,第 $i$ 座城市的人口为 $w_i$,城市与城市之间可能有双向道路相连。

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

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

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

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

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

答案对 $998244353$ 取模。

两个划分 {$V_1...V_k$} 和 {$C_1...C_s$} 是不同的,当且仅当 $k \neq s$,或存在某个 $1 \leq i \leq k$,使得 $V_i \neq C_i$。

输入格式

从文件 ${\tt walk.in}$ 中读入数据。

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

接下来 $m$ 行,每行两个正整数 $u,v$,描述一条无向的道路,保证无重边无自环。

输入第 $m+2$ 行有 $n$ 个正整数,第 $i$ 个正整数表示 $w_i$。

输出格式

输出到文件 ${\tt walk.out}$ 中。

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

即设答案化为最简分式后的形式为 $a/b$ ,其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a$ mod $998244353$ 且 $0 \le x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

样例输入

3 2 1
1 2
2 3
1 1 1

样例输出

1

说明

保证对于所有数据有: $0 \leq n \leq 21$, $0 \leq m \leq n*(n-1)/2$ , $0 \leq p \leq 2$, $1 \leq w_i \leq 100$。


分析

考虑dp,设$f(S)$表示前几个州的选点状态为$S$的答案,则:

$$f(S)=\frac{1}{sum^p(S)}\sum_{T\subset S且ok(T)}f(S-T)sum^p(T)$$

这里$ok(T)$表示$T$能单独作为一个州,即没有欧拉回路。预处理的时候每个集合判一下是否联通和是否有度数为奇数的点即可。

写完方程以后,子集卷积一下就完事了。复杂度$O(n^2\cdot 2^n)$。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 23;
const int S = (1 << 21) + 50;
const int P = 998244353;

int bin[N];
int n, m, p;
int mp[N][N];
int w[N];
int bits[S];
int deg[N];
int sum[S], isum[S];
int fa[N];
int f[N][S], g[N][S];

int find(int x) {
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

bool check(int s) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        deg[i] = 0;
    }
    int b = bits[s];
    for (int i = 1; i <= n; i++) {
        if (!(s & bin[i-1])) continue;
        for (int j = i+1; j <= n; j++) {
            if (!(s & bin[j-1])) continue;
            if (!mp[i][j]) continue;
            deg[i]++;
            deg[j]++;
            if (find(i) != find(j)) {
                fa[find(i)] = fa[find(j)];
                b--;
            }
        }
    }
    if (b > 1) return true;
    for (int i = 1; i <= n; i++)
        if (deg[i] & 1) return true;
    return false;
}

int qPow(int x, int k) {
    int rtn = 1;
    for (; k; k >>= 1, x = (ll)x * x % P)
        if (k & 1) rtn = (ll)rtn * x % P;
    return rtn;
}

void fmt(int f[], int sgn) {
    for (int i = 1; i < bin[n]; i <<= 1)
        for (int j = 0; j < bin[n]; j++)
            if (j & i) (f[j] += sgn * f[j^i]) %= P;
}

int main() {
    bin[0] = 1;
    for (int i = 1; i < N; i++)
        bin[i] = bin[i-1] << 1;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        mp[u][v] = mp[v][u] = true;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int s = 0; s < bin[n]; s++) {
        for (int i = 1; i <= n; i++) {
            if (s & bin[i-1]) {
                sum[s] += w[i];
                bits[s]++;
            }
        }
        sum[s] = qPow(sum[s], p);
        isum[s] = qPow(sum[s], P-2);
        if (check(s))
            g[bits[s]][s] = sum[s];
    }
    for (int i = 0; i <= n; i++)
        fmt(g[i], 1);
    f[0][0] = 1;
    fmt(f[0], 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++)
            for (int k = 0; k < bin[n]; k++)
                (f[i][k] += (ll)f[j][k] * g[i-j][k] % P) %= P;
        fmt(f[i], -1);
        for (int j = 0; j < bin[n]; j++)
            f[i][j] = (ll)f[i][j] * isum[j] % P;
        if (i != n)
            fmt(f[i], 1);
    }
    printf("%d\n", (f[n][bin[n]-1] + P) % P);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论