結果
問題 | No.2435 Order All Company |
ユーザー |
![]() |
提出日時 | 2023-08-18 23:06:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 3,318 bytes |
コンパイル時間 | 3,465 ms |
コンパイル使用メモリ | 257,320 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 09:43:06 |
合計ジャッジ時間 | 4,419 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 998'244'353; //const ll mod = 1'000'000'007; //const ll mod = 67'280'421'310'721; struct mint{ long long x; mint(long long x=0):x((x%mod+mod)%mod){} mint operator-() const{ return mint(-x); } mint& operator+=(const mint& a){ if((x+=a.x)>=mod)x-=mod; return *this; } mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod)x-=mod; return *this; } mint& operator*=(const mint& a){ (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const{ mint res(*this); return res+=a; } mint operator-(const mint& a) const{ mint res(*this); return res-=a; } mint operator*(const mint& a) const{ mint res(*this); return res*=a; } mint pow(long long n) const { assert(0 <= n); mint a = *this, r = 1; while (n) { if (n & 1) r *= a; a *= a; n >>= 1; } return r; } mint inv() const{ return pow(mod-2); } mint& operator/=(const mint& a){ return (*this)*=a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } bool operator==(const mint& a) const { return x == a.x; } bool operator<(const mint& a) const{ return x < a.x; } }; template < typename mint > mint det(vector<vector<mint>> a){ int n = a.size(); assert(a[0].size()==n); mint ans = 1; for(int i = 0;i<n;i++){ int ni = -1; for(int j = i;j<n;j++){ if(a[j][i].x!=0){ ni = j; break; } } if(ni==-1) return 0; if(ni!=i) ans *= -1; for(int j = i;j<n;j++) swap(a[i][j],a[ni][j]); ans *= a[i][i]; mint inv = a[i][i].inv(); for(int j = i + 1;j<n;j++){ mint tmp = a[j][i] * inv; for(int k = i;k<n;k++) a[j][k] -= tmp * a[i][k]; } } return ans; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,k; cin>>n>>k; vector<int> t(k); vector<vector<int>> a(k),b(k); for(int i = 0;i<k;i++){ cin>>t[i]; a[i].resize(t[i]); b[i].resize(t[i]); for(int j = 0;j<t[i];j++){ cin>>a[i][j]>>b[i][j]; a[i][j]--; b[i][j]--; } } mint ans = 0; for(int i = 0;i<1<<k;i++){ vector<vector<mint>> dat(n,vector<mint>(n,0)); for(int j = 0;j<k;j++) if(i>>j&1){ for(int l = 0;l<t[j];l++){ dat[a[j][l]][b[j][l]] -= 1; dat[b[j][l]][a[j][l]] -= 1; dat[a[j][l]][a[j][l]] += 1; dat[b[j][l]][b[j][l]] += 1; } } vector<vector<mint>> use (n-1,vector<mint>(n-1,0)); for(int j = 0;j<n-1;j++){ for(int l = 0;l<n-1;l++) use[j][l] = dat[j+1][l+1]; } int now = __builtin_popcount(i); if(now%2==k%2) ans += det<mint>(use); else ans -= det<mint>(use); } cout<<ans<<endl; }