神仙数位$DP$。
仅考虑$i\ xor\ j\ge k$的数对,答案就是所有$\sum\sum[i\ xor\ j\ge K] i\ xor\ j-K\times\sum\sum[i\ xor\ j\ge K]$
二进制下数位$DP$。设$f(i,0/1,0/1,0/1)$为填到第$i$位、第一个数是否顶着$n$上界、第二个数是否顶着$m$上界、异或结果是否顶着$K$下界的所有异或结果大于等于$K$的数对的异或的算术和,$g(i,0/1,0/1,0/1)$为方案数。
套路数位$DP$,枚举第$i$位上的数字刷表转移就行了。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 704
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
long long f[62][2][2][2],g[62][2][2][2];
int N[62],M[62],K[62],pw[62]={1};
inline void work(long long x,int *a){
for(register int i=61;i;--i)a[i]=x>>(i-1)&1;
}
int main(){
int t=read();
while(t--){
long long n=read<long long>()-1,m=read<long long>()-1,p=read<long long>(),rec=p;
int mod=read();
work(n,N),work(m,M),work(p,K);
memset(f,0,sizeof f),memset(g,0,sizeof g);
for(register int i=1;i<=60;++i)pw[i]=(pw[i-1]<<1)%mod;
g[61][1][1][1]=1;
for(register int i=61;i;--i)
for(register int j=0;j<2;++j)
for(register int k=0;k<2;++k)
for(register int l=0;l<2;++l)
for(register int a=0;a<=(j?N[i]:1);++a)
for(register int b=0;b<=(k?M[i]:1);++b){
int c=a^b;
if(l&&c<K[i])continue;
(g[i-1][j&&a==N[i]][k&&b==M[i]][l&&c==K[i]]+=g[i][j][k][l])%=mod;
(f[i-1][j&&a==N[i]][k&&b==M[i]][l&&c==K[i]]+=f[i][j][k][l]+(c?g[i][j][k][l]*pw[i-1]:0))%=mod;
}
long long ans=0;
rec%=mod;
for(register int i=0;i<2;++i)
for(register int j=0;j<2;++j)
for(register int k=0;k<2;++k)
(ans+=f[0][i][j][k]-rec*g[0][i][j][k])%=mod;
printf("%lld\n",(ans+mod)%mod);
}
}