Submission #54119516
Source Code Expand
Copy
#include <bits/stdc++.h>using namespace std;const long long mod = 998244353;const long long rev2 = 998244354 / 2;const int maxn = 2e5 + 10;long long binpow(long long x, long long power) {long long ans = 1;long long num = x;while (power > 0) {if (power & 1) {ans *= num;ans %= mod;power--;} else {num *= num;num %= mod;power >>= 1;}}return ans;}
#include <bits/stdc++.h> using namespace std; const long long mod = 998244353; const long long rev2 = 998244354 / 2; const int maxn = 2e5 + 10; long long binpow(long long x, long long power) { long long ans = 1; long long num = x; while (power > 0) { if (power & 1) { ans *= num; ans %= mod; power--; } else { num *= num; num %= mod; power >>= 1; } } return ans; } long long solve(long long x, long long m) { if (x == 0) { return 0; } unsigned long long old = (1ll << __lg(x)) - 1; long long ans = 0; ans += (long long)__builtin_popcountll(old & m) * (((old + 1) / 2) % mod) % mod; ans += (long long)__builtin_popcountll(m & (old + 1)) * ((x - old) % mod) % mod; ans %= mod; x -= (old + 1); ans += solve(x, m); ans %= mod; return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif long long n, m; cin >> n >> m; cout << solve(n, m) << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | D - Masked Popcount |
User | N00BGH0ST |
Language | C++ 20 (gcc 12.2) |
Score | 400 |
Code Size | 1046 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 3648 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 3456 KB |
sample_02.txt | AC | 1 ms | 3512 KB |
sample_03.txt | AC | 1 ms | 3528 KB |
test_01.txt | AC | 1 ms | 3520 KB |
test_02.txt | AC | 1 ms | 3596 KB |
test_03.txt | AC | 1 ms | 3460 KB |
test_04.txt | AC | 1 ms | 3520 KB |
test_05.txt | AC | 1 ms | 3400 KB |
test_06.txt | AC | 1 ms | 3424 KB |
test_07.txt | AC | 1 ms | 3456 KB |
test_08.txt | AC | 1 ms | 3524 KB |
test_09.txt | AC | 1 ms | 3428 KB |
test_10.txt | AC | 1 ms | 3596 KB |
test_11.txt | AC | 1 ms | 3532 KB |
test_12.txt | AC | 1 ms | 3456 KB |
test_13.txt | AC | 1 ms | 3532 KB |
test_14.txt | AC | 1 ms | 3488 KB |
test_15.txt | AC | 1 ms | 3520 KB |
test_16.txt | AC | 1 ms | 3424 KB |
test_17.txt | AC | 1 ms | 3524 KB |
test_18.txt | AC | 1 ms | 3404 KB |
test_19.txt | AC | 1 ms | 3612 KB |
test_20.txt | AC | 1 ms | 3436 KB |
test_21.txt | AC | 1 ms | 3520 KB |
test_22.txt | AC | 1 ms | 3424 KB |
test_23.txt | AC | 1 ms | 3424 KB |
test_24.txt | AC | 1 ms | 3592 KB |
test_25.txt | AC | 1 ms | 3404 KB |
test_26.txt | AC | 1 ms | 3648 KB |
test_27.txt | AC | 1 ms | 3532 KB |
test_28.txt | AC | 1 ms | 3420 KB |
test_29.txt | AC | 1 ms | 3528 KB |
test_30.txt | AC | 1 ms | 3532 KB |
test_31.txt | AC | 1 ms | 3420 KB |
test_32.txt | AC | 1 ms | 3396 KB |
test_33.txt | AC | 1 ms | 3428 KB |
test_34.txt | AC | 1 ms | 3524 KB |
test_35.txt | AC | 1 ms | 3532 KB |
test_36.txt | AC | 1 ms | 3464 KB |
test_37.txt | AC | 1 ms | 3592 KB |
test_38.txt | AC | 1 ms | 3424 KB |
test_39.txt | AC | 1 ms | 3596 KB |
test_40.txt | AC | 1 ms | 3484 KB |
test_41.txt | AC | 1 ms | 3524 KB |
test_42.txt | AC | 1 ms | 3424 KB |
test_43.txt | AC | 1 ms | 3460 KB |
test_44.txt | AC | 1 ms | 3584 KB |
test_45.txt | AC | 1 ms | 3532 KB |
test_46.txt | AC | 1 ms | 3528 KB |