100分AC题解 谨慎使用

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int P=1e9+7;
const int M=1005;
int f[M];
int inv[M];
int c[M][M];
int Inv[200005];
int dp[65][M][2];
int t[65];
LL z;

inline int a(int x,int y){return x+y>=P?x+y-P:x+y;}
inline int d(int x,int y){return x-y<0?x-y+P:x-y;}
inline int m(int x,int y){return 1ll*x*y%P;}

inline int qp(int a,int b){
    if(b<0)return 0;
    int res=1;
    a%=P;
    while(b){
        if(b&1)res=m(res,a);
        a=m(a,a);
        b>>=1;
    }
    return res;
}

void init(int n){
    f[0]=1;
    for(int i=1;i<=n;++i)f[i]=m(f[i-1],i);
    inv[n]=qp(f[n],P-2);
    for(int i=n-1;~i;--i)inv[i]=m(inv[i+1],i+1);
    for(int i=0;i<=n;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j)c[i][j]=m(m(f[i],inv[j]),inv[i-j]);
    }
    Inv[0]=Inv[1]=1;
    for(int i=2;i<=200000;++i)Inv[i]=m(P-P/i,Inv[P%i]);
}

int calc(int n,LL r){
    for(int w=0;w<=60;++w)
        for(int i=0;i<=n;++i)
            dp[w][i][0]=dp[w][i][1]=0;
    memset(t,0,sizeof(t));
    int p=0;
    LL tr=r;
    while(tr)t[p++]=tr%2,tr/=2;
    int k0=z&1;
    for(int i=k0;i<=n;i+=2){
        int g=(i%2)<=t[0];
        dp[0][i/2][g]=c[n][i];
    }
    int zt[65]={0};
    for(int w=0;w<=60;++w)zt[w]=(z>>w)&1;
    for(int w=0;w<60;++w){
        for(int i=0;i<=n;++i){
            for(int j=0;j<2;++j){
                if(!dp[w][i][j])continue;
                int k=zt[w+1];
                for(int x=k;x<=n;x+=2){
                    int s=(i+x)%2;
                    int g;
                    if(s<t[w+1])g=1;
                    else if(s==t[w+1])g=j;
                    else{g=0;continue;}
                    int ni=(i+x)/2;
                    dp[w+1][ni][g]=a(dp[w+1][ni][g],m(dp[w][i][j],c[n][x]));
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<=n;++i){
        for(int j=0;j<2;++j){
            if(!dp[60][i][j])continue;
            int x=i;
            int now=61;
            int g=j;
            while(x){
                int num=x%2;
                if(num<t[now])g=1;
                else if(num>t[now])g=0;
                if(!g)break;
                x/=2;now++;
            }
            if(g)res=a(res,dp[60][i][j]);
        }
    }
    return res;
}

signed main(){
    init(1000);
    int n;LL l,r;
    scanf("%d%lld%lld%lld",&n,&l,&r,&z);
    int ar=calc(n,r);
    int al=l?calc(n,l-1):0;
    int ans=d(ar,al);
    printf("%d\n",ans);
    return 0;
}