挺隐蔽的数位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
     
      #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=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=66;ll n,m,k;ll mod;ll f[N][2][2][2];ll g[N][2][2][2];int main(){        int t;    rd(t);    while(t--){        scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);        --n;--m;        memset(g,0,sizeof g);memset(f,0,sizeof f);        g[61][1][1][1]=1;                for(reg p=60;p>=0;--p){            int nn=(n>>p)&1LL,nm=(m>>p)&1LL,nk=(k>>p)&1LL;        //    cout<<" wei "<
      
<
       
        nn)||(r&&j>nm)||(o&&((i^j)
        
         nk))?0:1]+=(f[p+1][l][r][o]+(ll)(i^j)*(1LL*1<
         
          nk))?0:1]+=(g[p+1][l][r][o]))%=mod;                            }                        }                    }                }            }        }        ll ans=0;        ll tmp=0;        for(reg l=0;l<=1;++l){
   //lim n            for(reg r=0;r<=1;++r){
   //lim m                for(reg o=0;o<=1;++o){
   //lim k                    (ans+=f[0][l][r][o])%=mod;                    (tmp+=g[0][l][r][o])%=mod;                    }            }        }        k%=mod;        ans=(ans%mod-tmp%mod*k%mod+mod)%mod;        printf("%lld\n",ans%mod);    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/2/26 18:48:55*/
         
        
       
     

如果想到统计<=k的和和个数的话，就是一个限制比较多（维度多）的数位DP罢了。