挺隐蔽的数位DP。少见
其实减到0不减了挺难处理。。。。。然后就懵了。
其实换个思路：
xor小于k的哪些都没了，
只要留下(i^j)大于等于k的那些数的和以及个数，
和-个数*k就是答案
数位DP即可
f[i][0/1][0/1][0/1]表示，前i位，对n,m,k有无限制<=n,<=m,>=k？，xor值的总和
g[i][0/1][0/1][0/1]表示，前i位，对n,m,k有无限制<=n,<=m,>=k？，合法的方案数
然后枚举这一位的n，m数位填什么转移
注意爆int和爆long long：
1.1<<p爆int，这个还很大，必须立刻取模
2.最后tmp*k爆long long，k先对p取模
不稳啊~~
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define int long long
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(ll &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=;
ll n,m,k;
ll mod;
ll f[N][][][];
ll g[N][][][];
int main(){
int t;
rd(t);
while(t--){
scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);
--n;--m;
memset(g,,sizeof g);memset(f,,sizeof f);
g[][][][]=;
for(reg p=;p>=;--p){
int nn=(n>>p)&1LL,nm=(m>>p)&1LL,nk=(k>>p)&1LL;
// cout<<" wei "<<p<<endl;
// cout<<nn<<" "<<nm<<" "<<nk<<endl;
for(reg i=;i<=;++i){//i
for(reg j=;j<=;++j){//j
for(reg l=;l<=;++l){//lim n
for(reg r=;r<=;++r){//lim m
for(reg o=;o<=;++o){//lim k
if((l&&i>nn)||(r&&j>nm)||(o&&((i^j)<nk))) continue;
(f[p][((!l)||(i<nn))?:][((!r)||(j<nm))?:][((!o)||((i^j)>nk))?:]+=(f[p+][l][r][o]+(ll)(i^j)*(1LL*<<p)%mod*g[p+][l][r][o]%mod)%mod)%=mod;
(g[p][((!l)||(i<nn))?:][((!r)||(j<nm))?:][((!o)||((i^j)>nk))?:]+=(g[p+][l][r][o]))%=mod;
}
}
}
}
}
}
ll ans=;
ll tmp=;
for(reg l=;l<=;++l){//lim n
for(reg r=;r<=;++r){//lim m
for(reg o=;o<=;++o){//lim k
(ans+=f[][l][r][o])%=mod;
(tmp+=g[][l][r][o])%=mod;
}
}
}
k%=mod;
ans=(ans%mod-tmp%mod*k%mod+mod)%mod;
printf("%lld\n",ans%mod);
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/26 18:48:55
*/
如果想到统计<=k的和和个数的话，就是一个限制比较多（维度多）的数位DP罢了。