結果

問題 No.1304 あなたは基本が何か知っていますか？私は知っています．
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:36:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 683 ms / 2,000 ms
コード長 1,390 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 96,632 KB
最終ジャッジ日時 2025-06-22 03:10:26
合計ジャッジ時間 9,230 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 44 RE * 10 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    MOD = 998244353
    N, K, X, Y = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    element_to_index = {a: i for i, a in enumerate(A)}
    max_xor = 1023  # Based on problem constraints
    
    # Precompute next indices for each element
    next_indices = []
    for a_prev in A:
        indices = []
        for idx, a_next in enumerate(A):
            if a_next != a_prev:
                indices.append(idx)
        next_indices.append(indices)
    
    # Initialize DP
    dp = [[0] * (max_xor + 1) for _ in range(K)]
    for idx in range(K):
        a = A[idx]
        dp[idx][a] = 1
    
    for _ in range(N - 1):
        new_dp = [[0] * (max_xor + 1) for _ in range(K)]
        for a_prev_idx in range(K):
            for x in range(max_xor + 1):
                if dp[a_prev_idx][x] == 0:
                    continue
                for a_next_idx in next_indices[a_prev_idx]:
                    a_next = A[a_next_idx]
                    new_x = x ^ a_next
                    new_dp[a_next_idx][new_x] = (new_dp[a_next_idx][new_x] + dp[a_prev_idx][x]) % MOD
        dp = new_dp
    
    result = 0
    for idx in range(K):
        for x in range(X, Y + 1):
            result = (result + dp[idx][x]) % MOD
    print(result)

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