結果
問題 | No.2441 行列累乗 |
ユーザー |
|
提出日時 | 2023-08-25 21:25:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 850 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 174,776 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 07:48:21 |
合計ジャッジ時間 | 2,507 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; vector<vector<ll>> mul(vector<vector<ll>> v1,vector<vector<ll>> v2){ ll s=v1.size(); vector<vector<ll>> res(s,vector<ll>(s,0)); for(ll i=0;i<s;i++){ for(ll j=0;j<s;j++){ for(ll k=0;k<s;k++){ res[i][j]+=v1[i][k]*v2[k][j]; } } } return res; } vector<vector<ll>> modpow(vector<vector<ll>> v,ll n){ ll s=v.size(); vector<vector<ll>> res(s,vector<ll>(s,0)); for(ll i=0;i<s;i++){ res[i][i]=1; } while(n>0){ if(n&1){ res=mul(res,v); } v=mul(v,v); n>>=1; } return res; } int main(){ ll m11,m12; cin>>m11>>m12; ll m21,m22; cin>>m21>>m22; vector<vector<ll>> v={{m11,m12},{m21,m22}}; vector<vector<ll>> ans=modpow(v,3); cout<<ans[0][0]<<" "<<ans[0][1]<<endl; cout<<ans[1][0]<<" "<<ans[1][1]<<endl; }