結果
問題 | No.3105 Parallel Connection and Spanning Trees |
ユーザー |
![]() |
提出日時 | 2025-01-13 03:33:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 271 ms / 5,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 2,535 ms |
コンパイル使用メモリ | 204,524 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-28 22:57:24 |
合計ジャッジ時間 | 6,565 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
// naive #include<bits/stdc++.h> using namespace std; #include<atcoder/modint> typedef atcoder::modint998244353 mint; mint det(vector<vector<mint>> &a){ assert(a.size() == a[0].size()); int n = (int)a.size(); vector<vector<mint>> b = a; int piv = 0; mint ret = 1; for (int j=0; j<n; j++){ for (int i=piv; i<n; i++){ if (b[i][j] != 0){ swap(b[i], b[piv]); if (i != piv) ret = -ret; mint ip = b[piv][j].inv(); for (int l=0; l<n; l++){ if (l != piv){ mint tmp = ip * b[l][j]; for (int k=j; k<n; k++){ b[l][k] -= tmp * b[piv][k]; } } } ret *= b[piv][j]; for (int k=j; k<n; k++){ b[piv][k] *= ip; } piv++; break; } } } for (int i=0; i<n; i++){ ret *= b[i][i]; } return ret; } int main() { int k; cin >> k; vector dp(k+1, vector<mint>(2)); dp[0][0] = 1; for(int i=0; i<k; i++) { int n, m; cin >> n >> m; vector mat1(n-1, vector<mint>(n-1)); for (int i=0; i<m; i++) { int x, y; cin >> x >> y; x--; y--; if (x-1 >= 0 && y-1 >= 0) { mat1[x-1][y-1] -= 1; mat1[y-1][x-1] -= 1; } if (x-1 >= 0) { mat1[x-1][x-1] += 1; } if (y-1 >= 0) { mat1[y-1][y-1] += 1; } } vector<vector<mint>> mat2 = mat1; mat2[0][0] += 1; mint val1 = det(mat1); mint val2 = det(mat2); mint type123 = val1; mint type4 = val2 - val1; dp[i+1][1] += dp[i][0] * type123; dp[i+1][0] += dp[i][0] * (type123 * 2 + type4); dp[i+1][1] += dp[i][1] * (type123 * 2 + type4); } cout << dp[k][1].val() << endl; }