結果
問題 | No.2279 OR Insertion |
ユーザー | kotatsugame |
提出日時 | 2023-04-21 21:56:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,398 ms / 2,000 ms |
コード長 | 1,245 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 79,376 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-24 08:05:24 |
合計ジャッジ時間 | 34,745 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 150 ms
5,376 KB |
testcase_03 | AC | 64 ms
5,376 KB |
testcase_04 | AC | 1,240 ms
5,376 KB |
testcase_05 | AC | 15 ms
5,376 KB |
testcase_06 | AC | 493 ms
5,376 KB |
testcase_07 | AC | 545 ms
5,376 KB |
testcase_08 | AC | 165 ms
5,376 KB |
testcase_09 | AC | 728 ms
5,376 KB |
testcase_10 | AC | 1,256 ms
5,376 KB |
testcase_11 | AC | 124 ms
5,376 KB |
testcase_12 | AC | 968 ms
5,376 KB |
testcase_13 | AC | 47 ms
5,376 KB |
testcase_14 | AC | 61 ms
5,376 KB |
testcase_15 | AC | 596 ms
5,376 KB |
testcase_16 | AC | 9 ms
5,376 KB |
testcase_17 | AC | 460 ms
5,376 KB |
testcase_18 | AC | 841 ms
5,376 KB |
testcase_19 | AC | 1,146 ms
5,376 KB |
testcase_20 | AC | 559 ms
5,376 KB |
testcase_21 | AC | 399 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 1,303 ms
5,376 KB |
testcase_33 | AC | 1,302 ms
5,376 KB |
testcase_34 | AC | 1,317 ms
5,376 KB |
testcase_35 | AC | 1,300 ms
5,376 KB |
testcase_36 | AC | 1,307 ms
5,376 KB |
testcase_37 | AC | 1,296 ms
5,376 KB |
testcase_38 | AC | 1,295 ms
5,376 KB |
testcase_39 | AC | 1,287 ms
5,376 KB |
testcase_40 | AC | 1,284 ms
5,376 KB |
testcase_41 | AC | 1,301 ms
5,376 KB |
testcase_42 | AC | 1,354 ms
5,376 KB |
testcase_43 | AC | 1,387 ms
5,376 KB |
testcase_44 | AC | 1,376 ms
5,376 KB |
testcase_45 | AC | 1,092 ms
5,376 KB |
testcase_46 | AC | 1,089 ms
5,376 KB |
testcase_47 | AC | 1,114 ms
5,376 KB |
testcase_48 | AC | 1,398 ms
5,376 KB |
testcase_49 | AC | 1,135 ms
5,376 KB |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; struct dualsegtree{ int n; vector<mint>dat,lazy; dualsegtree(int n_=0) { n=1; while(n<n_)n<<=1; dat.assign(n,mint::raw(0)); lazy.assign(n-1,mint::raw(0)); } void update(int a,int b,mint x,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; if(b<=l||r<=a)return; else if(a<=l&&r<=b) { if(k<n-1)lazy[k]+=x; else dat[k-n+1]+=x; } else { update(a,b,x,k*2+1,l,(l+r)/2); update(a,b,x,k*2+2,(l+r)/2,r); } } mint query(int i) { mint ret=dat[i]; i+=n-1; while(i>0) { i=(i-1)/2; ret+=lazy[i]; } return ret; } }; int N; string S; mint p2[4040]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>S; p2[0]=mint::raw(1); for(int i=1;i<=N;i++)p2[i]=p2[i-1]+p2[i-1]; reverse(S.begin(),S.end()); mint ans=0; for(int k=0;k<N;k++) { dualsegtree seg(N); seg.update(0,1,mint::raw(1)); mint add=0; for(int i=0;i+k<N;i++) { mint now=seg.query(i); if(S[i+k]=='1') { seg.update(i+1,i+k+1,now); add+=now*p2[N-i-k-1]; } else { seg.update(i+1,N,now); } } ans+=add*p2[k]; } cout<<ans.val()<<endl; }