結果
問題 | No.3105 Parallel Connection and Spanning Trees |
ユーザー |
|
提出日時 | 2025-04-11 21:52:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 5,000 ms |
コード長 | 3,632 bytes |
コンパイル時間 | 1,690 ms |
コンパイル使用メモリ | 174,312 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-11 21:52:27 |
合計ジャッジ時間 | 4,129 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long const int p=998244353; int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}} int inv(int x) {return po(x,p-2);} mt19937 rnd; #define app push_back #define all(x) (x).begin(),(x).end() #ifdef LOCAL #define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__) #define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0) #else #define debug(...) #define debugv(v) #endif #define lob(a,x) lower_bound(all(a),x) #define upb(a,x) upper_bound(all(a),x) int det(vector<vector<int> > A) { if(A.empty()) return 1; int n=A.size();int m=A[0].size(); for(int i=0;i<n;++i) {for(int &x:A[i]) {x%=p;x+=p;x%=p;}} int bi=0; for(int i=0;i<n;++i) { if(bi==m) break; for(int j=i;j<n;++j) { if(A[j][bi]) { if(j!=i) {swap(A[i],A[j]);} break; } } if(A[i][bi]) { int o=inv(A[i][bi]); for(int j=i+1;j<n;++j) { int we=(A[j][bi]*o)%p; for(int k=bi;k<m;++k) { A[j][k]-=we*A[i][k];A[j][k]%=p;if(A[j][k]<0) A[j][k]+=p; } } } else { ++bi;--i;continue; } } int ans=1; for(int i=0;i<n;++i) { ans*=A[i][i];ans%=p; } return ans; } int trees(vector<vector<int> > A) { int n=A.size(); vector<vector<int> > B; for(int i=0;i<n;++i) { B.app({});B[i].resize(n); int s=0; for(int j=0;j<n;++j) { B[i][j]=(-A[i][j]);s+=A[i][j];s%=p; } B[i][i]=s; } vector<vector<int> > C; for(int i=0;i<n-1;++i) { C.app({});C[i].resize(n-1); for(int j=0;j<n-1;++j) { C[i][j]=B[i][j]; } } return det(C); } vector<vector<int> > collapse(vector<vector<int> > A) { int n=A.size(); vector<vector<int> > B(n-1,vector<int>(n-1,0)); for(int i=0;i<n-1;++i) { for(int j=0;j<n-1;++j) { if(i==0 && j==0) {B[i][j]=0;continue;} else if(i==0) { B[i][j]=(A[0][j+1] + A[1][j+1]); } else if(j==0) { B[i][j]=(A[i+1][0] + A[i+1][1]); } else { B[i][j]=A[i+1][j+1]; } } } return B; } int trees12(vector<vector<int> > A) { return trees(collapse(A)); } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int k;cin>>k; int res[k][2]; for(int i=0;i<k;++i) { int n,m;cin>>n>>m; vector<vector<int> > A(n,vector<int>(n,0)); for(int i=0;i<m;++i) { int x,y;cin>>x>>y;--x;--y;A[x][y]=1;A[y][x]=1; } int a1=trees(A);int a2=trees12(A); res[i][0]=(2*a1+a2)%p;res[i][1]=a1; debug(res[i][0],res[i][1]); } int dp[2]={1,0}; for(int i=0;i<k;++i) { int dp2[2]={0,0}; for(int was=0;was<2;++was) { for(int flag=0;flag<2;++flag) { if(was==1 && flag==1) continue; dp2[was+flag]+=dp[was]*res[i][flag];dp2[was+flag]%=p; } } copy(dp2,dp2+2,dp); } cout<<(dp[1]%p+p)%p; return 0; }