結果
問題 | No.2435 Order All Company |
ユーザー |
|
提出日時 | 2023-08-26 01:56:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,148 bytes |
コンパイル時間 | 4,699 ms |
コンパイル使用メモリ | 257,760 KB |
最終ジャッジ日時 | 2025-02-16 14:34:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;#define rep(i,n) for(int i=0;i<(int)(n);i++)using mint = atcoder::modint998244353;int n;using mat=vector<vector<mint>>;void tri(mat &a){rep(i,n-1){if(a.at(i).at(i)==0){for(int j=i+1;j<n;j++){if(a.at(j).at(i)!=0){swap(a.at(i),a.at(j));rep(k,n) a.at(j).at(k)*=-1;break;}}if(a.at(i).at(i)==0) continue;}for(int j=i+1;j<n;j++){mint p=a.at(j).at(i)/a.at(i).at(i);rep(k,n) a.at(j).at(k)-=a.at(i).at(k)*p;}}}int main(){int k;cin>>n>>k;vector<mat> g(k,mat(n,vector<mint>(n,0)));rep(i,k){int t;cin>>t;rep(lp,t){int a,b;cin>>a>>b;a--; b--;g.at(i).at(a).at(a)++;g.at(i).at(b).at(b)++;g.at(i).at(a).at(b)--;g.at(i).at(b).at(a)--;}}mint ans=0;rep(bit,(1<<k)){mat ad(n,vector<mint>(n,0));rep(i,k){if(bit>>i&1){rep(a,n) rep(b,n) ad.at(a).at(b)+=g.at(i).at(a).at(b);}}tri(ad);mint tmp=1;rep(i,n-1) tmp*=ad.at(i).at(i);if((k-__builtin_popcount(bit))%2==0) ans+=tmp;else ans-=tmp;}cout<<ans.val()<<endl;}