結果

問題 No.1654 Binary Compression
ユーザー chocorusk
提出日時 2021-06-16 21:35:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,315 bytes
コンパイル時間 3,055 ms
コンパイル使用メモリ 157,624 KB
最終ジャッジ日時 2025-01-22 08:32:43
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 12 WA * 36 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint=modint998244353;
using P=pair<int, int>;
mint dp[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;
    }
    int pr1=-1;
    vector<int> w;
    for(int i=0; i<n; i++){
        if(s[i]=='1'){
            pr1=i;
        }else if(s[i]=='0' && (i==n-1 || s[i+1]=='1')){
            int c=i-pr1;
            w.push_back(c);
        }
    }
    sort(w.begin(), w.end());
    w.erase(unique(w.begin(), w.end()), w.end());
    int m=w.size();
    vector<vector<int>> wp(m);
    pr1=-1;
    for(int i=0; i<n; i++){
        if(s[i]=='1'){
            pr1=i;
        }else if(s[i]=='0' && (i==n-1 || s[i+1]=='1')){
            int c=i-pr1;
            wp[lower_bound(w.begin(), w.end(), c)-w.begin()].push_back(i);
        }
    }
    for(int i=0; i<m; i++) reverse(wp[i].begin(), wp[i].end());

    if(s[0]=='1'){
        dp[0]=1;
    }else{
        int t=0;
        while(s[t]=='0') t++;
        dp[t]=1, dp[t-1]=t;
    }
    pr1=-1;
    for(int i=0; i<n-1; i++){
        if(s[i]=='1'){
            if(s[i+1]=='1'){
                dp[i+1]+=dp[i];
            }else{
                int nx=i+1;
                while(nx<n && s[nx]=='0') nx++;
                if(nx<n) dp[nx]+=dp[i];
            }
            int l=0, pri=n+1, prj=m;
            for(int j=m-1; j>=0; j--){
                if(wp[j].empty()) continue;
                if(wp[j].back()<pri){
                    if(prj<m) dp[pri]+=mint(w[prj]-w[j])*dp[i];
                    pri=wp[j].back();
                    prj=j;
                }
            }
            if(prj<m) dp[pri]+=mint(w[prj])*dp[i];
            pr1=i;
        }else if(s[i]=='0' && s[i+1]=='1'){
            dp[i+1]+=dp[i];
            int c=i-pr1;
            wp[lower_bound(w.begin(), w.end(), c)-w.begin()].pop_back();
        }
    }
    mint ans=0;
    for(int i=0; i<n; i++){
        if(s[i]=='1') ans+=dp[i];
    }
    int cnt0=0;
    for(int i=n-1; i>=0; i--){
        if(s[i]=='0') cnt0++;
        else break;
    }
    ans*=mint(cnt0+1);
    cout<<ans.val()<<endl;
    return 0;
}
0