結果
問題 | No.2611 Count 01 |
ユーザー | 沙耶花 |
提出日時 | 2024-01-19 22:17:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,190 ms / 6,000 ms |
コード長 | 2,025 bytes |
コンパイル時間 | 4,987 ms |
コンパイル使用メモリ | 269,244 KB |
実行使用メモリ | 56,444 KB |
最終ジャッジ日時 | 2024-01-19 22:18:09 |
合計ジャッジ時間 | 49,692 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 2,164 ms
56,444 KB |
testcase_04 | AC | 2,174 ms
56,444 KB |
testcase_05 | AC | 2,133 ms
56,444 KB |
testcase_06 | AC | 2,190 ms
56,444 KB |
testcase_07 | AC | 2,143 ms
56,444 KB |
testcase_08 | AC | 2,145 ms
56,444 KB |
testcase_09 | AC | 2,138 ms
56,444 KB |
testcase_10 | AC | 2,156 ms
56,444 KB |
testcase_11 | AC | 2,141 ms
56,444 KB |
testcase_12 | AC | 2,139 ms
56,444 KB |
testcase_13 | AC | 2,148 ms
56,444 KB |
testcase_14 | AC | 2,149 ms
56,444 KB |
testcase_15 | AC | 2,138 ms
56,444 KB |
testcase_16 | AC | 2,143 ms
56,444 KB |
testcase_17 | AC | 2,149 ms
56,444 KB |
testcase_18 | AC | 2,164 ms
56,444 KB |
testcase_19 | AC | 2,137 ms
56,444 KB |
testcase_20 | AC | 2,132 ms
56,444 KB |
testcase_21 | AC | 2,132 ms
56,444 KB |
testcase_22 | AC | 2,134 ms
56,444 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 using A = array<array<mint,4>,5>; A e(){ A ret; rep(i,5){ rep(j,4){ ret[i][j] = 0; } } return ret; } A op(A a,A b){ if(a==e())return b; if(b==e())return a; A ret = e(); rep(i,4){ rep(j,4){ if(j&i)continue; int k = (i|j); rep(l,5){ rep(m,5){ //cout<<k<<endl; int n = 0; if(l==0){ if(m==0)n = 0; if(m==1)n = 4; if(m==2)n = 2; if(m==3)n = 2; if(m==4)n = 4; } if(l==1){ if(m==0)n = 1; if(m==1)continue; if(m==2)continue; if(m==3)continue; if(m==4)continue; } if(l==2){ if(m==0)n = 4; if(m==1)n = 4; if(m==2)continue; if(m==3)n = 2; if(m==4)continue; } if(l==3){ if(m==0)n = 1; if(m==1)n = 1; if(m==2)continue; if(m==3)n = 3; if(m==4)continue; } if(l==4){ if(m==0)n = 4; else continue; } ret[n][k] += a[l][i] * b[m][j]; } } } } return ret; } int main(){ int n,q; cin>>n>>q; vector<A> t(n); string s; cin>>s; rep(i,n){ A temp = e(); temp[0][0] = 1; temp[3][1<<(s[i]-'0')] ++; temp[3][0] ++; t[i] = temp; } /*auto ret = op(t[0],t[1]); rep(i,5){ rep(j,4){ cout<<ret[i][j].val()<<' '; } cout<<endl; } return 0; */ segtree<A,op,e> seg(t); rep(_,q){ int x; cin>>x; if(x==1){ int ii; cin>>ii; ii--; s[ii] ^= 1; A temp = e(); temp[0][0] = 1; temp[3][1<<(s[ii]-'0')] ++; temp[3][0] ++; seg.set(ii,temp); } else{ int l,r; cin>>l>>r; l--; auto ret = seg.prod(l,r); mint ans = 0; rep(i,5)ans += ret[i][3]; /*rep(i,5){ rep(j,4){ cout<<ret[i][j].val()<<' '; } cout<<endl; }*/ cout<<ans.val()<<endl; } } return 0; }