結果
| 問題 |
No.3105 Parallel Connection and Spanning Trees
|
| ユーザー |
 nonon
|
| 提出日時 | 2025-09-18 07:57:38 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 241 ms / 5,000 ms |
| コード長 | 6,565 bytes |
| コンパイル時間 | 3,871 ms |
| コンパイル使用メモリ | 291,068 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-09-18 07:57:47 |
| 合計ジャッジ時間 | 9,065 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }
template<typename mint>
struct matrix : vector<vector<mint>> {
using vector<vector<mint>>::vector;
matrix(int h, int w) : vector<vector<mint>>(h, vector<mint>(w)) {}
matrix &operator*=(const mint &r) {
for (vector<mint> &v : *this) {
for (mint &a : v) a *= r;
}
return *this;
}
matrix &operator/=(const mint &r) {
mint invr = r.inv();
return *this *= invr;
}
matrix &operator+=(const matrix& a) {
assert(this->size() == a.size());
for (int i = 0; i < int(this->size()); i++) {
assert((*this)[i].size() == a[i].size());
for (int j = 0; j < int((*this)[i].size()); j++) {
(*this)[i][j] += a[i][j];
}
}
return *this;
}
matrix &operator-=(const matrix& a) {
assert(this->size() == a.size());
for (int i = 0; i < int(this->size()); i++) {
assert((*this)[i].size() == a[i].size());
for (int j = 0; j < int((*this)[i].size()); j++) {
(*this)[i][j] -= a[i][j];
}
}
return *this;
}
matrix &operator*=(const matrix &a) {
int n = this->size(), m = a.size();
assert(m >= 1);
int l = a[0].size();
matrix res(n, vector<mint>(l));
for (int i = 0; i < n; i++) {
assert(int((*this)[i].size()) == m);
for (int k = 0; k < m; k++) {
for (int j = 0; j < l; j++) {
res[i][j] += (*this)[i][k] * a[k][j];
}
}
}
return *this = res;
}
matrix operator*(const mint &r) const { return matrix(*this) *= r; }
matrix operator/(const mint &r) const { return matrix(*this) /= r; }
matrix operator+(const matrix &a) const { return matrix(*this) += a; }
matrix operator-(const matrix &a) const { return matrix(*this) -= a; }
matrix operator*(const matrix &a) const { return matrix(*this) *= a; }
static constexpr matrix I(int n) {
matrix res(n, n);
for (int i = 0; i < n; i++) {
res[i][i] = 1;
}
return res;
}
static constexpr matrix O(int n) { return matrix(n, n); }
matrix pow(long long k) const {
matrix res = I(this->size()), a = *this;
while (k > 0) {
if (k & 1) res *= a;
a *= a;
k >>= 1;
}
return res;
}
mint det() const {
int n = this->size();
assert(n >= 1);
assert((*this)[0].size() == this->size());
mint res = 1;
matrix a = *this;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (a[j][i] != 0) {
if (i != j) res = -res;
swap(a[i], a[j]);
break;
}
}
if (a[i][i] != 0) {
for (int j = i + 1; j < n; j++) {
mint inv = a[j][i] * a[i][i].inv();
for (int k = i + 1; k < n; k++) {
a[j][k] -= a[i][k] * inv;
}
}
}
}
for (int i = 0; i < n; i++) {
res *= a[i][i];
}
return res;
}
matrix inv() const {
int n = this->size();
matrix a = *this, res = I(n);
for (int i = 0; i < n; i++) {
if (a[i][i] == 0) {
for (int j = i + 1; j < n; j++) {
if (a[j][i] != 0) {
swap(a[i], a[j]);
swap(res[i], res[j]);
break;
}
}
}
assert(a[i][i] != 0);
mint cef = a[i][i].inv();
for (int j = 0; j < n; j++) {
a[i][j] *= cef;
res[i][j] *= cef;
}
for (int j = 0; j < n; j++) {
if (j != i) {
cef = a[j][i];
for (int k = 0; k < n; k++) {
a[j][k] -= a[i][k] * cef;
res[j][k] -= res[i][k] * cef;
}
}
}
}
return res;
}
int rank() const {
matrix a = *this;
int h = a.size(), w = a[0].size();
int r = 0;
for (int j = 0; j < w && r < h; j++) {
int i = r;
while (i < h && a[i][j] == 0) i++;
if (i == h) continue;
swap(a[r], a[i]);
mint inv = a[r][j].inv();
for (i = r + 1; i < h; i++) {
mint cef = a[i][j] * inv;
for (int k = j; k < w; k++) {
a[i][k] -= a[r][k] * cef;
}
}
r++;
}
return r;
}
};
template<typename mint>
mint matrix_tree_theorem_adjacency(const vector<vector<int>> &a, int r = 0) {
int n = a.size();
if (n == 1) return 1;
auto p = [&](int u) -> int {
return u - (u > r);
};
matrix<mint> b(n - 1, n - 1);
for (int u = 0; u < n; u++) {
if (u == r) continue;
for (int v = 0; v < n; v++) {
b[p(u)][p(u)] += a[u][v];
if (v != r) {
b[p(u)][p(v)] -= a[u][v];
}
}
}
return b.det();
}
template<typename mint>
mint matrix_tree_theorem(const vector<vector<int>> &g, int r = 0) {
int n = g.size();
vector<vector<int>> a(n, vector<int>(n));
for (int u = 0; u < n; u++) {
for (int v : g[u]) a[u][v]++;
}
return matrix_tree_theorem_adjacency<mint>(a, r);
}
#include <atcoder/modint>
using mint = atcoder::modint998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K;
cin >> K;
mint ans1 = 1, ans2 = 0;
while (K--) {
int N, M;
cin >> N >> M;
vector<vector<int>> G(N);
for (int u, v; M--;) {
cin >> u >> v;
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
mint P = matrix_tree_theorem<mint>(G);
G[0].push_back(1);
G[1].push_back(0);
mint Q = matrix_tree_theorem<mint>(G) - P;
ans2 = P * ans1 + (2 * P + Q) * ans2;
ans1 = (2 * P + Q) * ans1;
}
cout << ans2.val() << endl;
}