結果
問題 |
No.3226 2×2行列累乗
|
ユーザー |
![]() |
提出日時 | 2025-08-08 22:11:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,178 bytes |
コンパイル時間 | 3,491 ms |
コンパイル使用メモリ | 291,496 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-08 22:11:18 |
合計ジャッジ時間 | 4,043 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/modint> using namespace std; using T=atcoder::modint; struct matrix{ int h,w; vector<vector<T>> val; matrix(int r,int c=-1):h(r),w(c){ if (w==-1) w=h; val.assign(h,vector<T>(w,0)); } matrix operator*(matrix b){ matrix a=*this,c(h,w); for (int i=0;i<h;i++){ for (int j=0;j<w;j++){ for (int k=0;k<b.h;k++){ c.val[i][j]+=a.val[i][k]*b.val[k][j]; } } } return c; } matrix identity(int n){ matrix ret(n,n); for (int i=0;i<n;i++) ret.val[i][i]=1; return ret; } matrix pow(long long k){ matrix ret(h,w),m=*this; ret=ret.identity(h); while (k>0){ if (k%2==1) ret=ret*m; m=m*m; k/=2; } return ret; } }; int main(){ int n=2; vector<vector<int>> tmp(n,vector<int>(2)); matrix m(n); for (int i=0;i<n;i++) for (int j=0;j<n;j++) cin>>tmp[i][j]; int s,t; cin>>s>>t; long long N,K; cin>>N>>K; T::set_mod(K); for (int i=0;i<n;i++) for (int j=0;j<n;j++) m.val[i][j]=tmp[i][j]; matrix ans=m.pow(N); for (int i=0;i<n;i++){ cout<<(ans.val[i][0]*s+ans.val[i][1]*t).val()<<" \n"[i==n-1]; } }