結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    X = int(input[ptr]); ptr +=1
    Y = int(input[ptr]); ptr +=1
    A = list(map(int, input[ptr:ptr+K]))
    ptr += K
    
    # Remove duplicates and ensure order (though problem states A has unique elements)
    A = list(dict.fromkeys(A))
    K = len(A)
    
    # Precompute allowed transitions: for each element index, list of allowed next indices
    allowed = [[] for _ in range(K)]
    for i in range(K):
        for j in range(K):
            if i != j:
                allowed[i].append(j)
    
    # Determine the maximum possible XOR value
    max_xor = 0
    if N > 0:
        max_a = max(A)
        max_xor = max_a
        # For N elements, the maximum XOR can be up to (max_a) * (some factor), but in practice, we use the maximum possible based on problem constraints
        # For the original problem constraints, A_i < 1024, so max_xor is 1023
        # For other cases, this might need adjustment, but here we proceed with 1024 as per original constraints
        max_xor = 1023  # Assuming original problem's constraints
    
    # Initialize DP: prev_dp[i][x] is the count ending with A[i] with XOR x
    prev_dp = [[0] * (max_xor + 1) for _ in range(K)]
    for i in range(K):
        a = A[i]
        prev_dp[i][a] = 1  # First element is a
    
    for _ in range(N - 1):
        next_dp = [[0] * (max_xor + 1) for _ in range(K)]
        for i in range(K):
            for x in range(max_xor + 1):
                if prev_dp[i][x] == 0:
                    continue
                cnt = prev_dp[i][x]
                for j in allowed[i]:
                    q = A[j]
                    new_x = x ^ q
                    if new_x > max_xor:
                        continue  # Skip if beyond the considered range
                    next_dp[j][new_x] = (next_dp[j][new_x] + cnt) % MOD
        prev_dp = next_dp
    
    total = 0
    for i in range(K):
        for x in range(X, Y + 1):
            if x <= max_xor:
                total = (total + prev_dp[i][x]) % MOD
    print(total % MOD)

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