結果
問題 | No.2498 OX Operations |
ユーザー |
|
提出日時 | 2023-10-06 23:37:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,141 ms / 4,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 950 ms |
コンパイル使用メモリ | 86,316 KB |
実行使用メモリ | 51,556 KB |
最終ジャッジ日時 | 2024-07-26 17:18:20 |
合計ジャッジ時間 | 21,407 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include<iostream> #include<cassert> #include<atcoder/modint> #include<atcoder/lazysegtree> using namespace std; using mint=atcoder::modint998244353; using dat=pair<bool,bool>; dat op(dat a,dat b){return a;} dat e(){return make_pair(false,false);} dat mp(int f,dat x) { if(f==0); else if(f==1)x.first=!x.first,x.second=!x.second; else if(f==2)x=make_pair(false,false); else x=make_pair(true,true); return x; } int cmp(int f,int g) { static const int tb[4][4]={ {0,1,2,3}, {1,0,3,2}, {2,2,2,2}, {3,3,3,3}, }; return tb[f][g]; } int id(){return 0;} int N,Q; int M[1<<17]; int F[1<<17],T[1<<17]; mint dp[1<<17][31]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>Q; for(int i=0;i<N;i++)cin>>M[i]; vector<dat>init(N,make_pair(false,true)); atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>seg[30]; for(int k=0;k<30;k++) { seg[k]=atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>(init); } for(int i=0;i<Q;i++) { char C; int L,R,X; cin>>C>>L>>R>>X; L--; if(C=='o') { for(int k=0;k<30;k++)if(X>>k&1) { seg[k].apply(L,R,3); } } else { for(int k=0;k<30;k++)if(X>>k&1) { seg[k].apply(L,R,1); } } } for(int k=0;k<30;k++) { for(int i=0;i<N;i++) { dat t=seg[k].get(i); if(t.first)F[i]|=1<<k; if(t.second)T[i]|=1<<k; } } dp[0][0]=1; for(int i=0;i<N;i++) { mint way[2][2][31]; int now=0; for(int a=0;a<2;a++)for(int b=0;b<=30;b++)way[now][a][b]=0; way[now][0][0]=1; for(int k=30;k--;) { int nxt=1-now; for(int a=0;a<2;a++)for(int b=0;b<=30;b++)way[nxt][a][b]=0; for(int j=0;j<2;j++) { int up=j?1:M[i]>>k&1; for(int b=0;b<=up;b++) { int p=(b?T[i]:F[i])>>k&1; for(int l=0;l<30;l++) { way[nxt][j|b<up][l+p]+=way[now][j][l]; } } } now=nxt; } for(int a=0;a<=30;a++)for(int b=0;b<=30;b++) { dp[i+1][max(a,b)]+=dp[i][a]*(way[now][0][b]+way[now][1][b]); } } mint ans=0; for(int k=0;k<=30;k++)ans+=mint::raw(k)*dp[N][k]; cout<<ans.val()<<endl; }