#920769 (C++17(clang)) No.1907 DETERMINATION

提出ソース

結果

問題	No.1907 DETERMINATION
ユーザー	Taiki0715
提出日時	2023-10-20 14:59:52
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	614 ms / 4,000 ms
コード長	5,973 bytes
コンパイル時間	11,441 ms
コンパイル使用メモリ	179,228 KB
実行使用メモリ	6,976 KB
最終ジャッジ日時	2023-10-20 15:00:31
合計ジャッジ時間	35,370 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	172 ms 5,448 KB
testcase_08	AC	69 ms 4,588 KB
testcase_09	AC	118 ms 5,048 KB
testcase_10	AC	451 ms 6,868 KB
testcase_11	AC	302 ms 5,468 KB
testcase_12	AC	407 ms 6,920 KB
testcase_13	AC	386 ms 6,788 KB
testcase_14	AC	353 ms 6,920 KB
testcase_15	AC	77 ms 4,868 KB
testcase_16	AC	27 ms 4,348 KB
testcase_17	AC	425 ms 6,804 KB
testcase_18	AC	276 ms 6,016 KB
testcase_19	AC	8 ms 4,348 KB
testcase_20	AC	393 ms 6,860 KB
testcase_21	AC	36 ms 4,348 KB
testcase_22	AC	417 ms 5,468 KB
testcase_23	AC	473 ms 6,852 KB
testcase_24	AC	126 ms 5,016 KB
testcase_25	AC	2 ms 4,348 KB
testcase_26	AC	416 ms 6,976 KB
testcase_27	AC	510 ms 6,976 KB
testcase_28	AC	512 ms 6,976 KB
testcase_29	AC	509 ms 6,976 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	425 ms 6,976 KB
testcase_32	AC	412 ms 6,968 KB
testcase_33	AC	415 ms 6,976 KB
testcase_34	AC	417 ms 6,976 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	414 ms 6,976 KB
testcase_39	AC	414 ms 6,976 KB
testcase_40	AC	614 ms 6,976 KB
testcase_41	AC	415 ms 6,976 KB
testcase_42	AC	613 ms 6,976 KB
testcase_43	AC	614 ms 6,976 KB
testcase_44	AC	474 ms 6,976 KB
testcase_45	AC	510 ms 6,976 KB
testcase_46	AC	411 ms 6,928 KB
testcase_47	AC	413 ms 6,968 KB
testcase_48	AC	415 ms 6,976 KB
testcase_49	AC	447 ms 6,976 KB
testcase_50	AC	413 ms 6,976 KB
testcase_51	AC	414 ms 6,976 KB
testcase_52	AC	2 ms 4,348 KB
testcase_53	AC	444 ms 5,732 KB
testcase_54	AC	447 ms 5,732 KB
testcase_55	AC	2 ms 4,348 KB
testcase_56	AC	444 ms 5,732 KB
testcase_57	AC	445 ms 5,732 KB
testcase_58	AC	452 ms 6,928 KB
testcase_59	AC	265 ms 6,968 KB
testcase_60	AC	269 ms 6,976 KB
testcase_61	AC	342 ms 6,976 KB
testcase_62	AC	267 ms 6,976 KB
testcase_63	AC	416 ms 6,976 KB
testcase_64	AC	2 ms 4,348 KB
testcase_65	AC	2 ms 4,348 KB
testcase_66	AC	1 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}
istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}
#endif
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 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 reps(i,a,n) for(int i=(a);i<(n);i++)
#define rep(i,n) reps(i,0,n)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcount(x)
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"
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
void SOLVE();
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef LOCAL
  clock_t start=clock();
  #endif
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
  #ifdef LOCAL
  cerr<<"time:";
  cerr<<(clock()-start)/1000;
  cerr<<"ms\n";
  #endif
}
template<typename T>
vector<vector<T>>matrix_mul(const vector<vector<T>>&a,const vector<vector<T>>&b){
  assert(a[0].size()==b.size());
  vector<vector<T>>ret(a.size(),vector<T>(b[0].size(),0));
  rep(i,a.size())rep(j,b.size())rep(k,b[0].size())ret[i][k]+=a[i][j]*b[j][k];
  return ret;
}
template<typename T>
vector<vector<T>>matrix_pow(vector<vector<T>>a,ll k){
  assert(a.size()==a[0].size());
  vector<vector<T>>ret(a.size(),vector<T>(a.size(),0));
  rep(i,a.size())ret[i][i]=1;
  while(k){
    if(k&1)ret=matrix_mul(ret,a);
    a=matrix_mul(a,a);
    k>>=1;
  }
  return ret;
}
template<typename T>
T matrix_det(vector<vector<T>>a){
  assert(a.size()==a[0].size());
  int n=a.size();
  T ret=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)return 0;
    if(i!=id){
      ret*=-1;
      swap(a[i],a[id]);
    }
    ret*=a[i][i];
    T inv=a[i][i].inv();
    rep(j,n)a[i][j]*=inv;
    reps(j,i+1,n){
      T x=a[j][i];
      rep(k,n)a[j][k]-=a[i][k]*x;
    }
  }
  return ret;
}
template<typename T>
vector<vector<T>>matrix_inv(vector<vector<T>>a){
  assert(a.size()==a[0].size());
  int n=a.size();
  vector<vector<T>>ret(n,vector<T>(n,0));
  rep(i,n)ret[i][i]=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)return vector<vector<T>>(n,vector<T>(n,0));
    if(i!=id){
      swap(a[i],a[id]);
      swap(ret[i],ret[id]);
    }
    T inv=a[i][i].inv();
    rep(j,n){
      a[i][j]*=inv;
      ret[i][j]*=inv;
    }
    rep(j,n)if(i!=j){
      T x=a[j][i];
      rep(k,n){
        a[j][k]-=a[i][k]*x;
        ret[j][k]-=ret[i][k]*x;
      }
    }
  }
  return ret;
}
template<typename T>
void matrix_hessenberg(vector<vector<T>>&a){
  assert(a.size()==a[0].size());
  int n=a.size();
  rep(i,n-2){
    int id=-1;
    reps(j,i+1,n){
      if(a[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1)continue;
    swap(a[i+1],a[id]);
    rep(j,n)swap(a[j][i+1],a[j][id]);
    T inv=a[i+1][i].inv();
    reps(j,i+2,n){
      T x=a[j][i]*inv;
      rep(k,n)a[j][k]-=a[i+1][k]*x;
      rep(k,n)a[k][i+1]+=a[k][j]*x;
    }
  }
}
//det(xI-a)
template<typename T>
vector<T>matrix_charpoly(vector<vector<T>>a){
  matrix_hessenberg(a);
  int n=a.size();
  vector<vector<T>>ret(n+1);
  ret[0]={1};
  rep(i,n){
    ret[i+1].resize(i+2,0);
    rep(j,i+1)ret[i+1][j+1]+=ret[i][j];
    rep(j,i+1)ret[i+1][j]-=ret[i][j]*a[i][i];
    T b=1;
    for(int j=i-1;j>=0;j--){
      b*=a[j+1][j];
      T c=-a[j][i]*b;
      rep(k,j+1)ret[i+1][k]+=c*ret[j][k];
    }
  }
  return ret[n];
}
//det(a+xb)
template<typename T>
vector<T>matrix_detpoly(vector<vector<T>>a,vector<vector<T>>b){
  assert(a.size()==a[0].size());
  assert(b.size()==b[0].size());
  assert(a.size()==b.size());
  int n=a.size();
  int cx=0;
  T ab=1;
  rep(i,n){
    int id=-1;
    reps(j,i,n){
      if(b[j][i]!=0){
        id=j;
        break;
      }
    }
    if(id==-1){
      if(++cx>n)return vector<T>(n+1,0);
      rep(j,n){
        T v=b[j][i];
        b[j][i]=0;
        rep(k,n)a[k][i]-=v*a[k][j];
      }
      rep(j,n)swap(a[j][i],b[j][i]);
      i--;
      continue;
    }
    if(i!=id){
      swap(a[i],a[id]);
      swap(b[i],b[id]);
      ab*=-1;
    }
    ab*=b[i][i];
    T inv=b[i][i].inv();
    rep(j,n){
      a[i][j]*=inv;
      b[i][j]*=inv;
    }
    rep(j,n)if(i!=j){
      T v=b[j][i];
      rep(k,n){
        a[j][k]-=a[i][k]*v;
        b[j][k]-=b[i][k]*v;
      }
    }
  }
  rep(i,n)rep(j,n)a[i][j]*=-1;
  vector<T> poly=matrix_charpoly(a);
  rep(i,n+1)poly[i]*=ab;
  poly.erase(poly.begin(),poly.begin()+cx);
  poly.resize(n+1,0);
  return poly;
}
using mint=modint998244353;
void SOLVE(){
  int n;
  cin>>n;
  auto a=vec<mint>({n,n}),b=vec<mint>({n,n});
  cin>>a>>b;
  vector<mint>c=matrix_detpoly(a,b);
  rep(i,n+1)cout<<c[i].val()<<endl;
}

yukicoder

結果

テストケース

ソースコード