結果
問題 |
No.3227 Matrix Query
|
ユーザー |
|
提出日時 | 2025-09-26 14:22:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 573 ms / 8,000 ms |
コード長 | 1,019 bytes |
コンパイル時間 | 6,573 ms |
コンパイル使用メモリ | 334,988 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-26 14:22:32 |
合計ジャッジ時間 | 21,134 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define all(x) (x).begin(), (x).end() using ll = long long; const ll MOD = 998244353; #include<atcoder/all> using namespace atcoder; using mint = modint998244353; ll k,n; struct G{ ll a,b,c,d; }; G f(G X,G Y){ G Z; Z.a=(X.a*Y.a+X.b*Y.c)%k; Z.b=(X.a*Y.b+X.b*Y.d)%k; Z.c=(X.c*Y.a+X.d*Y.c)%k; Z.d=(X.c*Y.b+X.d*Y.d)%k; if(Z.a<0)Z.a+=k; if(Z.b<0)Z.b+=k; if(Z.c<0)Z.c+=k; if(Z.d<0)Z.d+=k; return Z; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>k>>n; vector<G> g(n); rep(i,n)cin>>g[i].a>>g[i].b>>g[i].c>>g[i].d; auto e=[](){ G Z; Z.a=1;Z.b=0;Z.c=0;Z.d=1; return Z; }; segtree<G,f,e> seg(g); ll q;cin>>q; while(q--){ ll I,l,r;cin>>I>>l>>r; I--;l--;r--; G Y; cin>>Y.a>>Y.b>>Y.c>>Y.d; seg.set(I,Y); G ans=seg.prod(l,r+1); cout<<ans.a<<" "<<ans.b<<endl; cout<<ans.c<<" "<<ans.d<<endl; } }