結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-08 22:19:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,917 ms / 8,000 ms |
コード長 | 1,464 bytes |
コンパイル時間 | 6,183 ms |
コンパイル使用メモリ | 335,696 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2025-08-08 22:20:09 |
合計ジャッジ時間 | 36,060 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> 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 n=2; matrix op(matrix a,matrix b){return a*b;} matrix e(){return matrix(n).identity(n);} int main(){ long long N,K; cin>>K>>N; T::set_mod(K); vector<matrix> x(N,matrix(n)); for (int i=0;i<N;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++){ int val; cin>>val; x[i].val[j][k]=val; } atcoder::segtree<matrix,op,e> seg(x); int q; cin>>q; while (q--){ int i,l,r; cin>>i>>l>>r; i--;l--; matrix y(n); for (int i=0;i<n;i++) for (int j=0;j<n;j++){ int val; cin>>val; y.val[i][j]=val; } seg.set(i,y); auto p=seg.prod(l,r); for (int i=0;i<n;i++) for (int j=0;j<n;j++) cout<<p.val[i][j].val()<<" \n"[j==n-1]; } }