結果
問題 | No.2441 行列累乗 |
ユーザー |
![]() |
提出日時 | 2023-08-25 22:18:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,199 bytes |
コンパイル時間 | 3,527 ms |
コンパイル使用メモリ | 251,824 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 09:21:05 |
合計ジャッジ時間 | 4,385 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; template< typename T > vector<vector<T>> mattimes(vector<vector<T>> &A,vector<vector<T>> &B){ assert(A.size()==B.size()); int n = A.size(); vector<vector<T>> res(n,vector<T>(n,0)); for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)res[i][j]+=A[i][k]*B[k][j]; return res; } template< typename T > vector<T> mattimes(vector<vector<T>> &A,vector<T> &B){ assert(A.size()==B.size()); int n = A.size(); vector<T> res(n,0); for(int i=0;i<n;i++)for(int j=0;j<n;j++)res[i]+=A[i][j]*B[j]; return res; } template< typename T > vector<vector<T>> matpow(vector<vector<T>> a,ll k){ int n = a.size(); vector<vector<T>> res(n,vector<T>(n,0)); for(int i=0;i<n;i++)res[i][i] = T(1); for(;k;k>>=1){ if(k&1) res = mattimes<T>(res,a); a = mattimes<T>(a,a); } return res; } int main(){ vector<vector<ll>> m(2,vector<ll>(2,0)); cin>>m[0][0]>>m[0][1]>>m[1][0]>>m[1][1]; m = matpow<ll>(m,3); for(int i = 0;i<2;i++){ for(int j = 0;j<2;j++){ if(j) cout<<" "; cout<<m[i][j]; } cout<<endl; } }