1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| #include <bits/stdc++.h> #define re read() #define ll long long #define mkp(a, b) make_pair(a, b) #define mst(a, c) memset(a, c, sizeof(a)) #define rep(a, b, c) for(int a = b; a <= c; a++) #define per(a, b, c) for(int a = b; a >= c; a--) using namespace std; const int MOD = 998244353; int read() { int num = 0; bool f = 0; char ch = getchar(); while(ch < '0' || ch > '9') {f = (ch == '-'); ch = getchar();} while(ch >= '0' && ch <= '9') {num = (num << 1) + (num << 3) + ch - '0'; ch = getchar();} return f? -num : num; } struct SF { int u, v, w; }e[10005]; ll qpow(ll a, ll b) { ll ans = 1; while(b > 0) { if(b & 1) ans = ans * a % MOD; b >>= 1; a = a * a % MOD; } return ans; } int n, m, cnt; char str[15][15]; ll a[115][115]; void init(ll x, int ff) { mst(a, 0); rep(i, 1, m) { int u = e[i].u, v = e[i].v, w = e[i].w; if(ff || x & w) { a[u][v]--, a[u][u]++; a[v][u]--, a[v][v]++; } } } ll det(int x) { rep(i, 1, x) rep(j, 1, x) a[i][j] = (a[i][j] + MOD) % MOD; ll res = 1, f = 1; rep(i, 1, x) { rep(j, i + 1, x) { ll A = a[i][i], B = a[j][i]; while(B) { ll tmp = A / B; A %= B; swap(A, B); rep(k, i, x) a[i][k] = (a[i][k] - tmp * a[j][k] % MOD + MOD) % MOD; rep(k, i, x) swap(a[i][k], a[j][k]); f = -f; } } if(!a[i][i]) return 0; res = (res * a[i][i]) % MOD; } if(f == -1) return (MOD - res) % MOD; return res; } int solve() { n = re, m = re; rep(i, 1, m){ e[i].u = re, e[i].v = re, e[i].w = re; } ll x = 1, ans = 0; rep(i, 0, 31){ init(x, 0); ans += 1ll * det(n - 1) * x % MOD; if(ans >= MOD) ans -= MOD; x = x * 2; } init(0, 1); ll tt = det(n - 1); tt = qpow(tt, MOD - 2); ans = 1ll * ans * tt % MOD; printf("%d\n", ans); return 0; } int main() { per(_,re,1) solve(); }
|