#300816 (C++17) No.572 妖精の演奏

• 問題: No.572 妖精の演奏
• ユーザー: beet
• 提出日時: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX