LOJ#6622. 「THUPC 2019」找树 / findtree（FWT+矩阵树）

https://loj.ac/problem/6622

• 求最大是假的，其实是求方案数。

• 每一位独立，每一位做不同的FWT后变点积，直接跑矩阵树即可。

• 矩阵树模一个质数，最好别取常见质数。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;

const int mo = 961661263;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

const ll ni2 = ksm(2, mo - 2);

const int N = 75;

int n, m, w;
char s[N];

void fwt(ll *a, int n, int f) {
	for(int i = 1, tp = 1; i < n; i *= 2, tp ++) for(int j = 0; j < n; j += 2 * i) ff(k, 0, i) {
		ll &u = a[j + k], &v = a[i + j + k];
		if(s[tp] == '&') {
			if(f == 1)  {
				u += v;
			} else {
				u -= v;
			}
		} else
		if(s[tp] == '|') {
			if(f == 1) {
				v += u;
			} else {
				v -= u;
			}
		} else
		if(s[tp] == '^') {
			ll x = u;
			u = (u + v);
			v = (x - v);
		}
	}
	ff(i, 0, n) a[i] %= mo;
	if(f == -1) {
		int cnt = 0;
		fo(i, 1, w) cnt += s[i] == '^';
		ll v = ksm(ni2, cnt);
		ff(i, 0, 1 << w) a[i] = a[i] * v %mo;
	}
}

ll x, y, z;

ll a[N][N][1 << 12], b[1 << 12];
ll c[N][N];

ll solve(ll (*a)[N], int n) {
	ll ans = 1;
	fo(i, 1, n) {
		int u = -1;
		fo(j, i, n) if(a[j][i]) { u = j; break;}
		if(u == -1) return 0;
		if(u > i) {
			ans = -ans;
			fo(j, i, n) swap(a[i][j], a[u][j]);
		}
		ll v = a[i][i];
		ans = ans * v % mo;
		v = ksm(v, mo - 2);
		fo(j, i, n) a[i][j] = a[i][j] * v % mo;
		fo(j, i + 1, n) if(a[j][i]) {
			v = -a[j][i];
			fo(k, i, n) a[j][k] = (a[j][k] + a[i][k] * v) % mo;
		}
	}
	return ans;
}

int main() {
	scanf("%d %d", &n, &m);
	scanf("%s", s + 1);
	w = strlen(s + 1);
	fo(i, 1, m) {
		scanf("%lld %lld %lld", &x, &y, &z);
		a[x][x][z] ++; a[y][y][z] ++;
		a[x][y][z] --; a[y][x][z] --;
	}
	fo(i, 1, n - 1) fo(j, 1, n - 1) fwt(a[i][j], 1 << w, 1);
	ff(s, 0, (1 << w)) {
		fo(i, 1, n - 1) fo(j, 1, n - 1) c[i][j] = a[i][j][s];
		b[s] = solve(c, n - 1);
	}
	fwt(b, 1 << w, -1);
	fd(i, (1 << w) - 1, 0) if(b[i]) {
		pp("%d
", i);
		return 0;
	}
	pp("-1
");
}