loj2540. 「PKUWC2018」随机算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了loj2540. 「PKUWC2018」随机算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2221字，纯文字阅读大概需要4分钟。

内容图文

题意

略。

题解

听说考场上暴力搜出独立集有90分
这道题的状态还是挺难找的。
初始排列为空。考虑设\(f_{s, i}\)表示当前状态，独立集为\(s\)，已经不在独立集里面（即与\(s\)中的点有连边）且还没有加入排列的点数为\(i\)。
则有初始状态\(f_{0, 0} = 1\)。
考虑转移，如果某一个点可以加入这个独立集，则：
\[ f_{s \cup \{x\}, i + \text{new}(x, s)} += f_{s, i} \ (x \notin s) \]
其中\(new(x, s)\)代表的是与\(x\)有连边，并且不属于\(s\)且不与\(s\)中任何点有连边的点的个数。
这个操作代表将\(x\)加入排列。
只有这样一种操作是不够的，考虑要把已经不在独立集里面且还没有加入排列的点加入排列，如果有\(i\)个这样的点，那么这次可以选择任何一个加入。
即
\[ f_{s, i - 1} += f_{s, i} \]
考虑到转移一定构成了一个DAG（先按集合\(s\)的偏序，再按点数\(i\)的偏序），所以是没问题的。
但是转移的时候要注意后一种操作是可以不断地做的，所以\(i\)的枚举方向是从\(n\)到\(1\)。
复杂度\(\mathcal O(2 ^ n n ^ 2)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N = 20, M = 1 << 20, mod = 998244353;
int n, m, c, ans, e[M], d[N][M], t[M], f[N][M];
int power (int x, int y) {
    int ret = 1;
    for ( ; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) {
            ret = 1ll * ret * x % mod;
        }
    }
    return ret;
}
void U (int &x, int y) {
    if ((x += y) >= mod) {
        x -= mod;
    }
}
int main () {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        e[1 << i] = 1 << i;
    }
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y, --x, --y;
        e[1 << x] |= 1 << y, e[1 << y] |= 1 << x;
    }
    m = 1 << n;
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < m; ++s) {
            if (s >> i & 1) {
                e[s] |= e[s ^ 1 << i];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < m; ++s) {
            if (~e[s] >> i & 1) {
                d[i][s] = __builtin_popcount(e[s] | e[1 << i] ^ (1 << i)) - __builtin_popcount(e[s]);
            }
        }
    }
    f[0][0] = 1;
    for (int s = 0; s < m; ++s) {
        for (int i = n; i; --i) {
            U(f[i - 1][s], 1ll * f[i][s] * i % mod);
        }
        for (int i = n; ~i; --i) {
            if (f[i][s]) {
                for (int x = 0; x < n; ++x) {
                    if (~e[s] >> x & 1) {
                        U(f[i + d[x][s]][s | 1 << x], f[i][s]);
                    }
                }
            }
        }
    }
    for (int s = 0; s < m; ++s) {
        if (f[0][s]) {
            if (__builtin_popcount(s) > c) {
                c = __builtin_popcount(s), ans = 0;
            }
            if (__builtin_popcount(s) == c) {
                U(ans, f[0][s]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans = 1ll * ans * power(i, mod - 2) % mod;
    }
    cout << ans << endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的loj2540. 「PKUWC2018」随机算法全部内容，希望文章能够帮你解决loj2540. 「PKUWC2018」随机算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---