BZOJ5153 州区划分

bzoj上不能测试这题,需要下载数据手动测试,我写了个linux上的简易测试脚本
下载本地测试文件,将自己的程序重命名为 5153.cpp 放进解压后的文件夹里,然后把从 bzoj 上下载的数据也放进去,输入 sh test.sh 等待结果就行
update: 后来发现 UOJ 上也有

题面

链接

题解

设 $f _ S$ 为点集为 $S$ 时的答案,$g _ S$ 为点集为 $S$ 且点集对应的图合法时集合中所有点的权值和,$sum _ S$ 为点集 $S$ 中所有点的权值和
显然,当 $S$ 合法时 $g _ S=sum _ S$ ,否则 $g _ S=0$
根据题目
$$ f _ S=\sum _ {T\subseteq S} f _ {S-T}\times \big{(}\frac{g _ T}{sum _ S}\big{)}^p $$

将 $sum _ S$ 提到前面去
$$ f_S=\big{(}\frac{1}{sum _ S}\big{)}^p \sum _ {T\subseteq S}f _ {S-T}\cdot g _ T^p $$
然后后面可以用子集卷积做
现在问题只剩判断 $S$ 是否合法
发现当且仅当 $S$ 对应的图不是一张欧拉图(即不存在欧拉回路)时 $S$ 合法
某个无向图是欧拉图当且仅当它是所有点度数为偶数的连通图,然后判断一下就好了
复杂度 $\mathcal{O(n ^ 2 2 ^ n)} $

代码

#define MAX_N 10000007
#define MOD 998244353

int N, M, P, U;
int deg[MAX_N], fa[MAX_N];
int w[MAX_N];
int sum[MAX_N], g[22][MAX_N], f[22][MAX_N];
int bitcnt[MAX_N];

struct edge {
    int u, v;
}e[507];

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

inline void merge (int x, int y) {
    int p = find(x), q = find(y);
    deg[x]++, deg[y]++;
    if (p != q)
        fa[p] = q;
}

inline int quick_pow (int x, int p) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = 1LL * ans * x % MOD;
        x = 1LL * x * x % MOD;
        p >>= 1;
    }
    return ans;
}

inline void init () {
    for (int s = 0; s < U; ++s) {
        for (int i = 1; i <= N; ++i) {
            deg[i] = 0, fa[i] = i;
            if ((s >> i - 1) & 1)
                bitcnt[s]++, sum[s] += w[i];
        }
        sum[s] = quick_pow(sum[s], P);
        int u, v;
        for (int i = 1; i <= M; ++i) {
            u = e[i].u, v = e[i].v;
            if (((s >> u - 1) & 1) && ((s >> v - 1) & 1))
                merge(u, v);
        }
        int bl = -1;
        for (int i = 1; i <= N; ++i) {
            if (deg[i] & 1) {
                g[bitcnt[s]][s] = sum[s];
                break;
            }
            if ((s >> i - 1) & 1) {
                if (bl == -1) bl = find(i);
                else if (bl != find(i)) {
                    g[bitcnt[s]][s] = sum[s];
                    break;
                }
            }
        }
        sum[s] = quick_pow(sum[s], MOD - 2);
    }
}

inline void FMT (int *A, int M, int type) {
    for (int l = 1; l < M; l <<= 1) {
        for (int i = 0, L = l << 1; i < M; i += L) {
            for (int j = i, x, y; j < i + l; ++j) {
                A[j + l] = (1LL * A[j + l] + 1LL * type * A[j] + MOD) % MOD;
            }
        }
    }
}

int main () {
    read(N), read(M), read(P);
    U = 1 << N;
    for (int i = 1;i <= M; ++i)
        read(e[i].u), read(e[i].v);
    for (int i = 1; i <= N; ++i) read(w[i]);
    init();
    for (int i = 0; i <= N; ++i)
        FMT(g[i], U, 1);
    f[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        FMT(f[i - 1], U, 1);
        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] % MOD) % MOD;
            }
        }
        FMT(f[i], U, -1);
        for (int s = 0; s < U; ++s)
            if (bitcnt[s] == i) f[i][s] = 1LL * f[i][s] * sum[s] % MOD;
            else f[i][s] = 0;
    }
    printf("%d\n", f[N][U - 1]);
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注