結果
問題 |
No.1304 あなたは基本が何か知っていますか?私は知っています.
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)