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;
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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
AC × 3
AC × 49
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


2025-02-27 (Thu)
22:48:15 +00:00