結果
問題 | No.1773 Love Triangle |
ユーザー |
![]() |
提出日時 | 2021-12-08 13:52:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 2,597 bytes |
コンパイル時間 | 2,205 ms |
コンパイル使用メモリ | 187,136 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-16 05:43:30 |
合計ジャッジ時間 | 9,665 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 90 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using namespace atcoder; using mint=modint1000000007; ostream& operator<<(ostream &os,mint a){os<<a.val();return os;} #define REP(i,n) for(int i=0;i<(n);i++) #define REP_(i,n) for(int i=0;i<(n);i++) template<typename K> struct Matrix{ typedef vector<K> vec; typedef vector<vec> mat; size_t r,c; mat M; Matrix(size_t r,size_t c):r(r),c(c),M(r,vec(c,K())){} Matrix(mat A):M(A){} vec& operator[](size_t k){return M[k];} const vec& operator[](size_t k)const{return M[k];} friend Matrix operator+(const Matrix &A,const Matrix &B){ assert(A.r==B.r&&A.c==B.c); Matrix res(A); REP_(i,A.r)REP_(j,A.c)res[i][j]+=B[i][j]; return res; } void operator+=(const Matrix &B){ assert(r==B.r&&c==B.c); REP_(i,r)REP_(j,c)M[i][j]+=B[i][j]; } friend Matrix operator*(const Matrix &A,const Matrix &B){ assert(A.c==B.r); Matrix res(A.r,B.c); REP_(i,A.r)REP_(k,A.c)REP_(j,B.c)res[i][j]+=A[i][k]*B[k][j]; return res; } void operator*=(const Matrix &B){ M(M*B); } static Matrix I(size_t n){ Matrix res(n,n); REP_(i,n)res[i][i]=K(1); return res; } Matrix pow(long long n)const{ assert(n>=0&&r==c); Matrix A(M),res=I(r); while(n){ if(n&1)res*=A; A*=A; n>>=1; } return res; } int rank() const{ Matrix A(M); int res=0; for(int k=0;k<c;k++){ for(int i=res+1;i<r&&A[res][k]==0;i++) if(A[i][k]!=0)swap(A[i],A[res]); if(A[res][k]==0)continue; for(int l=k+1;l<c;l++)A[res][l]/=A[res][k]; for(int j=res+1;j<r;j++) for(int l=k+1;l<c;l++) A[j][l]-=A[j][k]*A[res][l]; res++; } return res; } K det() const{ assert(r==c); Matrix A=M; K res(1); REP_(i,r){ for(int j=i+1;j<c&&A[i][i]==0;j++) if(A[j][i]!=0)swap(A[i],A[j]),res*=-1; res*=A[i][i]; if(A[i][i]==0)return res; for(int k=i+1;k<c;k++)A[i][k]/=A[i][i]; for(int j=i+1;j<r;j++) for(int k=i+1;k<c;k++) A[j][k]-=A[j][i]*A[i][k]; } return res; } }; #undef REP_ random_device seed_gen; mt19937_64 rnd(seed_gen()); #define RND(a,b) uniform_int_distribution<int>(a,b)(rnd); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m;cin>>n>>m; Matrix<mint> M(n,n); REP(_,m){ int u,v,w;cin>>u>>v>>w;u--;v--;w--; mint a=RND(1,1000000006); M[u][v]+=a;M[v][w]+=a;M[w][u]+=a; M[v][u]-=a;M[w][v]-=a;M[u][w]-=a; } cout<<(M.rank()>>1)<<endl; }