题意
- 给定一个无向图，定义一个生成树的权值为按位(oplus_{o_i})的结果
- 求最大的生成树
先将问题转化一下，把求最大的生成树，转化为存不存在某个权值的生成树，于是就可以利用(matrix-tree)定理求出某个权值的生成树的个数，但这里的边权可以先按照(oplus_{o_i})的规则fwt一下，最后再将行列式的值ifwt回来
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define mod 998244353
#define maxn 70
using namespace std;
int n, m, w, a[maxn + 5], lim, inv2;
int fp(int x, int y){
int asi = 1;
while(y){
if(y & 1) asi = 1ll * asi * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return asi;
}
struct Pol{
int x[4096];
void out(){
For(i, 0, lim - 1) cout << x[i] << " ";
cout << endl;
}
void fwt(int ty){
for(int i = 2, now = 0; i <= lim; i <<= 1, now++){
int ii = i >> 1;
for(int j = 0; j < lim; j += i){
For(p, j, j + ii - 1){
if(!ty){
int tem = x[p], tem1 = x[p + ii];
if(a[now] == 0) x[p] = (tem + tem1) % mod;
if(a[now] == 1) x[p + ii] = (tem + tem1) % mod;
if(a[now] == 2){
x[p] = (tem - tem1 + mod) % mod;
x[p + ii] = (tem + tem1) % mod;
}
}
else{
int tem = x[p], tem1 = x[p + ii];
if(a[now] == 0) x[p] = (tem - tem1 + mod) % mod;
if(a[now] == 1) x[p + ii] = (tem1 - tem + mod) % mod;
if(a[now] == 2){
x[p] = 1ll * inv2 * (tem + tem1) % mod;
x[p + ii] = 1ll * inv2 * (tem1 - tem + mod) % mod;
}
}
}
}
}
}
} zer;
Pol operator + (cst Pol &x, cst Pol &y){Pol asi; For(i, 0, lim - 1) asi.x[i] = (x.x[i] + y.x[i]) % mod; return asi;}
Pol operator - (cst Pol &x, cst Pol &y){Pol asi; For(i, 0, lim - 1) asi.x[i] = (x.x[i] - y.x[i] + mod) % mod; return asi;}
Pol operator * (cst Pol &x, cst Pol &y){Pol asi; For(i, 0, lim - 1) asi.x[i] = 1ll * x.x[i] * y.x[i] % mod; return asi;}
Pol operator / (cst Pol &x, cst Pol &y){Pol asi; For(i, 0, lim - 1) asi.x[i] = 1ll * x.x[i] * fp(y.x[i], mod - 2) % mod; return asi;}
bool operator ! (cst Pol &x){For(i, 0, lim - 1) if(x.x[i]) return 0; return 1;}
struct Mat{
Pol x[maxn + 5][maxn + 5];
Pol get_det(){
int k = 0;
Pol asi;
For(i, 0, lim - 1) asi.x[i] = 1;
For(i, 1, n - 1){
if(!x[i][i]){
k++;
For(j, i + 1, n - 1){
if(!x[j][i]) continue;
For(p, i, n - 1) swap(x[i][p], x[j][p]);
break;
}
}
if(!x[i][i]) return zer;
asi = asi * x[i][i];
For(j, i + 1, n - 1){
Pol tem = x[j][i] / x[i][i];
For(p, i, n - 1) x[j][p] = x[j][p] - tem * x[i][p];
}
}
if(k & 1) For(i, 0, lim - 1) asi.x[i] = mod - asi.x[i];
return asi;
}
} ma;
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
char s[maxn + 5];
int main(){
//freopen("19.in", "r", stdin);
inv2 = fp(2, mod - 2);
read(n); read(m);
scanf("%s",s); w = strlen(s);
For(i, 0, w - 1){
if(s[i] == '|') a[i] = 1;
if(s[i] == '^') a[i] = 2;
}
lim = 1 << w;
For(i, 1, m){
int u, v, wi; read(u); read(v); read(wi);
ma.x[u][v].x[wi]--;
ma.x[v][u].x[wi]--;
ma.x[u][u].x[wi]++;
ma.x[v][v].x[wi]++;
}
For(i, 1, n - 1) For(j, 1, n - 1){
if(i ^ j) For(p, 0, lim - 1) ma.x[i][j].x[p] = (ma.x[i][j].x[p] + mod) % mod;
ma.x[i][j].fwt(0);
}
Pol tem = ma.get_det();
tem.fwt(1);
Rof(i, lim - 1, 0) if(tem.x[i]){printf("%d
", i); return 0;}
puts("-1");
return 0;
}