結果
問題 | No.1654 Binary Compression |
ユーザー |
![]() |
提出日時 | 2021-08-08 10:35:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,804 ms / 2,000 ms |
コード長 | 2,087 bytes |
コンパイル時間 | 3,453 ms |
コンパイル使用メモリ | 193,712 KB |
最終ジャッジ日時 | 2025-01-23 16:57:34 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;using mint=static_modint<924844033>;using S=pair<mint, int>;using F=pair<bool, mint>;S op(S a, S b){return S(a.first+b.first, a.second+b.second);}S e(){return S(0, 1);}S mapping(F f, S x){if(f.first) return S(x.first+f.second*x.second, x.second);else return S(f.second*x.second, x.second);}F composition(F f, F g){if(f.first) return make_pair(g.first, f.second+g.second);else return make_pair(0, f.second);}pair<bool, mint> id(){return make_pair(1, 0);}int main(){string s; cin>>s;int n=s.size();int l=0;while(l<n && s[l]=='0') l++;if(l==n){cout<<n<<endl;return 0;}int r=n-1;while(r>=0 && s[r]=='0') r--;mint c=mint(l+1)*mint(n-r);s=s.substr(l, r-l+1);n=s.size();int lmx=0;int i=0;while(s[i]=='1') i++;lmx=max(lmx, i);while(i<n){int c0=0, c1=0;while(s[i]=='0') i++, c0++;while(s[i]=='1') i++, c1++;lmx=max(lmx, c0);}lazy_segtree<S, op, e, F, mapping, composition, id> seg(lmx+1);i=0;while(s[i]=='1') i++;seg.apply(0, lmx+1, make_pair(1, i));mint v=1;while(i<n){int c0=0, c1=0;while(s[i]=='0') i++, c0++;while(s[i]=='1') i++, c1++;v+=seg.prod(0, c0).first;seg.apply(0, c0, make_pair(0, 0));seg.apply(0, lmx+1, make_pair(1, c1*v));}mint ans=c*seg.get(lmx).first;cout<<ans.val()<<endl;return 0;}