Luogu p5406 [thupc2019] find tree

https://www.luogu.com.cn/problem/P5406

First of all, realize that this problem is not an optimization problem , It's a counting problem （ This alone is not simple ）

Consider what the matrix tree theorem calculates
$$\sum _T\prod w_{e\in T}$$

here $\prod$ Not necessarily multiplication , These operations given in the title can

So we can construct set power series $x^w$, be aware $FWT$ It's a linear operation , Can stack , First $FWT$ End , Find a determinant , And then again $IDFT$ Just go back

code:

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N = (1 << 12) + 5;
const int inv2 = (mod + 1) / 2;
char st[15];
void fwt(ll *a, int n, int o) {
    
    for(int len = 2, pos = 1; len <= n; len <<= 1, pos ++) {
    
        if(st[pos] == '|') {
    
            for(int j = 0; j < n; j += len)
                for(int k = j; k < j + (len >> 1); k ++)
                    a[k + (len >> 1)] = (a[k + (len >> 1)] + o * a[k] + mod) % mod;
        }
        if(st[pos] == '&') {
    
            for(int j = 0; j < n; j += len)
                for(int k = j; k < j + (len >> 1); k ++)
                    a[k] = (a[k] + o * a[k + (len >> 1)] + mod) % mod;
        }
        if(st[pos] == '^') {
    
            for(int j = 0; j < n; j += len)
                for(int k = j; k < j + (len >> 1); k ++) {
    
                    int X = a[k], Y = a[k + (len >> 1)];
                    a[k] = (X + Y) % mod, a[k + (len >> 1)] = (X - Y + mod) % mod;
                    if(o == -1) a[k] = a[k] * inv2 % mod, a[k + (len >> 1)] = a[k + (len >> 1)] * inv2 % mod;
                }
        }
    }
}
ll qpow(ll x, ll y) {
    
    ll ret = 1;
    for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
ll a[75][75];
ll DET(int n) {
    
    ll ans = 1;
    for(int i = 1; i <= n; i ++) {
    
        int j = i;
        for(int k = i + 1; k <= n; k ++) if(a[k][i]) j = k;
        if(j != i) {
    
            ans = (mod - ans);
            swap(a[i], a[j]);
        }
        if(!a[i][i]) return 0;
        for(int j = i + 1; j <= n; j ++) {
    
            ll t = a[j][i] * qpow(a[i][i], mod - 2) % mod;
            for(int k = i; k <= n; k ++) {
    
                a[j][k] = (a[j][k] - t * a[i][k] % mod + mod) % mod;
            }
        }
    }
    for(int i = 1; i <= n; i ++) ans = ans * a[i][i] % mod;
    return ans;
}
int n, m, w, lim;
ll in[75][75][N], ans[N];
int main() {
    
    scanf("%d%d", &n, &m);
    scanf("%s", st + 1);
    w = strlen(st + 1);
    lim = (1 << w);
    for(int i = 1; i <= m; i ++) {
    
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        in[u][v][c] --, in[v][u][c] --;
        in[u][u][c] ++, in[v][v][c] ++;
    }
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            for(int k = 0; k < lim; k ++)
                in[i][j][k] = (in[i][j][k] + mod) % mod;
    

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++) 
            fwt(in[i][j], lim, 1);
    
    for(int c = 0; c < lim; c ++) {
    
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                a[i][j] = in[i][j][c];
        ans[c] = DET(n - 1);
    }
    fwt(ans, lim, -1);
    for(int i = lim - 1; i >= 0; i --) {
    
        if(ans[i]) {
    printf("%d", i); return 0;}
    }
    printf("-1");
    return 0;
}