给定一个有向图任意两点间的关系:要么强连通,要么弱联通,要么恰好只有一个方向可达。要求构造一个有向图使得边数最小,直接输出边数即可。n \leq 46

首先非常明显的是我们可以直接抛弃掉 \text{or} 边,直接保证整张图是弱联通的即可。对于 \text{and} 边我们可以把他们连到同一个联通块里,对于 \text{xor} 边我们转化为联通块之间的关系处理。

显然把一个联通块连成环,联通块之间连成一条链一定是可行方案,但不一定足够优秀。考虑到如果两个联通块之间的如果没有 \text{xor} 边,把他们缩到一起是没有关系的。同时发现如果联通块大小为 1,那么是否进行缩一起不会影响答案;因此只需要状压大小大于 1 的联通块即可,个数记为 mm \leq 23

显然可以用一个 DP f[S][k] 表示用 k 条边讲状态 S 的联通块连一起是否可行,显然:

f[n][m] = \sum_{i | j = n} f[i][m - 1] \cdot f[j][0]

如果直接 FWT 的话单次时间复杂度为 \mathcal O(2^m \times m),一共要做 m 次,总时间复杂度为 \mathcal O(2^m \times m^2),并不能通过此题。

考虑到其实我们只需要知道 f[2^m-1][...] 这一位,可以先处理出 UFWT 过程中对其的贡献系数,之后每次点值乘好了以后不用 UFWT 回去,而是直接 2^m 扫一遍判断即可。时间复杂度为 \mathcal O(n^2 + 2^m \times m),可以通过此题。

在 zx2003 的指导下,关于求或的单点 IFWT 系数还有个比较通用的公式。

FWT 的过程可以理解为一个行向量右乘一个矩阵得到新的行向量,这个矩阵就是我们想要的系数,可以证明

a[x][y] = \left\{ \begin{aligned} &(-1)^{\operatorname{popcount}(x ^ y)} &(x \& y = x) \\ &0 &(x \& y \neq x) \end{aligned} \right.

代码:

// =================================
//   author: memset0
//   date: 2019.05.08 13:55:10
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
    if (s != "") std::cout << s << ": ";
    for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 50, M = 1 << 23;
char c[N][N];
bool tag[N][N];
int n, m, cnt, ans, sum;
int id[N], fa[N], mrk[N];
unsigned ll f[M], g[M], s[M];

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

inline void fwt(unsigned ll *a, int lim) {
    for (int len = 1; len < lim; len <<= 1)
        for (int i = 0; i < lim; i += (len << 1))
            for (int j = 0; j < len; j++) {
                a[i + j + len] = a[i + j] + a[i + j + len];
            }
}

void main() {
    read(n);
    for (int i = 1; i <= n; i++)
        scanf("%s", c[i] + 1);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c[i][j] == 'A') {
                fa[find(i)] = find(j);
            }
    for (int i = 1; i <= n; i++)
        if (find(i) == i) {
            std::vector<int> s;
            for (int j = 1; j <= n; j++)
                if (find(j) == i)
                    s.push_back(j);
            ++cnt;
            if (s.size() > 1) {
                ++m, sum += s.size();
                for (auto x : s) id[x] = m;
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c[i][j] == 'X') {
                int f_i = find(i), f_j = find(j);
                if (f_i == f_j) {
                    puts("-1"); return;
                } else {
                    tag[id[f_i]][id[f_j]] = 1;
                }
            }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++)
            if (tag[i][j])
                mrk[i] |= 1 << (j - 1);
    }
    for (int x = 0; x < (1 << m); x++) {
        f[x] = 1;
        for (int i = 1; i <= m; i++)
            if (((x >> (i - 1)) & 1) && (x & mrk[i])) {
                f[x] = 0;
                break;
            }
    }
    // print(mrk, 1, m, "mrk");
    // print(f, 0, (1 << m) - 1, "F");
    if (f[(1 << m) - 1]) ans = 0;
    else {
        fwt(f, 1 << m);
        for (int x = 0, y = (1 << m) - 1; x < (1 << m); x++)
            g[x] = __builtin_popcount(x ^ y) & 1 ? -1 : 1;
        // print(f, 0, (1 << m) - 1, "F");
        // print(g, 0, (1 << m) - 1, "G");
        for (int x = 0; x < (1 << m); x++) s[x] = f[x];
        for (ans = 1; ; ans++) {
            for (int x = 0; x < (1 << m); x++) s[x] = s[x] * f[x];
            unsigned ll sum = 0;
            for (int x = 0; x < (1 << m); x++) sum += s[x] * g[x];
            // print(s, 0, (1 << m) - 1, "S");
            // printf(">> %d => %d\n", ans, sum);
            if (sum) break;
        }
        // printf(">> ans = %d\n", ans);
    }
    // printf("sum = %d cnt = %d m = %d ans = %d\n", sum, cnt, m, ans);
    print(sum + ans + (m ? cnt - m : cnt - m - 1), '\n');
}

} signed main() {
#ifdef MEMSET0_LOCAL_ENVIRONMENT
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), 0;
}

巧妙的思路 容斥 FWT 状压

洛谷5281 [ZJOI2019]Minimax搜索
上一篇 «
洛谷2048 [NOI2010]超级钢琴
» 下一篇