結果
問題 |
No.1654 Binary Compression
|
ユーザー |
![]() |
提出日時 | 2021-06-15 01:49:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 1,402 bytes |
コンパイル時間 | 2,547 ms |
コンパイル使用メモリ | 153,684 KB |
最終ジャッジ日時 | 2025-01-22 08:22:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <atcoder/all> using namespace std; using namespace atcoder; using mint=static_modint<924844033>; using P=pair<int, int>; mint dp[3000010], dps[3000010]; int main() { string s; cin>>s; int n=s.size(); bool allzero=1; for(int i=0; i<n; i++) if(s[i]=='1') allzero=0; if(allzero){ cout<<n<<endl; return 0; } dp[0]=1, dps[1]=1; vector<P> v{P(n+1, -1)}; int pr1=-1; for(int i=0; i<n; i++){ if(s[i]=='1'){ dp[i+1]+=dp[i]; if(pr1!=i-1) dp[i+1]+=dp[pr1+1]; pr1=i; }else if(s[i]=='0' && (i==n-1 || s[i+1]=='1')){ int c=i-pr1; int l=0, pr=i+1; while(v.back().first<=c){ dp[i+1]+=(dps[pr]-dps[v.back().second+1])*mint(c-l); l=v.back().first; pr=v.back().second; v.pop_back(); } if(pr1!=-1 && v.back().second==-1) dp[i+1]+=(dps[pr]-dps[1])*mint(c-l); else dp[i+1]+=(dps[pr]-dps[v.back().second+1])*mint(c-l); v.push_back(P(c, i+1)); } dps[i+2]=dps[i+1]+(s[i]=='1'?dp[i+1]:0); } mint ans=0; for(int i=0; i<n; i++){ if(s[i]=='1') ans+=dp[i+1]; } if(s[n-1]=='0'){ ans*=mint(v.back().first+1); } cout<<ans.val()<<endl; return 0; }