萌萌 FWT 题。
仙人掌满足任意一条边只在至多一个环上，因此要求生成树，只需要每个环断一条边即可。显然生成树上边权异或和等于所有边异或和再异或上所有断的边。
设所有边异或和为 \(s\)，第 \(i\) 个环上有 \(c_{i,j}\) 条边权为 \(j\) 的边。
令 \(F_0(z)=[z=s]\)，\(F_i(z)=c_{i,z}\)。定义 \((F\stackrel{\operatorname{xor}}{*}G)(z)=\sum\limits_{i\operatorname{xor} j=z}F(i)G(j)\)。
使用 FWT 计算出 \(\prod\limits^{\operatorname{xor}}F_i\)，其第 \(z\) 项的值即为边权异或和为 \(z\) 的生成树个数，从小到大枚举 \(z\) 找出第一个可行解并输出即可。
需要注意的是，在第 \(31\) 个测试点，最小异或生成树个数对 \(10^9+7\) 取模恰好余 \(0\)，会使得我们漏掉最优解，因此需要双模数。
时间复杂度为 \(O(kn\log n)\)，其中 \(k\) 为环数，值域视为与 \(n\) 同阶。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 131072, mod1 = 1e9+7, mod2 = 1e9+9;
ll n, m, xsum, F[N], G[N], f[N], g[N], fa[N], val[N], dfn[N], tms;
vector<tuple<ll, ll>> e[N];
vector<vector<ll>> cyc;
template<ll mod, ll flg>
void FWT_xor(ll* a, ll n) {
ll mul = flg == +1 ? 1 : (mod + 1) / 2;
for(ll o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for(ll i = 0; i < n; i += o)
rep(j, 0, k-1) {
a[i+j] += a[i+j+k];
a[i+j+k] = a[i+j] + 2 * (mod - a[i+j+k]);
a[i+j] *= mul;
a[i+j+k] *= mul;
a[i+j] %= mod;
a[i+j+k] %= mod;
}
}
void dfs(ll u, ll f, ll w) {
fa[u] = f;
val[u] = w;
dfn[u] = ++tms;
for(auto& i : e[u]) {
ll v = get<0>(i), w = get<1>(i);
if(v != f) {
if(!dfn[v]) dfs(v, u, w);
else if(dfn[v] < dfn[u]) {
cyc.push_back({});
cyc.back().push_back(w);
for(ll k = u; k != v; k = fa[k]) cyc.back().push_back(val[k]);
}
}
}
}
int main() {
scanf("%lld%lld", &n, &m);
rep(i, 1, m) {
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
xsum ^= w;
}
F[xsum] = G[xsum] = 1;
FWT_xor<mod1, +1>(F, N);
FWT_xor<mod2, +1>(G, N);
dfs(1, 0, 0);
for(auto& c : cyc) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for(ll i : c) ++f[i], ++g[i];
FWT_xor<mod1, +1>(f, N);
FWT_xor<mod2, +1>(g, N);
rep(i, 0, N-1) {
F[i] = F[i] * f[i] % mod1;
G[i] = G[i] * g[i] % mod2;
}
}
FWT_xor<mod1, -1>(F, N);
FWT_xor<mod2, -1>(G, N);
rep(i, 0, N-1) {
if(F[i] || G[i]) {
printf("%lld %lld\n", i, F[i]);
break;
}
}
return 0;
}