一个点就是一个数对 ((x,y))。
记状态 (f[i][1/0][1/0][1/0]) 和 (g[i][1/0][1/0][1/0])，其中三个 (1/0) 取值分别代表“(x) 在前 (i) 位卡满 (n)（的前 (i) 位）/小于它”、“(y) 在前 (i) 位卡满 (m)（的前 (i) 位）/小于它”、“(k_{current}) 在前 (i) 位卡满 (k)（的前 (i) 位）/大于它”。(f) 是数值和，(g) 是方案数。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int T, f[62][2][2][2], g[62][2][2][2];
ll n, m, k, p;
int main(){
cin>>T;
while(T--){
scanf("%lld %lld %lld %lld", &n, &m, &k, &p);
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
g[61][1][1][1] = 1;
for(int i=60; i>=0; i--){
int dn=(n>>i)&1, dm=(m>>i)&1, dk=(k>>i)&1;
//取出 $n,m,k$ 的第 $i$ 位
for(int a=0; a<=1; a++)
for(int b=0; b<=1; b++)
for(int c=0; c<=1; c++)
if(f[i+1][a][b][c] || g[i+1][a][b][c])
for(int ia=0; ia<=1; ia++)
for(int ib=0; ib<=1; ib++){
int ic=ia^ib;
//确定当前第 $i$ 位上的 $x,y,k_{current}$ 的数值
if(a && ia>dn) continue;
//明明前头卡满了，现在又大了，就不合法了
if(b && ib>dm) continue;
if(c && ic<dk) continue;
int in=a&&ia==dn;
//是否现在还卡满
int im=b&&ib==dm;
int ik=c&&ic==dk;
g[i][in][im][ik] = (g[i][in][im][ik] + g[i+1][a][b][c]) % p;
f[i][in][im][ik] = (f[i][in][im][ik] + (f[i+1][a][b][c] + (ll)(ic-dk+p) % p * ((1ll<<i) % p) % p * g[i+1][a][b][c] % p) % p) % p;
}
}
printf("%d
", f[0][0][0][0]);
}
return 0;
}