結果

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

ソースコード

diff # 

N, K, X, Y = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

# Determine the maximum possible XOR value based on input elements and X, Y
max_val = max(A + [X, Y])
required_bits = max_val.bit_length()
M = 1 << required_bits if (max_val & (max_val + 1)) != 0 else max_val + 1

# Initialize DP table: current_dp[prev_index][xor_val] = count
current_dp = [[0] * M for _ in range(K)]
for i in range(K):
    current_dp[i][A[i]] = 1

for _ in range(N - 1):
    # Precompute sum_total[x] which is the sum of current_dp[j][x] for all j
    sum_total = [0] * M
    for x in range(M):
        total = 0
        for j in range(K):
            total = (total + current_dp[j][x]) % MOD
        sum_total[x] = total
    
    # Compute next_dp
    next_dp = [[0] * M for _ in range(K)]
    for i in range(K):
        ai = A[i]
        for x_new in range(M):
            x_prev = x_new ^ ai
            next_dp[i][x_new] = (sum_total[x_prev] - current_dp[i][x_prev]) % MOD
    current_dp = next_dp

# Sum up all valid XOR values
result = 0
for i in range(K):
    for x in range(M):
        if X <= x <= Y:
            result = (result + current_dp[i][x]) % MOD

print(result)
0