結果

問題 No.2279 OR Insertion
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:06:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 512 ms / 2,000 ms
コード長 2,295 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 78,088 KB
最終ジャッジ日時 2025-04-09 21:08:33
合計ジャッジ時間 14,782 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n = int(input())
s = list(input())

result = 0

max_k = n - 1  # since k+1 <=n implies k <=n-1

pow2_nminus1 = pow(2, n-1, MOD)

for k in range(0, max_k + 1):
    # Compute allowed splits for this k
    dp = [0] * (n + 1)
    dp[0] = 1
    pre = [0] * (n + 1)
    pre[0] = 1
    for i in range(1, n + 1):
        if i < k + 1:
            # All j <i are considered (since i-j <k+1)
            dp_i = pre[i-1]
        else:
            # sum1 = j >=i-k
            sum1 = (pre[i-1] - (pre[i - k - 1] if (i - k -1) >=0 else 0)) % MOD
            # sum2 = j <=i-k-1 and S[i-k-1] == '0'
            idx = i - k -1 -1  # because i is 1-based, s is 0-based, and the position is i -k -1 is for the current part ending at i-1
            if i -k -1 -1 <0:  # i-k-1 is 0-based in S
                char = '0'
            else:
                char = s[i - k -1 -1]  # because i-k-1 is the position in the part's binary number that determines the bit
            # original code may have a mistake here:
            # wait for substring j..i-1 (i is 1-based), which has length l = i-1 -j +1 =i-j
            # correct position is i-1 - k -1? No, for k-th bit, the position in the original string is (i-1 -k)
            # wait when j..i-1 is the substring, the index in the substring that contributes to the k-th bit is (l-1 -k), l =i-j
            # So the position in original string is j + (l-1 -k) =j + (i-j-1 -k) = i-1 -k.
            # So i-1 -k is the correct index in s
            # So the code should check s[i-1 -k]
            # i is 1-based. when processing i, it's first i characters (0..i-1 in s)
            # so for substring j..i-1, the critical index is i-1 -k
            # which must be >=0
            if (i-1 -k) >=0 and (i-1 -k) < len(s):
                char = s[i-1 -k]
            else:
                char = '0'  # if out of bounds, not relevant
            if char == '0':
                sum2 = pre[i - k -1] % MOD
            else:
                sum2 = 0
            dp_i = (sum1 + sum2) % MOD
        dp[i] = dp_i % MOD
        pre[i] = (pre[i-1] + dp[i]) % MOD
    
    allowed = dp[n] % MOD
    total_splits = pow2_nminus1
    contr = (total_splits - allowed) * pow(2, k, MOD)
    contr %= MOD
    result = (result + contr) % MOD

print(result % MOD)
0