当 $k = 0$ 时，内部为 $1$ 当且仅当 $x = y$，答案为 $2^n - 1$。

当 $k = 1$ 时：

• $x = y$ 且 $\text{popcount}(x) = 1$ 时答案为 $2$，$x = y$ 且 $\text{popcount}(x) > 1$ 时答案为 $1$，这部分的答案为 $2^n + n - 1$。
• $\text{popcount}(x) > 1$ 时拿掉一个二进制位 $1$ 可以使得答案为 $1$，所有 $n$ 位二进制数中每位为 $1$ 的频率均为 $\dfrac{1}{2}$，一共 $2^{n - 1} \cdot n$ 个 $1$，去掉 $\text{popcount}(x) = 1$ 的情况后有 $2^{n - 1} \cdot n - n$ 个，考虑 $(x, y)$ 互换后这部分的答案为 $2^n \cdot n - 2n$ 个。
• 上面两部分求和得到 $(n + 1) \cdot (2^n - 1)$。

#include <bits/stdc++.h>
using namespace std;
long long p[32];
const int P = 998244353;
long long power(int x, long long y)
{
	y %= P - 1;
	long long ans = 1;
	for (int i = 29; i >= 0; i--)
		if (y & (1 << i)) ans = ans * p[i] % P;
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	p[0] = 2;
	for (int i = 1; i <= 30; i++)
		p[i] = p[i - 1] * p[i - 1] % P;
	int T;
	cin >> T;
	while (T--)
	{
		long long n, k;
		cin >> n >> k;
		if (k == 0) cout << power(2, n) - 1 << '\n';
		if (k == 1) cout << (n + 1) % P * (power(2, n) - 1) % P << '\n';
	}
	return 0;
}

• 对于 $k = 0$ 的情况，只有当 $x = y$ 时，表达式值为 $1$，否则为 $0$，所以和为 $2 ^ n - 1$。

• 对于 $k = 1$ 的情况，通过分析二进制位的性质，推导出通项公式为 $(n + 1) \times 2 ^ n - n - 1$。

AC code：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define ll long long

ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        if (k == 0) {
            cout << (qpow(2, n, MOD) - 1 + MOD) % MOD << endl;
        } else {
            cout << ((((n % MOD) + 1) % MOD * qpow(2, n, MOD) % MOD) - (n % MOD) - 1 + MOD) % MOD << endl;
        }
    }
    return 0;
}

观察到 $k=0$ 时答案为 $2^n-1$，$k=1$ 时答案为 $(n+1)(2^n-1)$。使用快速幂即可，时间复杂度 $O(T \log n)$。

进一步地，可以把指数对 $p - 1$ 取模后先做光速幂，时间复杂度 $O(\sqrt{p} + T)$。

#include <bits/stdc++.h>
using namespace std;
long long p[32];
const int P = 998244353;
long long power(int x, long long y)
{
	y %= P - 1;
	long long ans = 1;
	for (int i = 29; i >= 0; i--)
		if (y & (1 << i)) ans = ans * p[i] % P;
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	p[0] = 2;
	for (int i = 1; i <= 30; i++)
		p[i] = p[i - 1] * p[i - 1] % P;
	int T;
	cin >> T;
	while (T--)
	{
		long long n, k;
		cin >> n >> k;
		if (k == 0) cout << power(2, n) - 1 << '\n';
		if (k == 1) cout << (n + 1) % P * (power(2, n) - 1) % P << '\n';
	}
	return 0;
}