結果

問題 No.1654 Binary Compression
ユーザー qwewe
提出日時 2025-05-14 13:26:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,083 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 252,980 KB
最終ジャッジ日時 2025-05-14 13:27:36
合計ジャッジ時間 10,702 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    S = input()
    N = len(S)
    MOD = 924844033

    if all(c == '0' for c in S):
        print(N)
        return

    N_L = 0
    while N_L < N and S[N_L] == '0':
        N_L += 1

    N_R = 0
    while N_R < N and S[N - 1 - N_R] == '0':
        N_R += 1

    core_S = S[N_L : N - N_R]
    
    if not core_S: # Should not happen if not all zeros
        # This case implies S was like "00" and core_S became empty,
        # but we already handled all zeros case.
        # If S = "001100" -> N_L=2, N_R=2, core_S = "11"
        # This check is defensive, but logic implies core_S is non-empty here
        print(0) # Or some other appropriate value for an edge case
        return

    # Parse core_S into blocks B_i (ones) and Z_j (zeros)
    # core_S starts and ends with '1'
    # B0 Z1 B1 Z2 ... Zm Bm
    # x_lengths for B blocks, y_lengths for Z blocks
    
    x_lengths = []
    y_lengths = []
    
    curr = 0
    # First block must be 1s (B0)
    count = 0
    while curr < len(core_S) and core_S[curr] == '1':
        count += 1
        curr += 1
    x_lengths.append(count)
    
    while curr < len(core_S):
        # Next block must be 0s (Zj)
        count = 0
        while curr < len(core_S) and core_S[curr] == '0':
            count += 1
            curr += 1
        y_lengths.append(count)
        
        # Next block must be 1s (Bj)
        # It's possible core_S ends with Z block if original S ended with 0s inside core part
        # But definition of core_S implies it ends with '1'. So this B block must exist.
        if curr < len(core_S):
            count = 0
            while curr < len(core_S) and core_S[curr] == '1':
                count += 1
                curr += 1
            x_lengths.append(count)
            
    num_B_blocks = len(x_lengths) # This is m+1
    num_Z_blocks = len(y_lengths) # This is m
    
    # Calculate K_core
    # SufP[i] = product_{j=i to num_Z_blocks-1} (y_lengths[j]+1)
    # More precisely, SufP[i] = product_{Z_k after B_i} (length of Z_k + 1)
    # Product from j=i to m-1 of (y_lengths[j]+1)
    # K_core = sum_{i=0 to num_B_blocks-1} (x_lengths[i] * product_{k=i to num_Z_blocks-1} (y_lengths[k]+1) )
    
    # SufP_val[k] = product_{j=k to num_Z_blocks-1} (y_lengths[j]+1)
    # SufP_val[num_Z_blocks] = 1 (empty product)
    # SufP_val[k] = SufP_val[k+1] * (y_lengths[k]+1)
    
    suf_prods = [1] * (num_Z_blocks + 1)
    for k in range(num_Z_blocks - 1, -1, -1):
        suf_prods[k] = (suf_prods[k+1] * (y_lengths[k] + 1)) % MOD
        
    K_core = 0
    for i in range(num_B_blocks):
        term_prod = 1
        if i < len(suf_prods): # if there are Z blocks after B_i
             term_prod = suf_prods[i] 
        else: # B_i is the last block B_m, no Z blocks after it
             term_prod = 1

        term = (x_lengths[i] * term_prod) % MOD
        K_core = (K_core + term) % MOD
        
    ans_L = (N_L + 1) % MOD
    ans_R = (N_R + 1) % MOD
    
    final_ans = (ans_L * K_core) % MOD
    final_ans = (final_ans * ans_R) % MOD
    
    print(final_ans)

solve()
0