http://www.lydsy.com/JudgeOnline/problem.php?id=4513
f[i][0/1][0/1][0/1] 从高到低第i位，是否卡n的上限，是否卡m的上限，是否卡k的下限 的方案数
g[i][0/1][0/1][0/1] 对应 f 的和
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[62][2][2][2],g[62][2][2][2]; template<typename T> void read(T &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void solve() { long long n,m,k; int p; read(n); read(m); read(k); read(p); memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); f[61][1][1][1]=1; int A,B,C,z; int ni,mi,ki; for(int i=60;i>=0;--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]) { ni=n>>i&1; mi=m>>i&1; ki=k>>i&1; for(int x=0;x<=1;++x) if(!a || x<=ni) for(int y=0;y<=1;++y) if(!b || y<=mi) { z=x^y; if(c && z<ki) continue; A=a&x==ni; B=b&&y==mi; C=c&&z==ki; f[i][A][B][C]=(f[i][A][B][C]+f[i+1][a][b][c])%p; g[i][A][B][C]=(g[i][A][B][C]+g[i+1][a][b][c])%p; if(z) g[i][A][B][C]=(g[i][A][B][C]+(1LL<<i)%p*f[i+1][a][b][c]%p)%p; } } printf("%d ",(g[0][0][0][0]-k%p*f[0][0][0][0]%p+p)%p); } int main() { int T; read(T); while(T--) solve(); return 0; }