結果
問題 | No.619 CardShuffle |
ユーザー |
![]() |
提出日時 | 2018-06-11 18:44:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,447 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 175,708 KB |
実行使用メモリ | 94,152 KB |
最終ジャッジ日時 | 2024-06-30 13:40:05 |
合計ジャッジ時間 | 8,063 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 TLE * 5 -- * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcount #define INF 1e16 #define mod 1000000007 typedef vector<ll> vec; typedef vector<vec> mat; mat operator*(const mat& a,const mat& b){ mat res(4,vec(4,0)); rep(k,4){ rep(i,4){ rep(j,4){ (res[i][j]+=a[i][k]*b[k][j])%=mod; } } } return res; } vector<mat> dat; int sz; mat e; void init(int n_){ sz=1; while(sz<n_) sz*=2; for(int i=0;i<2*sz-1;i++){ dat.push_back(mat(4,vec(4,0))); rep(j,4)dat[i][j][j]=1; } e=mat(4,vec(4,0)); rep(i,4)e[i][i]=1; } void update(int k,mat a){ k+=sz-1; dat[k]=a; while(k>0){ k=(k-1)/2; dat[k]=dat[k*2+2]*dat[k*2+1]; } } mat query(int a,int b,int k=0,int l=0,int r=sz){ if(r<=a||b<=l)return e; if(a<=l&&r<=b)return dat[k]; else{ return query(a,b,k*2+2,(l+r)/2,r)*query(a,b,k*2+1,l,(l+r)/2); } } int n,q; vector<char> cs; ll pls[4][4]={ {1, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 1}, }; ll mul[4][4]={ {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}, }; ll num[4][4]={ {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 10, 0}, {0, 0, 0, 1}, }; int main(){ cin>>n; rep(i,n){ char c; cin>>c; cs.push_back(c); } init(n); rep(i,n){ mat m(4,vec(4,0)); if(isdigit(cs[i])){ rep(j,4)rep(k,4)m[j][k]=num[j][k]; m[2][1]=cs[i]-'0'; }else if(cs[i]=='+'){ rep(j,4)rep(k,4)m[j][k]=pls[j][k]; }else if(cs[i]=='*'){ rep(j,4)rep(k,4)m[j][k]=mul[j][k]; } update(i,m); } mat mpls(4,vec(4,0)); rep(i,4)rep(j,4)mpls[i][j]=pls[i][j]; cin>>q; while(q--){ char typ; cin>>typ; if(typ=='?'){ int l,r; cin>>l>>r; l--; mat m=query(l,r); m=mpls*m; cout<<(m[0][1]+m[0][3])%mod<<endl; }else{ int i,j; cin>>i>>j; i--;j--; mat m1=query(i,i+1); mat m2=query(j,j+1); update(i,m2); update(j,m1); } } return 0; }