Submission #66614017

---

Source Code Expand

#include <stdio.h>
#include <inttypes.h>

#define MOD_BY 998244353

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int T, tc;
uint64_t N;
int K;

struct res_s {
	int sum, num;
} memo[64][64][2];
int memo_gen[64][64][2];

struct res_s calc(int pos, int left, int sati) {
	const int bit = (N >> pos) & 1;
	struct res_s ans = {0, 0};
	if (pos < 0) return (struct res_s){0, left == 0};
	if (memo_gen[pos][left][sati] == tc) return memo[pos][left][sati];
	/* 0 */
	{
		struct res_s delta = calc(pos - 1, left, sati && bit == 0);
		ans.sum = add(ans.sum, delta.sum);
		ans.num = add(ans.num, delta.num);
	}
	/* 1 */
	if (left > 0 && (!sati || bit != 0)) {
		struct res_s delta = calc(pos - 1, left - 1, sati);
		ans.sum = add(ans.sum, add(delta.sum, mul((1LL << pos) % MOD_BY, delta.num)));
		ans.num = add(ans.num, delta.num);
	}
	memo_gen[pos][left][sati] = tc;
	memo[pos][left][sati] = ans;
	return ans;
}

int main(void) {
	int i;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
		if (scanf("%" SCNu64 "%d", &N, &K) != 2) return 1;
		printf("%d\n", calc(63, K, 1).sum);
	}
	return 0;
}

Submission Info

Judge Result