結果

問題 No.572 妖精の演奏
ユーザー beetbeet
提出日時 2018-12-02 11:03:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,878 bytes
コンパイル時間 1,976 ms
コンパイル使用メモリ 201,268 KB
最終ジャッジ日時 2025-01-06 17:54:42
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename K>
struct Matrix{
  typedef vector<K> arr;
  typedef vector<arr> mat;
  mat dat;

  Matrix(size_t r,size_t c):dat(r,arr(c,K())){}
  Matrix(mat dat):dat(dat){}

  size_t size() const{return dat.size();};
  bool empty() const{return size()==0;};
  arr& operator[](size_t k){return dat[k];};
  const arr& operator[](size_t k) const {return dat[k];};
  
  static Matrix cross(const Matrix &A,const Matrix &B){
    Matrix res(A.size(),B[0].size());    
    for(Int i=0;i<(Int)A.size();i++)
      for(Int j=0;j<(Int)B[0].size();j++)
        for(Int k=0;k<(Int)B.size();k++)
          res[i][j]+=A[i][k]*B[k][j];
    return res;
  }

  static Matrix identity(size_t n){
    Matrix res(n,n);
    for(Int i=0;i<(Int)n;i++) res[i][i]=K(1);
    return res;
  }
  
  Matrix pow(long long n) const{
    Matrix a(dat),res=identity(size());
    while(n){
      if(n&1) res=cross(res,a);
      a=cross(a,a);      
      n>>=1;
    }
    return res;
  }
};

const Int INF = 1e15;
struct R{
  Int v;
  R():v(-INF){}
  R(Int x){if(x==1) v=0;}
  R operator+=(const R &a){
    v=max(v,a.v);
    return *this;
  }
  R operator*=(const R &a){
    v=v+a.v;
    return *this;
  }
  R operator+(const R &a) const{
    R b(*this);
    return b+=a;
  }
  R operator*(const R &a) const{
    R b(*this);
    return b*=a;
  }
};

//INSERT ABOVE HERE
signed main(){
  using M = Matrix<R>;
  Int n,m;
  cin>>n>>m;
  M A(m,m);
  for(Int i=0;i<m;i++)
    for(Int j=0;j<m;j++)
      cin>>A[i][j].v;
  M B(m,1);
  for(Int i=0;i<m;i++) B[i][0].v=0;

  M C=M::cross(A.pow(n-1),B);

  Int res=0;
  for(Int i=0;i<m;i++) chmax(res,C[i][0].v);
  cout<<res<<endl;
  return 0;
}
0