結果
問題 | No.2435 Order All Company |
ユーザー |
![]() |
提出日時 | 2023-08-18 22:34:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 2,243 bytes |
コンパイル時間 | 944 ms |
コンパイル使用メモリ | 81,136 KB |
最終ジャッジ日時 | 2025-02-16 10:21:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; ll mod = 998244353; ll pw(ll a,ll x){ ll ret = 1; while(x){ if(x&1) (ret *= a) %= mod; (a *= a) %= mod; x /= 2; } return ret; } ll inv(ll x){return pw(x,mod - 2);} ll det(vector<vector<ll>> a){ int i,j,k,n = a.size(); ll ret = 1; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[i][j]<0) a[i][j] += mod; } } for(i=0;i<n;i++){ int piv = -1; for(j=i;j<n;j++){ if(a[j][i]!=0){ piv = j; break; } } if(piv==-1) break; swap(a[piv],a[i]); if(piv!=i) ret *= -1; for(j=i + 1;j<n;j++){ ll x = a[j][i]*inv(a[i][i])%mod; for(k=0;k<n;k++){ (a[j][k] += mod - a[i][k]*x%mod) %= mod; } } } if(ret<0) ret += mod; for(i=0;i<n;i++) (ret *= a[i][i]) %= mod; return ret; } ll matrix_tree(vector<vector<ll>> mat){ int i,j,k,n = mat.size(); if(n==1) return 1; vector<vector<ll>> mat2(n - 1,vector<ll>(n - 1)); //(n,n) no yoinshi for(i=0;i<n - 1;i++){ for(j=0;j<n - 1;j++){ if(i==j){ for(k=0;k<n;k++){ if(k!=i) mat2[i][i] += mat[i][k]; } }else{ mat2[i][j] = mod - mat[i][j]; } } } return det(mat2); } vector<pair<int,int>> v[10]; int main(){ int i,j,n,k; cin >> n >> k; for(i=0;i<k;i++){ int t; cin >> t; for(j=0;j<t;j++){ int a,b; cin >> a >> b; a--; b--; v[i].push_back({a,b}); } } ll ans = 0; for(i=0;i<(1<<k);i++){ int c = 0; vector<vector<ll>> mat(n,vector<ll>(n,0)); for(j=0;j<k;j++){ if(i>>j&1) c++; else{ for(auto p:v[j]){ mat[p.first][p.second]++; mat[p.second][p.first]++; } } } if(c&1){ ans += mod - matrix_tree(mat); }else{ ans += matrix_tree(mat); } (ans %= mod); } cout << ans << "\n"; }