結果

問題 No.786 京都大学の過去問
コンテスト
ユーザー lightning
提出日時 2019-03-21 20:35:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,866 bytes
コンパイル時間 2,035 ms
コンパイル使用メモリ 177,360 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 02:00:28
合計ジャッジ時間 2,522 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define TDARRAY(int,a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) {if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a, T b) {if(a>b){a=b;return 1;}return 0;}

int n;

class Matrix{
public:
    vector<vector<ll>> m;
    int height,width;
    Matrix(int h,int w){//sizeを指定
        height = h;
        width = w;
        m.resize(h);
        REP(i,h){
            m[i].resize(w);
        }
    }
    Matrix operator*(Matrix b){
        int h=height;
        int w=b.width;
        int n=width;
        //if(n!=b.height){
        //}d
        Matrix c(h,w);
        REP(i,h){
            REP(j,w){
                ll v=0;
                REP(k,n){
                    v+=m[i][k]*b.m[k][j];
                }
                c.m[i][j]=v;
            }
        }
        return c;
    }
    Matrix operator+(Matrix b){//大きさが同じことが前提
        Matrix c(height,width);
        REP(i,height){
            REP(j,width){
                c.m[i][j]=m[i][j]+b.m[i][j];
            }
        }
        return c;
    }
    
};


Matrix pow_mat(Matrix a,int k){
    if(k==1){
        return a;
    }
    if(k%2==0){
        return pow_mat(a,k/2)*pow_mat(a,k/2);
    }else{
        return pow_mat(a,k-1)*a;
    }
}

int main(){
    cin >> n;
    Matrix a(2,2);
    a.m[0][0]=1;
    a.m[0][1]=1;
    a.m[1][0]=1;
    a.m[1][1]=0;
    
    Matrix res(2,2);
    res = pow_mat(a,n);
    put(res.m[0][0]);
    return 0;
}
0