Luogu

LOJ

分析

转化为计数问题，求每种权值的生成树个数。

考虑矩阵树定理
$$
\sum_T\prod_{e\in T} w_e
$$
我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。

具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这一位是什么就做哪一种运算。另外，我们只需要判断系数是否为 $0$，所以可以对若干个质数取模。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 70 + 5;
const int mod = 998244353, inv2 = 499122177;
int upd(const int &x) { return x + (x >> 31 & mod); }
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int n, m, w;
char s[15];
int C[N][N][1 << 12], A[N][N], cnt[1 << 12];

void FWT(int *A, int n, int op) {
    for (int i = 1, p = 0; i < n; i <<= 1, ++p) {
        if (s[p] == '|') {
            for (int j = 0; j < n; j += i << 1)
                for (int k = 0; k < i; ++k) {
                    if (op == 1) A[j + k + i] = upd(A[j + k + i] + A[j + k] - mod);
                    else A[j + k + i] = upd(A[j + k + i] - A[j + k]);
                }
        }
        if (s[p] == '&') {
            for (int j = 0; j < n; j += i << 1)
                for (int k = 0; k < i; ++k) {
                    if (op == 1) A[j + k] = upd(A[j + k] + A[j + k + i] - mod);
                    else A[j + k] = upd(A[j + k] - A[j + k + i]);
                }
        }
        if (s[p] == '^') {
            for (int j = 0; j < n; j += i << 1)
                for (int k = 0; k < i; ++k) {
                    int x = A[j + k], y = A[j + k + i];
                    A[j + k] = upd(x + y - mod), A[j + k + i] = upd(x - y);
                    if (op == -1) {
                        A[j + k] = 1ll * A[j + k] * inv2 % mod;
                        A[j + k + i] = 1ll * A[j + k + i] * inv2 % mod;
                    }
                }
        }
    }
}

int det(int n) {
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (!A[i][i]) {
            for (int j = i + 1; j <= n; ++j)
                if (A[j][i]) { swap(A[i], A[j]), ans = mod - ans; break; }
        }
        if (!A[i][i]) return 0;
        ans = 1ll * ans * A[i][i] % mod;
        int inv = qpow(A[i][i], mod - 2);
        for (int j = i + 1; j <= n; ++j) {
            int t = mod - 1ll * A[j][i] * inv % mod;
            for (int k = i; k <= n; ++k)
                A[j][k] = (A[j][k] + 1ll * t * A[i][k]) % mod;
        }
    }
    return ans;
}

int main() {
    n = read(), m = read();
    scanf("%s", s), w = strlen(s);
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        ++C[u][u][w], ++C[v][v][w];
        --C[u][v][w], --C[v][u][w];
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            for (int k = 0; k < 1 << w; ++k)
                C[i][j][k] = upd(C[i][j][k]);
            FWT(C[i][j], 1 << w, 1);
        }
    for (int i = 0; i < 1 << w; ++i) {
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                A[j][k] = C[j][k][i];
        cnt[i] = det(n - 1);
    }
    FWT(cnt, 1 << w, -1);
    for (int i = (1 << w) - 1; ~i; --i)
        if (cnt[i]) { printf("%d\n", i); return 0; }
    puts("-1");
    return 0;
}