結果
問題 |
No.3225 2×2行列相似判定 〜easy〜
|
ユーザー |
![]() |
提出日時 | 2025-08-08 21:44:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 845 ms / 2,000 ms |
コード長 | 10,954 bytes |
コンパイル時間 | 3,623 ms |
コンパイル使用メモリ | 278,416 KB |
実行使用メモリ | 7,712 KB |
最終ジャッジ日時 | 2025-08-08 21:44:38 |
合計ジャッジ時間 | 16,006 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast<void>(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template<typename T> inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } #ifdef LOCAL #include<debug.h> #define SWITCH(a,b) (a) #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) #define SWITCH(a,b) (b) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<<fixed<<setprecision(16); } inline double now(){return (double)(clock()-start)/1000;} #ifdef LOCAL ~Timer(){ cerr<<"time:"; cerr<<now(); cerr<<"ms\n"; } #endif }timer; void SOLVE(); int main(){ int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } } #include<concepts> template<typename T,int N,int M=N> struct ConstantMatrix{ private: std::array<std::array<T,M>,N>dat; public: ConstantMatrix(){ dat.fill([](){std::array<T,M>res;res.fill(T());return res;}()); } static ConstantMatrix E(){ static_assert(N==M); ConstantMatrix res; for(int i=0;i<N;i++)res[i][i]=T(1); return res; } inline ConstantMatrix &operator+=(const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)(*this)[i][j]+=rhs[i][j]; return *this; } inline ConstantMatrix &operator-=(const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)(*this)[i][j]-=rhs[i][j]; return *this; } inline ConstantMatrix &operator*=(const ConstantMatrix&rhs){ static_assert(N==M); ConstantMatrix res; for(int i=0;i<N;i++)for(int j=0;j<M;j++)for(int k=0;k<M;k++)res[i][k]+=(*this)[i][j]*rhs[j][k]; (*this)=std::move(res); return *this; } friend ConstantMatrix operator+(const ConstantMatrix&lhs,const ConstantMatrix&rhs){return ConstantMatrix(lhs)+=rhs;} friend ConstantMatrix operator-(const ConstantMatrix&lhs,const ConstantMatrix&rhs){return ConstantMatrix(lhs)-=rhs;} template<int K>friend ConstantMatrix<T,N,K> operator*(const ConstantMatrix&lhs,const ConstantMatrix<T,M,K>&rhs){ ConstantMatrix<T,N,K>res; for(int i=0;i<N;i++)for(int j=0;j<M;j++)for(int k=0;k<K;k++)res[i][k]+=lhs[i][j]*rhs[j][k]; return res; } std::array<T,M> &operator[](int i){return dat[i];} const std::array<T,M> &operator[](int i)const{return dat[i];} friend bool operator==(const ConstantMatrix&lhs,const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)if(lhs[i][j]!=rhs[i][j])return false; return true; } friend bool operator!=(const ConstantMatrix&lhs,const ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)if(lhs[i][j]!=rhs[i][j])return true; return false; } T det()const{ static_assert(N==M); T res=1; ConstantMatrix mat(*this); for(int i=0;i<M;i++){ int idx=-1; for(int j=i;j<N;j++)if(mat[j][i]!=T()){ idx=j; break; } if(idx==-1)return T(); if(i!=idx)std::swap(mat[i],mat[idx]),res=-res; res*=mat[i][i]; T inv_ii=mat[i][i].inv(); for(int j=i+1;j<M;j++)mat[i][j]*=inv_ii; for(int j=i+1;j<N;j++){ T coef=-mat[j][i]; for(int k=i+1;k<M;k++)mat[j][k]+=coef*mat[i][k]; } } return res; } ConstantMatrix inv()const{ static_assert(N==M); ConstantMatrix res=E(),mat=(*this); for(int i=0;i<N;i++){ int id=-1; for(int j=i;j<N;j++)if(mat[j][i]!=T()){ id=j; break; } if(id==-1)return ConstantMatrix(); if(i!=id){ std::swap(mat[i],mat[id]); std::swap(res[i],res[id]); } T inv=mat[i][i].inv(); for(int j=0;j<N;j++)if(i!=j){ T x=mat[j][i]; for(int k=0;k<N;k++){ mat[j][k]-=mat[i][k]*x; res[j][k]-=res[i][k]*x; } } } return res; } template<std::integral U> ConstantMatrix pow(U k)const{ static_assert(N==M); ConstantMatrix res=ConstantMatrix::E(),a(*this); while(k){ if(k&1)res*=a; a*=a; k>>=1; } return res; } std::vector<std::vector<T>>to_vector()const{ std::vector<std::vector<T>>res(N,std::vector<T>(M)); for(int i=0;i<N;i++)for(int j=0;j<M;j++)res[i][j]=dat[i][j]; return res; } friend std::istream &operator>>(std::istream&is,ConstantMatrix&rhs){ for(int i=0;i<N;i++)for(int j=0;j<M;j++)is>>rhs[i][j]; return is; } friend std::ostream &operator<<(std::ostream &os,const ConstantMatrix&rhs){ for(int i=0;i<N;i++){ for(int j=0;j<M;j++)os<<rhs[i][j]<<" \n"[j+1==M]; } return os; } }; #include<type_traits> #include<optional> constexpr int carmichael_constexpr(int n){ if(n==998244353)return 998244352; if(n==1000000007)return 1000000006; if(n<=1)return n; int res=1; int t=0; while(n%2==0){ n/=2; t++; } if(t==2)res=2; else if(t>=3)res=1<<(t-2); for(int i=3;i*i<=n;i++)if(n%i==0){ int c=0; while(n%i==0){ n/=i; c++; } int prod=i-1; for(int j=0;j<c-1;j++)prod*=i; res=std::lcm(res,prod); } if(n!=1)res=std::lcm(res,n-1); return res; } template<int m> struct mod_int{ private: static constexpr unsigned int umod=static_cast<unsigned int>(m); static constexpr unsigned int car=carmichael_constexpr(m); using uint=unsigned int; using mint=mod_int; uint v; static_assert(m<uint(1)<<31); mint sqrt_impl()const{ if(this->val()<=1)return *this; if constexpr(m%8==1){ mint b=2; while(b.pow((m-1)/2).val()==1)b++; int m2=m-1,e=0; while(m2%2==0)m2>>=1,e++; mint x=this->pow((m2-1)/2); mint y=(*this)*x*x; x*=*this; mint z=b.pow(m2); while(y.val()!=1){ int j=0; mint t=y; while(t.val()!=1)t*=t,j++; z=z.pow(1<<(e-j-1)); x*=z; z*=z; y*=z;e=j; } return x; } else if constexpr(m%8==5){ mint ret=this->pow((m+3)/8); if((ret*ret).val()==this->val())return ret; else return ret*mint::raw(2).pow((m-1)/4); } else{ return this->pow((m+1)/4); } } public: using value_type=uint; mod_int():v(0){} template<typename T,std::enable_if_t<std::is_signed_v<T>,std::nullptr_t> =nullptr> mod_int(T a){ a%=m; if(a<0)v=a+umod; else v=a; } template<typename T,std::enable_if_t<std::is_unsigned_v<T>,std::nullptr_t> =nullptr> mod_int(T a):v(a%umod){} static constexpr mint raw(int a){ mint ret; ret.v=a; return ret; } inline uint val()const{return this->v;} static constexpr int mod(){return m;} inline mint &operator+=(const mint &b){ this->v+=b.v; if(this->v>=umod)this->v-=umod; return *this; } inline mint &operator-=(const mint &b){ this->v-=b.v; if(this->v>=umod)this->v+=umod; return *this; } inline mint &operator*=(const mint &b){ this->v=((unsigned long long)this->v*b.v)%umod; return *this; } inline mint &operator/=(const mint &b){ *this*=b.inv(); return *this; } inline mint operator+()const{return *this;} inline mint operator-()const{return mint()-*this;} friend inline mint operator+(const mint &a,const mint &b){return mint(a)+=b;} friend inline mint operator-(const mint &a,const mint &b){return mint(a)-=b;} friend inline mint operator*(const mint &a,const mint &b){return mint(a)*=b;} friend inline mint operator/(const mint &a,const mint &b){return mint(a)/=b;} friend inline bool operator==(const mint &a,const mint &b){return a.val()==b.val();} friend inline bool operator!=(const mint &a,const mint &b){return !(a==b);} inline mint operator++(int){ mint ret=*this; *this+=mint::raw(1); return ret; } inline mint operator--(int){ mint ret=*this; *this-=mint::raw(1); return ret; } mint pow(long long n)const{ mint ret=mint::raw(1),a(*this); while(n){ if(n&1)ret*=a; a*=a; n>>=1; } return ret; } inline mint inv()const{ assert(this->v!=0); return pow(car-1); } std::optional<mint>sqrt()const{ if(this->val()<=1||this->pow((m-1)/2)==1)return std::make_optional(this->sqrt_impl()); else return std::nullopt; } static constexpr unsigned int order(){return car;} friend std::istream &operator>>(std::istream &is,mint &b){ long long a; is>>a; b=mint(a); return is; } friend std::ostream &operator<<(std::ostream &os,const mint &b){ os<<b.val(); return os; } }; template<int m> struct std::hash<mod_int<m>>{ std::size_t operator()(mod_int<m>x)const{ return std::hash<unsigned int>()(x.val()); } }; using mint998=mod_int<998244353>; using mint107=mod_int<1000000007>; using mint=mod_int<67>; void SOLVE(){ ConstantMatrix<mint,2>M,M2; cin>>M>>M2; rep(i,mint::mod()) rep(j,mint::mod()) rep(k,mint::mod()) rep(l,mint::mod())if((i*l-j*k)%mint::mod()!=0){ ConstantMatrix<mint,2> mat; mat[0][0]=mint::raw(i); mat[0][1]=mint::raw(j); mat[1][0]=mint::raw(k); mat[1][1]=mint::raw(l); if(mat*M==M2*mat)fin("Yes"); } cout<<"No"<<endl; }