結果

問題 No.1304 あなたは基本が何か知っていますか？私は知っています．
ユーザー lam6er
提出日時 2025-04-15 22:30:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,649 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 210,592 KB
最終ジャッジ日時 2025-06-22 03:10:00
合計ジャッジ時間 8,633 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 53 TLE * 1 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    X = int(data[2])
    Y = int(data[3])
    A = list(map(int, data[4:4+K]))
    
    # Preprocess allowed transitions for each previous element index
    allowed = [[] for _ in range(K)]
    for prev_idx in range(K):
        prev_val = A[prev_idx]
        for a_idx in range(K):
            if A[a_idx] != prev_val:
                allowed[prev_idx].append(a_idx)
    
    # Initialize DP: each element as the first element
    prev_dp = [{} for _ in range(K)]
    for idx in range(K):
        x = A[idx]
        prev_dp[idx][x] = 1
    
    # Iterate for N-1 steps (since first element is already handled)
    for _ in range(N - 1):
        curr_dp = [{} for _ in range(K)]
        for prev_idx in range(K):
            # For each allowed next element index
            for a_idx in allowed[prev_idx]:
                a_val = A[a_idx]
                # For each XOR value in the previous state
                for x_prev, cnt in prev_dp[prev_idx].items():
                    x_new = x_prev ^ a_val
                    if x_new in curr_dp[a_idx]:
                        curr_dp[a_idx][x_new] = (curr_dp[a_idx][x_new] + cnt) % MOD
                    else:
                        curr_dp[a_idx][x_new] = cnt % MOD
        prev_dp = curr_dp
    
    # Sum all valid XOR values in [X, Y]
    result = 0
    for idx in range(K):
        for x, cnt in prev_dp[idx].items():
            if X <= x <= Y:
                result = (result + cnt) % MOD
    print(result)

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