这题差点(已经)把我的心态搞爆了 qwq，似乎因为忘记了数位 \(dp\) 的基本姿势而自闭了一天一夜

\(f_{i, pn, pm, pk}.first\) 为从第 \(i\) 位开始考虑，并且 \(i + 1\) 位以前的数 \(n,m\) 卡不卡上界，且目前的异或值卡不卡 \(k\) 的下界

\(f_{i, pn, pm, pk}.second\) 为对应的方案数

转移时枚举当前位 \(n,m\) 分别选什么即可

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

typedef long long LL;

typedef pair <int, int> pii;

const int N = 65;

LL n, m, k;

bool vis[N][2][2][2];

pii f[N][2][2][2];

int mod, T, mx;

pii dfs_(int x, int pn, int pm, int pk) {
	if (x < 0)
		return pii(0, 1);
	if (vis[x][pn][pm][pk])
		return f[x][pn][pm][pk];
	vis[x][pn][pm][pk] = 1;
	int qn = pn ? (n>>x)&1 : 1, qm = pm ? (m>>x)&1 : 1;
	pii ans(0, 0), tp;
	for (int i = 0; i <= qn; i++)
		for (int j = 0; j <= qm; j++)
			if (((i^j) >= ((k>>x)&1)) || !pk) {
				tp = dfs_(x - 1, pn && i == qn, pm && j == qm, pk && ((i^j) == ((k>>x)&1)));
				ans.second = (ans.second + tp.second)%mod;
				ans.first = (ans.first + tp.first + 1ll*tp.second*((1ll*(i^j)<<x)%mod))%mod;
			}
	return f[x][pn][pm][pk] = ans;
}

void solve_() {
	memset(vis, 0, sizeof(vis));
	mx = 0;
	for (int i = 0; i <= 62; i++)
		if ((n|m|k)&(1ll<<i))
			mx = i;
	dfs_(mx, 1, 1, 1);
	printf("%lld\n", (f[mx][1][1][1].first - 1ll*f[mx][1][1][1].second*(k%mod)%mod + mod)%mod);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld%d", &n, &m, &k, &mod);
		n--, m--;
		solve_();
	}
}