結果

問題 No.3117 Reversible Tile
コンテスト
ユーザー Kevgen
提出日時 2025-04-19 00:11:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,460 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-04-19 00:11:33
合計ジャッジ時間 1,784 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    # Check if all zeros (edge case)
    all_zero = all(a == 0 for a in A)
    
    # Compute K = number of possible pairs (L, R)
    K = N * (N + 1) // 2
    
    # Compute the required parity for each position in the difference array D
    # D[1..N] and T (D[N+1])
    D = []
    prev = 0
    for a in A:
        current = a
        D.append(current ^ prev)
        prev = current
    # T is sum(D) mod 2
    sum_D = sum(D) % 2
    
    # Check if the desired parity is possible given M
    # Each operation toggles exactly two positions (a and b)
    # The parity of the sum of all operations' toggles is even (2*M)
    # For the desired parity, sum(D) + T must be even, which it is.
    # So the parity is always possible if sum(D) is even.
    # However, the parity of M must be compatible with the required toggles for each position.
    # But this is not straightforward, so we need to proceed with the code.
    
    # Compute the answer as (K^M) / (2^N) modulo MOD
    numerator = pow(K, M, MOD)
    denominator = pow(2, N, MOD)
    inv_denominator = pow(denominator, MOD-2, MOD)
    ans = (numerator * inv_denominator) % MOD
    
    # Handle the case where A is all zeros and M is even
    # But this is already handled by the general approach
    print(ans)

if __name__ == '__main__':
    main()
0