結果
問題 |
No.1952 xooooooooooor
|
ユーザー |
![]() |
提出日時 | 2022-05-20 22:48:35 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 788 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-09-20 09:10:09 |
合計ジャッジ時間 | 2,255 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
mod = 998244353 div2 = pow(2, mod-2, mod) def solve(N, M): res = 0 K = N.bit_length() cnt = 0 for i in range(K - 1): cnt ^= (N >> i) & 1 res += (1 << i) * cnt res %= mod two = pow(2, K + M - 1, mod) cnt = 0 for i in range(1, K)[::-1]: cnt ^= (N >> i) & 1 two = two * div2 % mod res += two * cnt res %= mod if bin(N).count("1") % 2 == 1: res += pow(2, M, mod) - pow(2, K - 1, mod) res %= mod return res def solve_naive(N, M): ans = 0 for i in range(M): ans ^= N << i return ans % mod def main(): N, M = map(int, input().split()) if N == 0: return 0 if M < 30: return solve_naive(N, M) return solve(N, M) print(main())