传送门

神仙数位$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);
    }    
}