题解

有两种解法

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
vector<ll> po3 = [](){
	vector<ll> res{1};
	for (int i = 1; i < 40; ++i) 
		res.push_back(3*res.back());
	return res;
}();

ll full[40];
void gen_full(int k, ll dif) { 
	dif = abs(dif);
	if (k == 0) {
		full[k] = (dif == 0);
		return;
	}
	if (dif >= po3[k-1]) {
		gen_full(k-1,dif-2*po3[k-1]);
		full[k] = full[k-1];
	} else {
		gen_full(k-1,dif);
		full[k] = 3*full[k-1];
	}
}
 
ll rec(ll x, ll y, int k) {
	x %= po3[k], y %= po3[k];
	if (k == 0) return 1;
	if (x < y) swap(x,y);
	if (x-y >= po3[k-1]) {
		if (x < 2*po3[k-1]) return 0;
		if (y < po3[k-1]) return rec(x,y,k-1);
		if (y >= po3[k-1]) return full[k-1];
	}
	if (x < po3[k-1]) return rec(x,y,k-1);
	if (y < po3[k-1]) return full[k-1];
	if (x < 2*po3[k-1]) return full[k-1]+rec(x,y,k-1);
	if (y < 2*po3[k-1]) return 2*full[k-1];
	return 2*full[k-1]+rec(x,y,k-1);
}
ll diag(ll x, ll y) {
	if (x < 0 || y < 0) return 0;
	gen_full(39,x-y);
	return rec(x,y,39);
}
 
int main() {
	int Q; cin >> Q;
	while (Q--) {
		ll d,x,y; cin >> d >> x >> y;
		cout << diag(x+d,y+d)-diag(x-1,y-1) << "\n";
	}
}

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

#define F0R(i,a) for (int i = 0; i < a; ++i)
 
int main() {
	vector<ll> po3{1};
	for (int i = 1; i < 40; ++i) 
		po3.push_back(3*po3.back());
	array<array<array<ll,2>,2>,3> dp, DP;
	int Q; cin >> Q;
	while (Q--) {
		ll d,x,y; cin >> d >> x >> y;
		dp = {}; dp[1][0][0] = 1;
		F0R(i,39) {
			DP = {};
			int dd = d/po3[i]%3, xd = x/po3[i]%3, yd = y/po3[i]%3;
			F0R(cmp,3) F0R(xc,2) F0R(yc,2) F0R(j,3) {
				int XD = (xd+xc+j)%3, XC = (xd+xc+j)/3;
				int YD = (yd+yc+j)%3, YC = (yd+yc+j)/3;
				int CMP = cmp;
				if (j > dd) CMP = 2;
				if (j < dd) CMP = 0;
				if (XD%2 == YD%2)
					DP[CMP][XC][YC] += dp[cmp][xc][yc];
			}
			swap(dp,DP);
		}
		cout << dp[0][0][0]+dp[1][0][0] << "\n";
	}
}