提出 #65924905

---

ソースコード 拡げる

#include <iostream>
using namespace std;
#define LL long long
const LL M = 998244353;

LL n, k, d[65], ans;
LL f[65][2][65]; // f[i][j][k]，长度为i，以j开头，包含k个1，数字的个数
LL g[65][2][65]; // 数字之和

LL er(LL x) {
	return (1 << x) % M;
}

LL dg(LL i, LL k) {
	if (k < 0) return 0;
	if (i == 0) {
		return (k==0);
	}
	
	if (d[i] == 1) {
		ans = (ans + g[i][0][k]) % M;
		// cout << "add g" << i << ' ' << 0 << ' ' << k << "=" << g[i][0][k] << endl;
		LL num = dg(i-1, k-1);
		ans = (ans + num * er(i-1)) % M;
		// cout << "add " << num << "*" << (1<<(i-1)) << endl;
		return (num + f[i][0][k]) % M;
	}
	else {
		return dg(i-1, k);
	}
}

void work() {
	LL cnt = 0;
	ans = 0;
	while (n > 0) {
		d[++cnt] = n % 2;
		n /= 2;
	}
	dg(cnt, k);
	cout << ans << endl;
}

void Init() {
	f[1][0][0] = 1;
	f[1][1][1] = 1;
	g[1][1][1] = 1;
	for(int i = 2; i <= 60; i++) {
		for(int j = 0; j <= 1; j++) {
			for(int k = 0; k <= i; k++) {
				if (k-j >= 0) {
					f[i][j][k] = f[i-1][0][k-j] + f[i-1][1][k-j];
					g[i][j][k] = (g[i-1][0][k-j] + g[i-1][1][k-j]) % M;
					if (j == 1) g[i][j][k] = (g[i][j][k] + f[i][j][k] * er(i-1)) % M;
				}
			}
		}
	}
}

LL popcnt(LL x) {
	int num = 0;
	while (x > 0) {
		num += (x % 2);
		x /= 2;
	}
	return num;
}

void bl() {
	LL ans = 0;
	for(int i = 1; i <= n; i++) {
		if (popcnt(i) == k) ans += i;
	}
	cout << ans << endl;
}

int main()
{
	Init();
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> k; // 1~N 内， popcount(i) = k 的 i的和
		// bl();
		work();
	}
	return 0;
}

提出情報

ジャッジ結果