結果
問題 |
No.1952 xooooooooooor
|
ユーザー |
![]() |
提出日時 | 2022-05-20 22:41:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,250 bytes |
コンパイル時間 | 1,578 ms |
コンパイル使用メモリ | 169,208 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-20 09:00:19 |
合計ジャッジ時間 | 2,517 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; long long modpow(long long a, long long b){ long long ans = 1; while (b > 0){ if (b % 2 == 1){ ans *= a; ans %= MOD; } a *= a; a %= MOD; b /= 2; } return ans; } int main(){ long long N, M; cin >> N >> M; if (N == 0){ cout << 0 << endl; } else if (M <= 29){ long long ans = 0; for (int i = 0; i < M; i++){ ans ^= N; N <<= 1; } ans %= MOD; cout << ans << endl; } else { string S; while (N > 0){ S += '0' + N % 2; N /= 2; } int L = S.size(); long long ans = 0; for (int i = 0; i < L - 1; i++){ int sum = 0; for (int j = 0; j <= i; j++){ sum += S[j] - '0'; } if (sum % 2 == 1){ ans += modpow(2, i); } } int cnt = 0; for (int i = 0; i < L; i++){ cnt += S[i] - '0'; } if (cnt % 2 == 1){ ans += (modpow(2, M - L + 1) - 1) * modpow(2, L - 1) % MOD; } for (int i = 1; i < L; i++){ int sum = 0; for (int j = i; j < L; j++){ sum += S[j] - '0'; } if (sum % 2 == 1){ ans += modpow(2, M - 1 + i); } } ans %= MOD; cout << ans << endl; } }