結果
| 問題 |
No.3105 Parallel Connection and Spanning Trees
|
| コンテスト | |
| ユーザー |
 Kude
|
| 提出日時 | 2025-04-11 23:17:28 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 464 ms / 5,000 ms |
| コード長 | 6,189 bytes |
| コンパイル時間 | 3,545 ms |
| コンパイル使用メモリ | 301,396 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-04-11 23:17:43 |
| 合計ジャッジ時間 | 14,896 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 32 |
ソースコード
#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;
template<class T, int N>
struct Mat: std::array<std::array<T, N>, N> {
friend Mat<T, N> operator*(const Mat& A, const Mat& B) {
Mat<T, N> C = {};
for(int i = 0; i < N; i++) {
for(int k = 0; k < N; k++) {
for(int j = 0; j < N; j++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
friend std::array<T, N> operator*(const Mat& A, const std::array<T, N>& v) {
std::array<T, N> x = {};
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) x[i] += A[i][j] * v[j];
return x;
}
friend Mat<T, N> operator+(const Mat& A, const Mat& B) {
Mat<T, N> C;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
Mat<T, N>& operator*=(const Mat& A) { return *this = *this * A; }
Mat<T, N>& operator+=(const Mat& A) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
(*this)[i][j] += A[i][j];
}
}
}
static Mat<T, N> I() {
Mat<T, N> X = {};
for(int i = 0; i < N; i++) X[i][i] = 1;
return X;
}
Mat<T, N> pow(long long k) const {
assert(k >= 0);
auto X = *this;
auto Y = I();
while(k) {
if (k & 1) Y *= X;
k >>= 1;
if (k) X *= X;
}
return Y;
}
Mat<T, N> inv() const {
auto X = *this;
auto Y = I();
for(int p = 0; p < N; p++) {
bool ok = false;
for(int i = p; i < N; i++) {
if (X[i][p] != T()) {
ok = true;
if (i != p) {
// std::swap(X[i], X[p]);
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
std::swap(Y[i], Y[p]);
}
break;
}
}
assert(ok);
T c = 1 / X[p][p];
for(int j = p; j < N; j++) X[p][j] *= c;
for(int j = 0; j < N; j++) Y[p][j] *= c;
for(int i = 0; i < N; i++) if (i != p) {
T c = X[i][p];
for(int j = p; j < N; j++) X[i][j] -= c * X[p][j];
for(int j = 0; j < N; j++) Y[i][j] -= c * Y[p][j];
}
}
return Y;
}
T det() const {
if (N == 0) return T();
auto X = *this;
bool flag = false;
T res = 1;
bool ok = false;
for(int p = 0; p < N; p++) {
for(int i = p; i < N; i++) {
if (X[i][p] != T()) {
ok = true;
if (i != p) {
flag = !flag;
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
}
break;
}
}
if (!ok) return T();
// T = modint
for(int i = p + 1; i < N; i++) {
T c0 = 1, c1 = 0, d0 = 0, d1 = 1;
int a = X[p][p].val(), b = X[i][p].val();
while(true) {
if (b == 0) {
break;
}
int q = a / b;
a -= q * b;
c0 -= q * d0;
c1 -= q * d1;
if (a == 0) {
flag = !flag;
for(int j = p; j < N; j++) std::swap(X[i][j], X[p][j]);
std::swap(c0, d1);
std::swap(c1, d0);
break;
}
q = b / a;
b -= q * a;
d0 -= q * c0;
d1 -= q * c1;
}
for(int j = p; j < N; j++) {
T a = X[p][j], b = X[i][j];
T x = c0 * a + c1 * b, y = d0 * a + d1 * b;
X[p][j] = x;
X[i][j] = y;
}
}
res *= X[p][p];
}
if (flag) res = -res;
return res;
}
friend std::ostream& operator<<(std::ostream& os, const Mat<T, N>& A) {
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) os << A[i][j] << " \n"[j + 1 == N];
return os;
}
};
using M = Mat<mint, 62>;
} int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k;
cin >> k;
mint dp[2][2];
dp[0][0] = 1;
rep(_, k) {
mint ndp[2][2];
mint res[2][2];
int n, m;
cin >> n >> m;
M a;
for (int i = n; i < 60; i++) a[i][i] = 1;
rep(_, m) {
int u, v;
cin >> u >> v;
u--, v--;
a[u][v]--, a[v][u]--;
a[u][u]++, a[v][v]++;
}
a[0][0]++;
a[0][60]--;
a[60][0]--;
a[60][60]++;
a[1][1]++;
a[1][61]--;
a[61][1]--;
a[61][61]++;
rep(x, 2) rep(y, 2) {
M b = a;
if (x) {
rep(i, 60) b[0][i] = 0;
} else {
b[0][60] = 0;
}
if (y) {
rep(i, 60) b[0][i] = 0;
} else {
b[1][61] = 0;
}
res[x][y] = b.det();
}
rep(i, 2) rep(j, 2) rep(x, 2 - i) rep(y, 2 - j) ndp[i+x][j+y] += dp[i][j] * res[x][y];
swap(dp, ndp);
}
mint ans = -dp[1][1];
cout << ans.val() << '\n';
}